アルゴリズムとプログラミング
平成28年度 春期 基本情報技術者試験 午前 問5
10 個の節（ノード）から成る次の 2 分木の各節に，1 から 10 までの値を一意に対応するように割り振ったとき，節 a，b の値の組合せはどれになるか。ここで，各節に割り振る値は，左の子及びその子孫に割り振る値よりも大きく，右の子及びその子孫に割り振る値よりも小さくするものとする。
2 分木。根は 5。根の左の子は 4，右の子は a。4 は左右 2 つの子（どちらも葉・値なし）をもつ。a は右の子（値なし）のみをもつ。a の右の子は，左の子が b，右の子が値なしの節 X（X は右の子 Y をもち，Y は葉）。すなわち 5→(4, a)，4→(葉, 葉)，a→右(節 P)，P→(左 b, 右 Q)，Q→右(葉)。節の総数 10。
答えを選ぶ
出典：平成28年度 春期 基本情報技術者試験 午前 問5（問題文は IPA の公開問題。解説は当サイト作成）
解説に誤りを見つけたら、解説の誤りを報告してください。
答えと解説を見る
正解：ア
覚える知識
2分探索木の大小関係
2分探索木では、各節は左部分木の全ての値より大きく、右部分木の全ての値より小さい。
この問題で必要なこと
左の子孫より大きく右の子孫より小さい配置なので中間順(左→根→右)で1から10を割り振り、a、bの値を読み取る。
ひっかけ
根の位置や右部分木の個数を数え誤ると、a・bの値がずれる。
この知識の出題：本試験系 4 回・免除試験 8 回（公開問題での観測値）。頻出知識ランキング109位（全1,254件中）。