問題プレビューID: 79380dc5基本情報技術者試験 2016年(平成28年度)春期 午前

問 5
基本情報技術者試験 2016年(平成28年度)春期 午前

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

解説

この 2 分木は,各節の値が「左の子及びその子孫 < 節 < 右の子及びその子孫」を満たす二分探索木です。したがって,中間順(左の子孫 → 節 → 右の子孫)にたどると値が昇順に並びます。根の 5 の左部分木は 4 を含む 4 節で,いずれも 5 より小さいので {1, 2, 3, 4},右部分木は残りの {6, 7, 8, 9, 10} です。右部分木を中間順にたどると a → b → … の順になるので,a=6, b=7 となります。 したがって,正解は「ア」です。

関連問題

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