平成30年度秋期 応用情報技術者試験 午前 問6
葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。
- ア 枝の個数がnならば，節点の個数もnである。
- イ 木の深さがnならば，葉の個数は2^(n-1)である。
- ウ 節点の個数がnならば，木の深さはlog2 nである。
- エ 葉の個数がnならば，葉以外の節点の個数はn-1である。
解答・解説を見る
正解：エ
AI解説
この木は全ての葉の深さが等しい完全な2分木である。2分木では「葉の個数=葉以外の節点(内部節点)の個数+1」という関係が常に成り立つ。葉がn個なら内部節点はn−1個であり、エが正しい。深さd、葉2^d個、内部節点2^d−1個、全節点2^(d+1)−1個という関係から確認できる。 ア: 木では「節点の個数=枝の個数+1」である。全ての節点は根を除きちょうど1本の枝で親とつながるため、枝がnなら節点はn+1であり誤りである。 イ: 深さがnのとき葉の個数は2^nである。2^(n-1)は深さn−1の場合の葉の数であり誤りである。 ウ: 節点の個数がnのとき、n=2^(d+1)−1より深さd=log2(n+1)−1である。log2 nちょうどにはならないため誤りである。 エ: 正しい。葉がn=2^d個のとき、内部節点は1+2+…+2^(d-1)=2^d−1=n−1個である。 💡 深さ2で具体的に描いて検算するのが確実(節点7、枝6、葉4、内部節点3)。「葉=内部節点+1」「節点=枝+1」の二つの関係は2分木問題の頻出公式である。
出典：平成30年度 秋期 応用情報技術者試験 午前 問6 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。