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

問題6

ポケットスタディ 基本情報午後・要点整理―即効!7つの知識 (情報処理技術者試験)

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

枝の個数がnならば、葉を含む節点の個数もnである。
木の深さが n ならば,葉の個数は 2n-1 である。
節点の個数がnならば、深さはlog2nである。
葉の個数がnならば、葉以外の節点の個数はn-1である。

解答・解説を見る

解答:エ

完全二分木(葉以外の節点はすべて二つの子をもち、根から葉までの深さがすべて等しい木)は、次の図のようになる。

× 枝の個数がnならば、葉を含む節点の個数はn+1である。
× 木の深さが n ならば,葉の個数は 2n である。
× 節点の個数が n ならば,深さは (log2(n+1))-1 である。
葉の個数がnならば、葉以外の節点の個数はn-1である。
前の問題 次の問題

Copyrithg naruha