応用情報技術者試験 応用情報技術者試験 平成30年度秋期 午前 問6: 葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまで

正解

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

正答率 67.3%（1,228人中 826人が正解）

問題の解説

葉以外の節点が全て二つの子をもち、全ての葉の深さが等しい木は、深さを とすると葉が 個、節点が全部で 個になる。したがって葉以外の節点は 個で、葉の個数 に対して常に 個である。

選択肢ごとの解説

• ア枝の個数は、根を除く全ての節点に親へつながる枝が 1 本ずつあるので、節点の個数より 1 少ない。枝が 本なら節点は 個である。
• イ深さ の木の葉は 個である。深さ 1 の木は根と二つの葉からなり、葉は 2 個なので にならない。
• ウ節点が 個なら深さは である。節点 7 個の木の深さは 2 だが、 は 2 にならない。
• エ正しい。葉が 個なら、葉以外の節点は 個になる。