【基本情報技術者試験平成17年秋期午前】問題・解説・解答

[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成17年秋期基本情報技術者午前問12

問12　　 ２分木

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

例

ア　 n ＝ k ( k ＋1)＋1　　　　　イ　 n ＝ 2 ^k ＋3

ウ　 n ＝ 2 ^k+1 －1　　　　　　　エ　 n ＝ ( k －1)( k ＋1)＋4

解説

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

よって、 n ＝ 2 ^k+1 －1　となる。