本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成25年度 秋期 応用情報技術者試験問題と解説

問6

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

ア 枝の個数がnならば、節点の個数もnである。

イ 木の深さがnならば、葉の個数は2n-1である。

ウ 節点の個数がnならば、深さは log2nである。

エ 葉の個数がnならば、葉以外の節点の個数はn−1である。


正解


解説

葉以外の節点はすべて二つの子をもち、根から葉までの深さがすべて等しい木のことを完全2分木という。

ア 枝の個数がnならば、節点の個数はn+1である。

イ 木の深さがnならば、葉の個数は2n である。

ウ 節点の個数がnならば、深さは log2(n+1) −1である。
逆に深さがnならば、節点の個数は 2n+1−1である。

エ 正しい。

問5 目次 問7