修了試験 2025-06-08実施分 基本情報技術者試験 問5

解説

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