修了試験 2020-01-26実施分 基本情報技術者試験 問7

解説

正解は4です。 葉以外の節点がすべて二つの子をもち、葉の深さがそろった木（完全二分木）の性質を問う問題です。 深さnの完全二分木では、葉は2^n個、節点は2^(n+1)－1個です。 【選択肢別解説】 1：× 木では、根以外の各節点に親へ向かう枝が1本ずつあります。 枝の個数がnなら、節点の個数はn＋1です。 2：× 深さ0（根だけ）で葉は1個、深さ1で2個と、深さが1増えるごとに葉は2倍になります。 深さnなら葉は2^(n-1)ではなく2^n個です。 3：× 節点の個数がnのとき、n＝2^(深さ＋1)－1が成り立ちます。 深さはlog_2 nではなく、log_2 (n＋1)－1です。 4：○ 深さdでは葉が2^d個、葉以外の節点が1＋2＋…＋2^(d-1)＝2^d－1個です。 葉の個数をnとすると、葉以外の節点はn－1個になります。 【ポイント】 完全二分木では「葉以外の節点数＝葉の数－1」が成り立ちます。 具体例として深さ2（葉4個、内部節点3個）で確かめると確実です。