平成23年度特別 応用情報技術者試験 午前 問6
葉以外の節点はすべて二つの子をもち，根から葉までの深さがすべて等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，深さとは根から葉に至るまでの枝の個数を表す。
- ア 枝の個数がnならば，葉を含む節点の個数もnである。
- イ 木の深さがnならば，葉の個数は2ⁿ⁻¹である。
- ウ 節点の個数がnならば，深さはlog₂nである。
- エ 葉の個数がnならば，葉以外の節点の個数はn−1である。
解答・解説を見る
正解：エ
AI解説
葉以外の全ての節点が2つの子を持ち、根から葉までの深さが全て等しい木(完全二分木)では、葉の個数をnとすると、内部節点(葉以外の節点)の個数はn-1個になる。これは二分木の性質から導かれる。 ア: 枝の個数がnのとき節点の個数はn+1であり(木構造では節点数=枝数+1)、葉を含む節点数がnになるわけではないため誤り。 イ: 深さnの完全二分木の葉の個数は2ⁿ(2のn乗)であり、2ⁿ⁻¹ではないため誤り。 ウ: 節点の個数がnのとき、深さは単純にlog₂nとは一致しない関係式になるため誤り。 エ: 葉の個数がnのとき、葉以外の節点(内部節点)の個数はn-1になるという性質の説明であり正解。 💡 二分木の基本性質「内部節点数=葉の数-1」(全ての内部節点が2つの子を持つ木の場合)は頻出。深さ1(根+葉2つ)なら葉2・内部節点1で確認できる。
出典：平成23年度 特別 応用情報技術者試験 午前 問6 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。