基本情報技術者試験 基本情報技術者試験 平成28年度 春期 午前 午前 問5: 10個の節(ノード)から成る2分木の各節に1から10までの値を一意に対応するように割り振ったとき，節 a, b の値の組合せはどれか。ここで，各節に割り振る値は

正解

ア. a=6, b=7

正答率 58.3%（1,497人中 873人が正解）

問題の解説

中順序(in-order)走査で昇順になる二分探索木の構造。根=5なので左部分木に1-4、右部分木にa(=6以降)を割り振る。aは右子の根で残りの5個から最小=6を選び子孫の最小、bはaの左子で7。

選択肢ごとの解説

• アa=6, b=7 で各節の左<自分<右子孫の関係が成立し正しい二分探索木になります。
• イa=6,b=8は b=8 がaの左子で b<aを満たさず誤り。
• ウa=7,b=8は b<aを満たすが、ノード値の連続性で残りノードがa右子側で組めず矛盾。
• エa=7,b=9は baで条件に反します。