応用情報技術者試験 応用情報技術者試験 平成28年度秋期 午前 問5: ある B 木は，各節点に 4 個のキーを格納し，5 本の枝を出す。この B 木の根（深さのレベル 0）から深さのレベル 2 までの節点に格納できるキーの個数は，

正解

エ. 124

正答率 72.5%（1,304人中 946人が正解）

問題の解説

各節点は最大 4 個のキーと 5 本の枝を持つので、深さが 1 つ下がるごとに節点数は 5 倍になる。レベル 0 は 1 個、レベル 1 は 5 個、レベル 2 は 25 個で、節点は合計 31 個である。キーは 1 節点に最大 4 個なので、31 × 4 = 124 個になる。

選択肢ごとの解説

• ア24 は、レベル 0 と 1 の節点 (1 + 5 = 6 個) だけにキーを数えた値である。レベル 2 の 25 個の節点を含めていない。
• イ31 は節点の総数 (1 + 5 + 25) であり、キーの個数ではない。各節点に最大 4 個のキーが入るので、4 倍する必要がある。
• ウ120 は、根を除いたレベル 1 と 2 の節点 (5 + 25 = 30 個) だけにキーを数えた値である。根の節点のキー 4 個が漏れている。
• エ正しい。節点数 1 + 5 + 25 = 31 個に、1 節点当たりの最大キー数 4 を掛けて、124 個になる。