第２種情報処理技術者試験
1999年度 ＝ 平成11年度・春期
午前
問27
Ｂ木を用いてデータを格納するとき、適切なものはどれか。
ア
階層の深さが同じになるように、ノードの分割・併合を行う。
イ
キー値からある関数によってデータの格納位置を求める。
ウ
先頭データからの順次アクセスだけが可能である。
エ
登録簿とメンバに分かれ、メンバは順編成ファイルである。
解答
ア
解説
Ｂ木
は、主に外部記憶域上での探索に適した木構造のデータ構造であり、次の条件を満たすものを、
m階のＢ木
と呼びます。
(1) 根は、葉であるか、もしくは2ないしm個の子をもつ
(2) 根、葉以外のノードは、［m/2］ないしm個の子をもつ
※[m/2]は、切り上げを表す
(3) 根からすべての葉までの経路の長さが等しい
(3)の条件から答えが
ア
であることがわかります。
なお、
イ
はハッシュ法、
ウ
は順次アクセスファイル、
エ
は区分編成ファイルです。
