問題プレビューID: 031770d0基本情報技術者試験 午前免除試験 2026年6月14日

問 5
基本情報技術者試験 午前免除試験 2026年6月14日

値が重複しない 15 個の自然数のデータを一つずつ追加して 2 分探索木を構成するとき,その構成に関する記述のうち,適切なものはどれか。ここで,途中で木の再構成は行わないものとする。

解説

正解は「イ」です。

2 分探索木では,中間順巡回(左部分木 → 節 → 右部分木)でたどると値が小さい順に並びます。15 個のデータで完全 2 分木(深さ 4 の完全な 2 分木)となる木の形状はただ一つに定まり,各節に入る値も,小さい順に並べたデータをその形状に中間順で割り当てたものに一意に決まります。したがって,完全 2 分木となるデータの配置はただ一つだけ存在します。

  • ア: 同じ配置の木を作る追加順は複数あり得るため,追加順がただ一つに定まるわけではありません。
  • ウ: データを昇順に追加すると右に偏った木になるので,常に完全 2 分木となるわけではありません。
  • エ: 15 個のデータを適切な順に追加すれば完全 2 分木にできるので,常に完全 2 分木とならないわけではありません。

関連問題

本文が同じ・似ている問題を表示しています