「応用情報技術者試験/平成30年秋期午前問6」

問題

出典:応用情報技術者令和平成30年秋期午前問6

葉以外の節点はすべて二つの子をもち、
根から葉までの深さがすべて等しい木を考える。

この木に関する記述のうち、適切なものはどれか。
ここで、木の深さとは根から葉に至るまでの枝の個数を表す。
また、節点には根及び葉も含まれる。

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

解説

実際に全部の選択肢に値を入れてみればよい。

根とは一番上の丸
枝とは棒のこと。
葉とは一番下の丸
節点とは全ての丸

ア:枝の個数が6ならば、葉を含む節点の個数も6である。
→違う。枝が6なら、葉は4である。

イ:木の深さが2ならば、葉の個数は(2^2-1)=2である。
→違う。葉の個数は4である。

ウ:節点の個数が7ならば、深さは(log2,7)=2乗して7になる値=約2.8である。
→小数点って時点で違う。あと節点てのは全部の丸の数のこと。

エ:葉の個数が4ならば、葉以外の節点の個数は3である。
→正しい

解答

正解:エ

アドセンス
改行

テックキャンプ