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

この条件は2分探索木の性質そのもので、木を左から順に（左部分木→自分→右部分木の順に）たどると値が1から10まで昇順に並ぶ。根が5なので左部分木の4個の節に1〜4、右部分木の5個の節に6〜10が入る。右部分木はaに左の子が無く右の子をもつ形なので、その順序ではaが最初に来て6、次にaの右の子の左の子であるbが7となる。

選択肢ごとの解説

• ア正解。右部分木を順にたどるとa、b、…の順になり、6から順に割り振られてa＝6、b＝7となる。
• イaは正しいがbが合わない。bはaの直後にたどられる節なので7になる。
• ウaには左の子が無く、根の直後にたどられるので右部分木の最小値6が入る。7ではない。
• エaもbも1ずつ大きく、走査順の起点を取り違えている。

同じ分野の他の問題

• 次のプログラム中の a と b に入れる正しい答えの組合せを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。…2026年度 公開問題 科目B 問4
• 次のプログラム中の a と b に入れる正しい答えの組合せを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。…2025年度 公開問題 科目B 問3
• 図の木構造は2分探索木である。a〜gの値の大小関係として，適切なものはどれか。ここで，a〜gの値は重複しないものとする。2025年度 公開問題 科目A 問3
• 次のプログラム中の に入れる正しい答えを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。 図1に示すグラフの…2024年度 公開問題 科目B 問3
• 双方向のポインタをもつリスト構造のデータを表に示す。この表において新たな社員Gを社員Aと社員Kの間に追加する。追加後の表…2023年度 公開問題 科目A 問2