アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20180128 実施分 問5
2 分探索木になっている 2 分木はどれか。
ア: 16(15(10,14),19)
イ: 17(14(10,16),19(18,―))
ウ: 18(16(15,14),19(―,20))
エ: 20(18(10,14),19(15,16))
（表記: 親(左の子,右の子)，―は子なし）
- ア [図] 根16，左の子15（その左の子10，右の子14），右の子19
- イ [図] 根17，左の子14（その左の子10，右の子16），右の子19（その左の子18）
- ウ [図] 根18，左の子16（その左の子15，右の子14），右の子19（その右の子20）
- エ [図] 根20，左の子18（その左の子10，右の子14），右の子19（その左の子15，右の子16）
出典：基本情報技術者試験 科目A免除 修了試験 20180128 実施分 問5
答えと解説を見る
正解：イ
覚える知識
2分探索木の大小関係
2分探索木は、各節について左部分木の全要素が節より小さく、右部分木の全要素が節より大きい木。
この問題で必要なこと
2分探索木では、全ての節で左部分木の値が節より小さく、右部分木の値が節より大きい。これを満たすのはイだけ。
ひっかけ
ア・ウ・エは、左右の子の大小関係か、部分木全体の大小関係のどこかが崩れている。
この知識の出題：本試験系 4 回・免除試験 8 回（公開問題での観測値）