基本情報技術者平成28年春期 午前問5

午前問5

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

分類

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

正解

解説

問題文中の「各節に割り振る値は,左の子及びその子孫に割り振る値より大きく,右の子及びその子孫に割り振る値より小さくする」というのは、「左の子の値<親の値<右の子の値」になるように割り振ればよいということです。つまり、左端が最小値、右端が最大値です。

左部分木の空白になっている3つの節には、それぞれ4より小さい値が入るので「3,2,1」が入ることになります。残る数字は「6,7,8,9,10」の5つですが、問題の大小関係を満たすためには節aの値に、5より大きく、残る5つの数字の中で最も小さい値が入る必要があるため節a=6が適切です。また節bの値は、「左の子の値<親の値<右の子の値」という条件から考えると、残る4つの数字の中で最も小さい7が収まることになります。

したがってa=6,b=7が正解です。
05a.gif/image-size:300×240
© 2010-2019 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop