平成28年度 秋期 午前 問5

✓ これが正解エ124

解説

節点の数を先に数えて、最後に4を掛けます。

この型の問は、キーの個数をいきなり足し合わせようとすると途中で迷います。先に節点がいくつあるかを数え、最後にまとめて1節点あたりのキーの個数を掛けるのが手堅い順序です。まず節点の数を段ごとに出します。根は1個です。根からは枝が5本出るので、その次の段は1×5で5個です。その5個からもそれぞれ5本ずつ出るので、さらに次の段は5×5で25個です。深さのレベル2までという指定なので、数えるのはこの3段ぶんで、合計は1＋5＋25＝31個になります。等比数列の和として確かめても、(125－1)÷(5－1)＝31で一致します。ここまで来てはじめて、1つの節点に格納できるキーが4個であることを使います。31×4＝124が答えです。レベル0から数えると書いてあるので根を数に入れること、そしてレベル2は上から3段目にあたること、この二つを取り違えなければ迷いません。

ほかの選択肢はなぜ違うのか

• ア24：根とその一つ下までで打ち切った場合の値です。1＋5で6個ぶんに4を掛けると24になりますが、指定された深さにはもう一段ぶんの25個が含まれているので、数え足りません。
• イ31：節点がいくつあるかを数え終えたところで手を止めた値です。問われているのは格納できるキーの個数なので、ここから1節点あたり4個という条件を使う手が残っています。
• ウ120：下の二段だけを数えて根を数に入れなかった場合の値です。5＋25の30個に4を掛けると120になります。レベル0という言い方は根そのものを指しており、除いてよいという意味ではありません。