応用情報技術者 2016年 秋期 午前2 問05

あるB木は、各節点に4個のキーを格納し、5本の枝を出す。このB木の根 (深さのレベル0) から深さのレベル2 までの節点に格納できるキーの個数は、最大で幾つか。【午前2 解説】

要点まとめ

• 結論：深さ2までの節点に格納できるキーの最大数は124個です。
• 根拠：各節点は最大4個のキーを持ち、枝は5本。レベルごとの節点数は5のべき乗で増加します。
• 差がつくポイント：節点数の計算とキー数の掛け算を正確に行うことが重要です。

正解の理由

• レベル0（根）：節点数1 → キー数 $1\times 4=4$
• レベル1：節点数5 → キー数 $5\times 4=20$
• レベル2：節点数 $5^2=25$ → キー数 $25\times 4=100$
  合計は $4+20+100=124$ となり、選択肢の中でエが正解です。

よくある誤解

解法ステップ

1. B木の枝の数（5本）から節点の最大子数を確認する。
2. 各レベルの節点数を計算する（レベル $l$ の節点数は $5^l$）。
3. 各節点の最大キー数（4個）を掛けてレベルごとのキー数を求める。
4. レベル0からレベル2までのキー数を合計する。
5. 合計値と選択肢を比較し、正解を選ぶ。

選択肢別の誤答解説

• ア: 24
  レベルごとの節点数やキー数の計算が不足しており、合計が大幅に少ない。
• イ: 31
  根のキー数4とレベル1の節点数5を混同し、正確なべき乗計算ができていない。
• ウ: 120
  レベル2の節点数25に4を掛けて100とし、合計を誤って計算している可能性がある。
• エ: 124
  正確に計算した結果であり、正解。

補足コラム

FAQ