ソフトウェア開発技術者試験 2001年度 = 平成13年度 午前 問9

 データ構造に関する記述のうち、B木の説明として適切なものはどれか。

ア ある特定のアルゴリズムに従って、レコードのキー値から物理的な格納アドレスを求めてレコードを格納する。
イ 索引部の各ノードを、そのキー値を中心にして小さい側と大きい側のレコード数がある許容範囲で平衡を保つよう動的に再配置する。
ウ レコードの物理的配置とは独立に、論理的にレコードをつなぐポインタによって、レコードを関係づけて格納する。
エ レコードをキー値の昇順にトラックなどのアクセス単位(ぺ一ジ)ごとに格納し、各ぺージ内の最大キー値とそのぺ一ジの番地をもつ索引を作る。

解答



解説

 B木は、主に外部記憶域上での探索に適した木構造のデータ構造であり、次の条件を満たすものを、n階のB木と呼びます。
  (1) 根は、葉であるか、もしくは2ないしn個の子をもつ
  (2) 根、葉以外のノードは、[m/2]ないしm個の子をもつ
      ※[m/2]は、切り上げを表す
  (3) 根からすべての葉までの経路の長さが等しい
(3)の条件から答えがであることがわかります。
 なお、はハッシュ法、は線形リスト、は索引順編成ファイルです。

BohYoh.comトップページへ