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

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

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

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

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

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

解説：
すべての葉以外の節点が2つの子を持ち，根から葉までの深さが等しい木（完全二分木）の性質を問う問題です。このような木では，葉の数をnとすると，葉以外の節点（内部節点）の数は必ずn-1になるという性質があります。これは二分木の分岐構造から導かれる一般的な法則で，「エ」が正解です。

「ア」は枝と節点の関係が誤り（木の節点数は枝数+1），「イ」は深さnのときの葉の数は2のn乗になるはずで誤り，「ウ」は節点数と深さの関係式が逆であり誤りです。二分木の基本的な数学的性質を暗記しているとすぐに判断できる問題です。