問題
10 個の節（ノード）から成る次の 2 分木の各節に、1 から 10 までの値を一意に対応するように割り振ったとき、節 a, b の値の組合せはどれになるか。ここで、各節に割り振る値は、左の子及びその子孫に割り振る値よりも大きく、右の子及びその子孫に割り振る値よりも小さくするものとする。
選択肢
- 1a＝6, b＝7
- 2a＝6, b＝8
- 3a＝7, b＝8
- 4a＝7, b＝9
正解
1. a＝6, b＝7
詳しい解説を見る解説を閉じる
解説
「左の子孫＜自分」「右の子孫＞自分」という条件は通常の 2 分探索木とは左右が逆で、節を右から左へ昇順に見ていく構造になる。根が 5 で左部分木（節 4 を含む）が 1〜5、右部分木（節 a を含む）が 6〜10 を持つ。右部分木の最左に位置する b が右部分木の最小値 6 ではなく、構造をたどると a＝6、b＝7 となる。よって「ア」が正しい。（出典: 平成28年度 春期 基本情報技術者試験 午前 問5）
一問一答
科目A 180問+科目B 60問