問題プレビューID: e966ce0f基本情報技術者試験 午前免除試験 2020年1月26日

問 7
基本情報技術者試験 午前免除試験 2020年1月26日

葉以外の節点は全て二つの子をもち,根から葉までの深さが全て等しい木を考える。この木に関する記述のうち,適切なものはどれか。ここで,木の深さとは根から葉に至るまでの枝の個数を表す。また,節点には根及び葉も含まれる。

解説

正解は「エ」である。

葉以外の節点が全て二つの子をもつ木(完全二分木)では,各節点は「親 1 個に対して子が 2 個」という関係にある。このため,葉の個数を nn とすると,葉以外の節点(内部節点)の個数は n−1n-1 となる。

  • ア: 木では一般に,節点の個数は枝の個数より 1 多い(節点 == 枝 +1+1)。枝の個数が nn なら節点は n+1n+1 であり,誤りである。
  • イ: 深さを根から葉までの枝の個数とすると,深さ nn の完全二分木の葉の個数は 2n2^n である。2n−12^{n-1} は誤りである。
  • ウ: 節点の個数が nn のとき,木の深さが log⁡2n\log_2 n になるとは限らず,誤りである。
  • エ: 完全二分木では葉の個数は内部節点の個数より 1 多い。したがって,葉の個数が nn ならば葉以外の節点の個数は n−1n-1 であり,正しい。

関連問題

本文が同じ・似ている問題を表示しています