基本情報技術者試験 - 令和5年6月修了 - 問5

葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。

ア	枝の個数がnならば，節点の個数もnである。
イ	木の深さがnならば，葉の個数は2^n-1である。
ウ	節点の個数がnならば，木の深さはlog₂nである。
エ	葉の個数がnならば，葉以外の節点の個数はn-1である。

◀ 問4　|　▲ 令和5年6月修了問題一覧　|　問6 ▶

答え：エ
分野：テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › データ構造

同一問題 ：〔令7修6問5〕〔令6修6問5〕〔令2修1問7〕〔平21修6問5〕

解説：
すべての葉以外の節点が二つの子を持ち，根から葉までの深さが等しい木を「完全二分木」と呼びます。この木では，葉の個数がnであれば，葉以外の節点（内部節点）の個数はn-1になるという性質があります。これは二分木の枝の数と節点数の関係から導かれるものです。

「ア」は枝の個数と節点の個数の関係を誤って述べており，実際には節点数は枝の数より1多くなります。

「イ」は深さnのときの葉の個数を誤った式で表しており，正しくは2のn乗になります。

「ウ」も同様に，節点数と深さの関係式が誤っています。