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

問 7
基本情報技術者試験 午前免除試験 2020年6月14日

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

解説

正解は「イ」である。

2 分探索木は,任意のノードについて「左部分木の全ての値 < ノードの値 < 右部分木の全ての値」を満たす木である。

  • ア: 根 1 の左の子が 2 となっており,左部分木の値が根より大きいので不適切である。
  • イ: 根 4 に対し左部分木 {2, 1, 3} は全て 4 未満,右部分木 {8, 6, 9, 5, 7} は全て 4 より大きい。ノード 2 は左 1 < 2 < 右 3,ノード 8 は左部分木 {6, 5, 7} < 8 < 右 9,ノード 6 は左 5 < 6 < 右 7 を満たし,全てのノードで条件を満たす。
  • ウ: 根 7 の右部分木に値 3 が含まれており,右部分木の値が根より小さいので不適切である。
  • エ: 根 9 の右部分木に値 8 以下の値が含まれており,条件を満たさない。

関連問題

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