基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

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

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


ア  n k ( k +1)+1      イ  n = 2 k +3

ウ  n = 2 k +1 −1        エ  n = ( k −1)( k +1)+4


解答←クリックすると正解が表示されます

解説

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

  • n =0……………1
  • n =1……………1+2
  • n =2……………1+2+4
  • n =3……………1+2+4+8
よって、 n = 2 k +1 −1 となる。

[←前の問題] [次の問題→] [問題一覧表] [分野別] [キーワード索引] [基本情報技術者試験TOP ]