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