B 木に格納できるキーの数
出典: 平成28年度 秋期 応用情報技術者試験 午前 問5 (IPA)
ある B 木は，各節点に 4 個のキーを格納し，5 本の枝を出す。この B 木の根（深さのレベル 0）から深さのレベル 2 までの節点に格納できるキーの個数は，最大で幾つか。
- ア 24
- イ 31
- ウ 120
- エ 124
正解と解説を見る
正解: エ
- ア: 24 は、レベル 0 とレベル 1 の節点 (1 ＋ 5 = 6 個) だけで計算した値です。レベル 2 の 25 個も入れます。
- イ: 31 は節点の数です。各節点にキーが 4 個入るので、4 倍します。
- ウ: 120 は、レベル 1 とレベル 2 の節点 (5 ＋ 25 = 30 個) だけで計算した値です。根の 4 個も入れます。
- エ: 節点 31 個 × キー 4 個 = 124 個なので正しい答えです。
ポイント
- 1 つの節点から枝が 5 本出るので、節点の数は レベル 0: 1 個、レベル 1: 5 個、レベル 2: 25 個 で、合計 31 個 です。
- 各節点に 4 個のキーを格納できるので、31 × 4 = 124 個 です。