アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20151220 実施分 問5
2 分探索木として適切なものはどれか。ここで，1～9 の数字は，各ノード（節）の値を表す。
ア: 1(2(4,5),3(6(8,9),7))／イ: 4(2(1,3),8(6(5,7),9))／ウ: 7(6(4,5),8(3(1,2),9))／エ: 9(7(1,2),8(5(3,4),6))。各 (左の子,右の子) の順に記述。
- ア [図] 根1。左の子2（その子 4，5），右の子3（その子 6，7）。6 の子は 8，9
- イ [図] 根4。左の子2（その子 1，3），右の子8（その子 6，9）。6 の子は 5，7
- ウ [図] 根7。左の子6（その子 4，5），右の子8（その子 3，9）。3 の子は 1，2
- エ [図] 根9。左の子7（その子 1，2），右の子8（その子 5，6）。5 の子は 3，4
出典：基本情報技術者試験 科目A免除 修了試験 20151220 実施分 問5
答えと解説を見る
正解：イ
覚える知識
2分探索木の大小関係
2分探索木は、どの節も左部分木の全値より大きく、右部分木の全値より小さい木である。
この問題で必要なこと
2分探索木は、各節で左部分木の値が節より小さく、右部分木の値が節より大きい。
ひっかけ
ヒープや完全2分木のように、親子間だけの大小関係を満たす木を選ばせる。
この知識の出題：本試験系 4 回・免除試験 8 回（公開問題での観測値）