問題プレビューID: 203332c5基本情報技術者試験 午前免除試験 2019年7月28日

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

2 分探索木になっている 2 分木はどれか。

解説

正解は「イ」です。

2 分探索木とは,任意の節において,左部分木のすべての節の値がその節の値より小さく,右部分木のすべての節の値がその節の値より大きい 2 分木です。各選択肢の構造を確認します。

  • ア: 根 16 の左の子 15 に対し,その右の子が 14 である。右の子は親より大きくなければならないが 14 < 15 なので不適切。
  • イ: 根 17 に対し,左部分木 {14,10,16}\{14, 10, 16\} はすべて 17 より小さく,右部分木 {19,18}\{19, 18\} はすべて 17 より大きい。節 14 は左の子 10 < 14,右の子 16 > 14。節 19 は左の子 18 < 19。すべての条件を満たし適切。
  • ウ: 根 18 の左の子 16 に対し,その右の子が 14 である。右の子は親より大きくなければならないが 14 < 16 なので不適切。
  • エ: 根 20 の右の子が 19 である。右の子は親より大きくなければならないが 19 < 20 なので不適切。

関連問題

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