修了試験 2026-06-14実施分 基本情報技術者試験 問5

解説

正解は2です。 2分探索木は、各節点について「左の部分木の値は小さく、右の部分木の値は大きい」という条件を満たす木です。 15個の節点で完全2分木になるのは、深さ0から3までの各段がすべて埋まった形（1＋2＋4＋8＝15）です。 【選択肢別解説】 1：× 完全2分木になる追加順は一つではありません。 根になる中央値を最初に追加し、各部分木でもその中央値を子孫より先に追加すれば完全2分木になります。 この条件を守れば、左右の部分木のどちらを先に追加してもよいので、追加順は複数あります。 2：○ 完全2分木では、根は15個の中央値（小さいほうから8番目）に決まり、左右の部分木の根もそれぞれの7個の中央値に決まります。 これを繰り返すと各節点に入る値はすべて一意に決まるので、配置はただ一つです。 3：× 追加順によっては完全2分木になりません。 例えば昇順に追加すると、すべての節点が右の子に連なる一直線の木になります。 4：× 中央値から順に追加すれば完全2分木を作れます。 必ず完全2分木にならないわけではありません。 【ポイント】 2分探索木の形は追加順で変わり、偏ると探索の効率が落ちます。 「形（配置）が一意」と「追加順が一意」は別のことで、配置は一つでも追加順は複数あります。