必ず受かる情報処理技術者試験

問題12

ポケットスタディ 基本情報午後・要点整理―即効!7つの知識 (情報処理技術者試験)

すべての葉が同じ深さをもち,葉以外のすべての節点が二つの子をもつ2分木に関して,節点数と深さの関係を表す式はどれか。ここで, n は節点数, k は根から葉までの深さを表す。例に示す2分木の深さ k は2である。

n = k (k+1)+1
n = 2k+3
n = 2k+1-1
n = (k-1)(k+1)+4

解答・解説を見る

解答:ウ

k は根から葉までの深さ k と節点数 n は、次のようになる。

  • n =0……………1
  • n =1……………3(1+2)
  • n =2……………7(1+2+4)
  • n =3……………15(1+2+4+8)

よって、 n = 2k+1-1 となる。

前の問題 次の問題

Copyrithg naruha