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

問題本文

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

選択肢

• ア.24
• イ.31
• ウ.120
• エ.124

正解

エ. 124

解説

B木(多分木)の節点数とキー数の数え上げを問う問題。各節点はキー4個・枝5本なので、ある節点からは5個の子節点が生まれる。レベル0(根)は節点1個、レベル1はその5本の枝の先で5個、レベル2は各節点がさらに5個ずつ子を持つので5×5=25個。よって節点数は 1+5+25=31個。各節点にキーが4個格納できるので、格納できるキーの最大個数は 31×4=124個となり、正解はエである。選択肢は数値のみで個別比較に意味が薄いため選択肢別解説は省略するが、イの31は「節点数」、ウの120は「125節点を24倍など」の計算ミスに対応する典型的な誤答である。