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

当サイトは、情報処理技術者試験に合格するためのWebサイトです。
ITパスポート試験，基本情報技術者,応用情報技術者,高度試験の過去問題と解答及び詳細な解説を掲載しています。
  1. トップページ
  2. 基本情報技術者
  3. 平成17年度秋季問題一覧
  4. 平成17年度秋季問題12-解答・解説-分析

平成17年度秋季問題

問題12

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

ア n ＝ k (k＋1)＋1
イ n ＝ 2k＋3
ウ n ＝ 2k+1－1
エ n ＝ (k－1)(k＋1)＋4

すべての葉が同じ深さをもち，葉以外のすべての節点が二つの子をもつ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 ＝０……………１
  • n ＝１……………３（１＋２）
  • n ＝２……………７（１＋２＋４）
  • n ＝３……………１５（１＋２＋４＋８）

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