平成30年度 秋期 応用情報技術者試験 午前 問6

この木は全ての段が埋まった完全な2分木です。深さをdとすると，葉の個数は2^d，葉以外の節点の個数は2^d − 1，節点の総数は2^(d+1) − 1，枝の個数は節点数 − 1 です。

• ア: 枝の個数がnならば，節点の個数もnである
  誤り。木では根以外の各節点に親への枝が1本ずつあるため，節点の個数は枝の個数＋1になります。

• イ: 木の深さがnならば，葉の個数は2ⁿ⁻¹である
  誤り。深さnの完全な2分木の葉の個数は2ⁿです。例えば深さ1なら葉は2個です。

• ウ: 節点の個数がnならば，木の深さはlog₂nである
  誤り。深さdの木の節点数は 2^(d+1) − 1 なので，深さは log₂(n＋1) − 1 です。例えば節点3個なら深さ1ですが，log₂3は1になりません。

• エ: 葉の個数がnならば，葉以外の節点の個数はn−1である
  正しい。深さdのとき葉は2^d個，葉以外の節点は 1＋2＋…＋2^(d−1) = 2^d − 1 個です。したがって葉がn個なら葉以外の節点はn−1個になります。例えば深さ2では葉4個，葉以外の節点3個です。

答え

エ: 葉の個数がnならば，葉以外の節点の個数はn−1である