修了試験 2011-06-26実施分 基本情報技術者試験 問5

解説

正解は1です。 この問題は、2分探索木の性質を使って節の値を決める問題です。 条件より、各節の値は左の子孫より大きく、右の子孫より小さくなります。 図では、根が5で、左の子が4です。 4の下には左の子が1つあり、さらにその下に子が2つあります。 根の右の子がaで、aには右の子（ここでは節cと呼びます）だけがあります。 cの左の子がbで、cの右の子（節d）があり、dにはさらに右の子（節e）があります。 【計算】 根5の左側には4を含む4つの節があるので、1〜4が入ります。 根5の右側にはa，c，b，d，eの5つの節があるので、6〜10が入ります。 aには左の子がないので、aは右側の5つの中で最小の6です。 cの部分木ではb＜c＜d＜eとなるので、b＝7，c＝8，d＝9，e＝10です。 したがって、a＝6，b＝7です。 【選択肢別解説】 1：○ aは左の子をもたないので右側の最小値6、bはcの部分木の最小値7になります。 2：× a＝6は正しいですが、bは部分木の中で最も小さい値なので8ではなく7です。 3：× aには左の子がないので、aが7だと6を入れる場所がなくなります。 正しくはa＝6です。 4：× aは6、bは7が正しいです。 a＝7，b＝9では、6と8を条件どおりに配置できません。 【ポイント】 2分探索木を中間順（左、節、右の順）にたどると、値が小さい順に並びます。 この性質を使うと、図の節に左から順に番号を振るだけで値が決まります。