トップ過去問一覧応用情報技術者 平成25年・秋 > 問6
問6

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

○正解
×不正解

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

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

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

葉の個数がnならば,葉以外の節点の個数はn-1である。

解説

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

枝の個数=葉以外の節点の数×2なので,

葉を含む節点の個数=n+1

になります。

 

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

木の深さ=根から葉までの枝の数なので,

葉の個数=2n

になります。

 

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

節点の個数=2深さ+1-1なので,

深さ=log2(n+1)-1

になります。

 

葉の個数がnならば,葉以外の節点の個数はn-1である。

正解です。

節点の個数=葉の個数×2-1なので,

葉以外の節点の個数=n-1

になります。

無料学習システムはこちら
→間違えた問題を繰り返し学習
→分野別学習
→模擬試験モード
デモサイト
無料ユーザ登録

問題文や解説文の内容の正確性については、できるかぎりチェックをしていますが、間違いがある可能性があります。 十分ご注意の上、参考までにご利用ください。