アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20210725 実施分 問7
2 分探索木になっている 2 分木はどれか。
選択肢ア〜エは 2 分木の図。構造は選択肢に記述。
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 20210725 実施分 問7（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：イ
覚える知識
2分探索木の大小関係
2分探索木は、各節について左部分木の全ての値がその節より小さく右部分木の全ての値が大きい2分木である。
この問題で必要なこと
全ての節で左部分木の全要素＜節＜右部分木の全要素。イは 17(14,10,16 / 19,18)で全節で成立する。
ひっかけ
子との比較だけでは不十分で、祖先節との大小も満たす必要がある(例 アの 14 は 15 の右だが 16 の左なので可、ウは 16 の右に 14 がある)。
この知識の出題：本試験系 4 回・免除試験 8 回（公開問題での観測値）