データ構造 (全29問中23問目)

No.23

データ構造に関する記述のうち,B木の説明として適切なものはどれか。
  • ある特定のアルゴリズムに従って,レコードのキー値から物理的な格納アドレスを求めてレコードを格納する。
  • 索引部の各ノードのキー値を中心にして,小さい側のレコード数と大きい側のレコード数の比率が,ある範囲内に収まるように動的に再配置しながら格納する。
  • レコードの物理的配置とは独立に,論理的にレコードをつなぐポインタによって,レコードを関係づけて格納する。
  • レコードをキー値の昇順にしてトラックなどのアクセス単位(ページ)ごとに格納し,各ページ内の最大キー値とそのページの番地をもつ索引を作る。
  • [この問題の出題歴]
  • ソフトウェア開発技術者 H13春期 問9
  • ソフトウェア開発技術者 H15春期 問9

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

B木は、木構造内のノードの容量の尺度である次数kを基準にして下記の特徴をもつ多分木です。
  • 根は1以上2k個以下のキーをもつ
  • 根以外の節はk以上2k個以下のキーをもつ
  • 根から全ての葉までの深さが同じである
09.gif/image-size:383×174
B木の各節は保持するキー数+1個のポインタをもちます。

k次のB木では、節点が持てる子の数が"k以上2k以下"という特徴があり、データの挿入や削除が行われた場合には、この範囲内に収まるように動的再構成が行われます。
  • ハッシュ法の説明です。
  • 正しい。
  • リスト構造の説明です。
  • 索引編成ファイルの構造についての説明です。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop