基本情報技術者平成15年春期 午前問12

問12

10個の節(ノード)からなる次の2分木の各節に,1から10までの値を一意に対応するように割り振ったとき,節a,bの値の組合せはどれになるか。ここで,各節に割り振る値は,左の子及びその子孫に割り振る値より大きく,右の子及びその子孫に割り振る値より小さくする。
12.png/image-size:216×161
  • a=6,b=7
  • a=6,b=8
  • a=7,b=8
  • a=7,b=9
  • [出題歴]
  • 基本情報技術者 H28春期 問5

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

問題文中の「各節に割り振る値は,左の子及びその子孫に割り振る値より大きく,右の子及びその子孫に割り振る値より小さくする」というのは、「左の子の値<親の値<右の子の値」になるように割り振ればよいということです。つまり、左端が最小値、右端が最大値です。
12a.png/image-size:300×240
節aの値は、5より大きく、上の図の赤の部分内の3つの値より小さくなります。
節bの値は、上の図の赤の部分内の3つの値より小さくなるので、節bの値は7です。
したがって、節aの値は6です。
© 2010- 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop