問題プレビューID: a9583c02応用情報技術者試験 2016年(平成28年度)秋期 午前

問 5
応用情報技術者試験 2016年(平成28年度)秋期 午前

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

解説

正解は「エ」です。

各節点に最大 4 個のキーを格納できるので,レベルごとに節点数を数えてキー数を求めます。

  • レベル 0(根):節点は 1 個 → 1×4=41 \times 4 = 4 個
  • レベル 1:各節点が 5 本の枝を出すので節点は 5 個 → 5×4=205 \times 4 = 20 個
  • レベル 2:5×5=255 \times 5 = 25 個の節点 → 25×4=10025 \times 4 = 100 個

合計すると 4+20+100=1244 + 20 + 100 = 124 個となります。

  • ア: レベル 2 の節点数を誤って 5 個とした場合の値で,枝分かれの分だけ不足します。
  • イ: レベルごとの節点数を単純加算しただけの値(1+5+25=311 + 5 + 25 = 31)で,各節点のキー数 4 を掛けていません。
  • ウ: レベル 1 と 2 のキー数(20+10020 + 100)だけで,根の 4 個を加えていません。

よって正解は「エ」です。

関連問題

本文が同じ・似ている問題を表示しています