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

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

2 分探索木として適切なものはどれか。ここで,1〜9 の数字は,各ノード(節)の値を表す。

解説

正解は「イ」です。

2 分探索木では,すべてのノードについて「左の子およびその子孫の値 < 親の値 < 右の子およびその子孫の値」が成り立ちます。

「イ」は,根 4 の左部分木に {1,2,3}\{1, 2, 3\},右部分木に {5,6,7,8,9}\{5, 6, 7, 8, 9\} が配置され,各ノードでも同じ関係が成り立っています(2 の左 1・右 3,8 の左 6・右 9,6 の左 5・右 7)。よって 2 分探索木になっています。

  • ア: 根 1 の左の子が 2 であり,左部分木の値が親より大きいので 2 分探索木ではありません。
  • ウ: 根 7 の右部分木に 3 が含まれており,右部分木の値は親より大きい必要があるため誤りです。
  • エ: 根 9 の右部分木に 8 が含まれており,右部分木の値は親より大きい必要があるため誤りです。

関連問題

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