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

問題本文

10個の節(ノード)から成る2分木の各節に1から10までの値を一意に対応するように割り振ったとき，節 a, b の値の組合せはどれか。ここで，各節に割り振る値は，左の子及びその子孫に割り振る値よりも大きく，右の子及びその子孫に割り振る値よりも小さくするものとする。

選択肢

• ア.a=6, b=7
• イ.a=6, b=8
• ウ.a=7, b=8
• エ.a=7, b=9

正解

ア. a=6, b=7

解説

中順序(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で条件に反します。