HOME»基本情報技術者平成15年春期»午前問12
基本情報技術者平成15年春期 午前問12
問12
10個の節(ノード)からなる次の2分木の各節に,1から10までの値を一意に対応するように割り振ったとき,節a,bの値の組合せはどれになるか。ここで,各節に割り振る値は,左の子及びその子孫に割り振る値より大きく,右の子及びその子孫に割り振る値より小さくする。
- a=6,b=7
- a=6,b=8
- a=7,b=8
- a=7,b=9
- [出題歴]
- 基本情報技術者 H28春期 問5
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
ア
解説
問題文中の「各節に割り振る値は,左の子及びその子孫に割り振る値より大きく,右の子及びその子孫に割り振る値より小さくする」というのは、「左の子の値<親の値<右の子の値」になるように割り振ればよいということです。つまり、左端が最小値、右端が最大値です。節aの値は、5より大きく、上の図の赤の部分内の3つの値より小さくなります。
節bの値は、上の図の赤の部分内の3つの値より小さくなるので、節bの値は7です。
したがって、節aの値は6です。
節bの値は、上の図の赤の部分内の3つの値より小さくなるので、節bの値は7です。
したがって、節aの値は6です。