平成25年度 秋期 午前 問6

✓ これが正解エ葉の個数が n ならば，葉以外の節点の個数は n−1 である。

解説

葉以外が全て2子なら、葉以外の個数は葉より1少なくなります。

設問は、葉以外の節点が全て二つの子をもち、根から葉までの深さが等しい木について、適切な記述を選ばせています。見る軸は一つで、枝の本数を二通りに数えて突き合わせることです。まず、葉以外の節点は必ず子を二つもつので、枝の本数は葉以外の個数の 2 倍になります。次に、根を除くどの節点にも自分へ入ってくる枝がちょうど 1 本あるので、枝の本数は節点の総数から 1 を引いた値にもなります。節点の総数は葉と葉以外の合計ですから、この二つを等号で結ぶと、葉以外の個数の 2 倍が葉と葉以外の合計から 1 を引いた値に等しくなります。整理すると葉以外の個数は葉の個数から 1 を引いた値になり、葉の個数が n ならば葉以外の節点の個数は n から 1 を引いた値である、という記述が当てはまります。深さ 1 では葉が 2 で葉以外が 1、深さ 2 では葉が 4 で葉以外が 3、深さ 3 では葉が 8 で葉以外が 7 と、実際に描いても同じ関係になります。

ほかの選択肢はなぜ違うのか

• ア枝の個数が n ならば，節点の個数も n…：枝と節点の個数が等しいとしていますが、根には入ってくる枝がないため、枝は節点より必ず一つ少なくなります。深さ 1 の木では枝が 2 本に対して節点は 3 個で、すでに食い違います。
• イ木の深さが n ならば，葉の個数は 2ⁿ…：深さ n のときの葉を 2 の n−1 乗としていますが、深さ 1 の木を描くと葉は 2 個あり、この式では 1 個になってしまいます。正しくは 2 の n 乗で、指数が一つ小さい形です。
• ウ節点の個数が n ならば，深さは log…：節点の総数の 2 を底とする対数を深さとしていますが、深さ 2 の木は節点が 7 個で、対数の値は約 2.807 となり整数にすらなりません。総数に 1 を足してから対数を取り、さらに 1 を引く必要があります。