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

解説

正解は4です。 葉以外のすべての節点が子を2つもち、葉の深さがすべて等しい木（完全二分木）の性質を問う問題です。 深さdの完全二分木では、葉の数は2^d個、節点の総数は2^(d+1)－1個になります。 【選択肢別解説】 1：× 木では、根以外の節点がそれぞれ1本の枝で親とつながります。 そのため枝の個数がnならば、節点の個数はnではなくn＋1です。 2：× 深さとは根から葉までの枝の数なので、深さ0は根だけで葉は1個です。 深さが1増えるごとに葉は2倍になるので、深さnの葉の個数は2^(n-1)ではなく2^nです。 3：× 節点の個数nは2^(d+1)－1と表されるので、深さdはlog_2(n＋1)－1です。 例えば節点3個（深さ1）ではlog_2 3は約1.58となり、深さと一致しません。 4：○ 深さdのとき葉は2^d個、葉以外の節点は1＋2＋…＋2^(d-1)＝2^d－1個です。 したがって葉の個数がnならば、葉以外の節点の個数はn－1です。 例えば深さ2では、葉が4個、葉以外が3個になります。 【ポイント】 完全二分木では「葉以外の節点数＝葉の数－1」が成り立ちます。 小さな例（深さ1や2）を描いて確かめると、選択肢の真偽を素早く判定できます。