アルゴリズムとプログラミング
平成28年度 秋期 基本情報技術者試験 午前 問6
2 分探索木になっている 2 分木はどれか。
2 分木 4 種（ア～エ）。各木の構造は choices に記述。
- ア [図] 根 16，左の子 15（その子は左 10・右 14），右の子 19。
- イ [図] 根 17，左の子 14（その子は左 10・右 16），右の子 19（その左の子 18）。
- ウ [図] 根 18，左の子 16（その子は左 15・右 14），右の子 19（その右の子 20）。
- エ [図] 根 20，左の子 18（その子は左 10・右 14），右の子 19（その子は左 15・右 16）。
出典：平成28年度 秋期 基本情報技術者試験 午前 問6
答えと解説を見る
正解：イ
覚える知識
2分探索木の大小関係
2分探索木は各節について左部分木の値が小さく、右部分木の値が大きい2分木である。
この問題で必要なこと
どの節でも左部分木の全値が節より小さく、右部分木の全値が節より大きいことを確認する。イは全ての節で条件を満たす。
ひっかけ
親の直下の子だけ見て、祖先との大小関係(深い位置の値の違反)を見落とさせる。
この知識の出題：本試験系 4 回・免除試験 8 回（公開問題での観測値）