アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 201007 実施分 問5
2 分探索木になっている 2 分木はどれか。
4つの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）
出典：基本情報技術者試験 科目A免除 修了試験 201007 実施分 問5
答えと解説を見る
正解：イ
覚える知識
2分探索木の大小関係
2分探索木は、各節点の左部分木の全要素がその節点より小さく、右部分木の全要素が大きい2分木である。
この問題で必要なこと
2分探索木では、全ての節点で左部分木の値<節点の値<右部分木の値が成り立つ。根だけでなく部分木内でも満たすか確認する。
ひっかけ
直接の親子だけ見て、根との大小関係(祖先全体との関係)を見落とさせる。
この知識の出題：本試験系 4 回・免除試験 8 回（公開問題での観測値）