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

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

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

解答



解説

 B木は、主に外部記憶域上での探索に適した木構造のデータ構造であり、次の条件を満たすものを、n階のB木と呼びます。
  (1) 根は、葉であるか、もしくは2ないしn個の子をもつ
  (2) 根、葉以外のノードは、[m/2]ないしm個の子をもつ
      ※[m/2]は、切り上げを表す
  (3) 根からすべての葉までの経路の長さが等しい

 ある特定のアルゴリズムに従って、レコードのキー値から物理的な格納アドレスを求めてレコードを格納するのは、ハッシュ法です。

 索引部の各ノードのキー値を中心にして、小さい側のレコード数と大きい側のレコード数の比率が、ある許容範囲内に収まるように動的に再配置します。

 レコードの物理的配置とは独立に、論理的にレコードをつなぐポインタによって、レコードを関係づけて格納するのは、リスト構造です。

 レコードをキー値の昇順にトラックなどのアクセス単位(ページ)ごとに格納し、各ページ内の最大キー値とそのページの番地をもつ索引を作るのは、索引順編成ファイルです。


BohYoh.comトップページへ