アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20110626 実施分 問5
10個の節（ノード）からなる次の2分木の各節に，1から10までの値を一意に対応するように割り振ったとき，節 a，b の値の組合せはどれになるか。ここで，各節に割り振る値は，左の子及びその子孫に割り振る値より大きく，右の子及びその子孫に割り振る値より小さくする。
2分木（10節）。根=5。根の左の子=4，右の子=a。
4 の子は1節（無印）X のみ（左下）。X は左右に子を2つ（どちらも葉・無印）。
a の子は右下の1節（無印）Y のみ。Y の左の子=b（葉），右の子=Z（無印）。Z は右下に子を1つ（無印の葉）。
- ア a＝6，b＝7
- イ a＝6，b＝8
- ウ a＝7，b＝8
- エ a＝7，b＝9
出典：基本情報技術者試験 科目A免除 修了試験 20110626 実施分 問5
答えと解説を見る
正解：ア
覚える知識
2分探索木の大小関係
2分探索木の節の値は、左部分木の全節より大きく右部分木の全節より小さい。中間順で巡回すると昇順になる。
この問題で必要なこと
各節が左部分木より大きく右部分木より小さい条件から、中間順で1〜10を割り振る。左部分木(根5の左)は4節で1〜4、根=5、右部分木は5節で6〜10。aの左部分木は空でbが最小になるので、aの右部分木内で順に数えるとa=6、bは7となる。
ひっかけ
左右の子の大小や部分木の節数の数え間違いを誘う。
この知識の出題：本試験系 4 回・免除試験 8 回（公開問題での観測値）