葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。
平成25年度 秋期 応用情報技術者 問6
テクノロジ系
正解と解説
正解 エ
全ての内部節点が子を2つもち、葉の深さがそろった木では、葉の個数がnなら葉以外の節点はn−1個です。
深さをdとすると、葉の個数は2^d、葉以外の節点の個数は1+2+…+2^(d−1)=2^d−1です。葉の個数をnとおくと、葉以外の節点はn−1個になります。たとえば深さ2では、葉が4個、葉以外の節点が3個です。節点の総数は2^(d+1)−1で、7個になります。枝の個数は6本です。
ア：根以外の各節点は親への枝を1本ずつもちます。そのため、枝の個数がnなら節点の個数はn+1です。
イ：深さが1増えるごとに葉の個数は2倍になります。深さnなら葉の個数は2^nです。
ウ：節点の個数nは2^(d+1)−1と表せます。そのため、深さはlog₂(n+1)−1です。
出典：平成25年度 秋期 応用情報技術者試験 問6
全年度から出題。10問で実力を判定します。登録不要。
出典：平成25年度 秋期 応用情報技術者試験 問6（独立行政法人情報処理推進機構）
解説と用語ページは生成 AI が書き、別の生成 AI が確かめています。作り方