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

解説

正解は4です。 葉以外のすべての節点が子を2つもち、葉の深さがすべて等しい木（完全二分木）の性質を問う問題です。 深さdの完全二分木では、葉の数は2のd乗、節点の総数は2の(d＋1)乗－1になります。 【選択肢別解説】 1：× 根以外の各節点には、親とつながる枝がちょうど1本ずつあります。 そのため枝の個数がnなら、節点の個数は根を加えたn＋1です。 2：× 深さが1増えるごとに葉の数は2倍になります。 深さ0では葉は1個なので、深さnの葉の個数は2の(n－1)乗ではなく2のn乗です。 3：× 深さdの節点数は2の(d＋1)乗－1です。 したがって節点数がnなら深さはlog₂(n＋1)－1であり、log₂nではありません。 4：○ 葉の個数をnとすると、深さdで2のd乗＝nです。 葉以外の節点は1＋2＋…＋2の(d－1)乗＝2のd乗－1＝n－1個になります。 【ポイント】 各節点が0個か2個の子をもつ二分木では、常に「葉の数＝内部節点の数＋1」が成り立ちます。 具体的に深さ1（葉2、内部1）や深さ2（葉4、内部3）で確かめると判断が速くなります。