午前問12
10個の節(ノード)からなる次の2分木の各節に、1から10までの値を一意に対応するように割り振ったとき、節a、bの値の組合せはどれになるか。ここで、各節に割り振る値は、左の子及びその子孫に割り振る値より大きく、右の子及びその子孫に割り振る値より小さくする。
| a＝6、b＝7 | |
| a＝6、b＝8 | |
| a＝7、b＝8 | |
| a＝7、b＝9 |
『情報処理過去問.com』からiPhoneアプリがリリースされました！！
正解
- ア
解説
2分探索木は「左(子)＜中(親)＜右(子)」の制約を持つ木構造です。
1から10までの値を一意になるように空白に入れていきます。
4,5は既に入っているので残りの値は1,2,3,6,7,8,9,10です。
左端が最小値、右端が最大値となるので、左下の3つには1,2,3,が入ります。
残りの値は6,7,8,9,10です。
aは5より大きく残りの値の最小値なので6が入ります。
残りの値は7,8,9,10です。
bは6より大きく残りの値の最小値なので7が入ります。
残りの値は8,9,10です。
8,9,10を左から順に入れると設問の2分木全て「左(子)＜中(親)＜右(子)」となっています。
よってa＝6、b＝7が正解となります。
1から10までの値を一意になるように空白に入れていきます。
4,5は既に入っているので残りの値は1,2,3,6,7,8,9,10です。
左端が最小値、右端が最大値となるので、左下の3つには1,2,3,が入ります。
残りの値は6,7,8,9,10です。
aは5より大きく残りの値の最小値なので6が入ります。
残りの値は7,8,9,10です。
bは6より大きく残りの値の最小値なので7が入ります。
残りの値は8,9,10です。
8,9,10を左から順に入れると設問の2分木全て「左(子)＜中(親)＜右(子)」となっています。
よってa＝6、b＝7が正解となります。