アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 200912 実施分 問5
すべての葉が同じ深さをもち，葉以外のすべての節点が二つの子をもつ 2 分木に関して，節点数と深さの関係を表す式はどれか。ここで，n は節点数，k は根から葉までの深さを表す。例に示す 2 分木の深さ k は 2 である。
例: 完全 2 分木。根（1 個）から子 2 個，さらにそれぞれ子 2 個の計 4 個の葉。葉の深さは k = 2（図中に「k = 2」と注記）。節点総数 7。
- ア n = 2^k + 3
- イ n = 2^(k+1) − 1
- ウ n = (k−1)(k+1) + 4
- エ n = k(k+1) + 1
出典：基本情報技術者試験 科目A免除 修了試験 200912 実施分 問5
答えと解説を見る
正解：イ
覚える知識
完全2分木の節点数と深さの関係
深さkの完全2分木の節点数は2^(k+1)−1である。
この問題で必要なこと
深さkの完全2分木は、各深さに2^i個の節点があり、i=0からkまでの総和でn=2^(k+1)−1となる。例のk=2ではn=7。
ひっかけ
2^kは葉の数にすぎない。2^k+3は式として一見もっともらしいが、k=2で7にならない。
この知識の出題：本試験系 0 回・免除試験 1 回（公開問題での観測値）