問題プレビューID: fdb07f61基本情報技術者試験 午前免除試験 2011年6月26日

問 5
基本情報技術者試験 午前免除試験 2011年6月26日

10 個の節(ノード)からなる次の 2 分木の各節に,1 から 10 までの値を一意に対応するように割り振ったとき,節 a, b の値の組合せはどれになるか。ここで,各節に割り振る値は,左の子及びその子孫に割り振る値より大きく,右の子及びその子孫に割り振る値より小さくする。

解説

正解は「ア」です。

条件「左の子およびその子孫の値 < 節の値 < 右の子およびその子孫の値」は 2 分探索木の性質であり,中間順巡回(左部分木 → 節 → 右部分木)でたどると値が小さい順に並びます。

この木を中間順巡回すると,

D, C, E, 4, 5, a, b, F, G, HD,\ C,\ E,\ 4,\ 5,\ a,\ b,\ F,\ G,\ H

の順になります。ここに 1 から 10 を小さい順に割り当てると,5 番目が aa,7 番目が bb なので,a=6a = 6,b=7b = 7 となります。

  • イ: b=8b = 8 としており,中間順の並びと一致しません。
  • ウ: a=7a = 7 としており,5 の直後の値と一致しません。
  • エ: いずれも中間順の並びと一致しません。

関連問題

本文が同じ・似ている問題を表示しています