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

正解 エ

葉以外の節点が全て2つの子をもつ木では、葉の個数がnのとき、葉以外の節点の個数は必ずn−1になります。

この木は、深さがそろった完全な二分木（完全二分木）です。深さをdとすると、葉の個数は2^d、葉以外の節点の個数は1+2+…+2^(d−1)=2^d−1です。葉の個数をnとおくと、葉以外の節点はn−1個になります。たとえば深さ2では、葉は4個、葉以外の節点は根と2つの子で3個です。また、節点の個数は2^(d+1)−1、枝の個数は節点の個数−1です。

ア：木では根以外の各節点に親への枝が1本ずつあるので、枝の個数は節点の個数−1です。枝がn本なら節点はn+1個です。

イ：深さが1増えるごとに葉は2倍になるので、深さnの葉の個数は2^nです。深さ1で葉が2個であることから確かめられます。

ウ：節点の個数nは2^(d+1)−1なので、深さdはlog₂(n+1)−1です。log₂nにはなりません。

出典：平成30年度 秋期 応用情報技術者試験 問6