平成22年度 秋期 午前 問6

✓ これが正解ウ5

解説

配列の値に一度も現れない番号が葉で、5個です。

この配列は、節点の番号を添字にして、そこに親の番号を入れる形で木を表しています。ある節点が子をもつということは、その節点の番号がどこかの要素の値として現れているということです。裏を返せば、配列の値に一度も現れない番号の節点は子をもたない、つまり葉です。そこで値の並びを見て、現れる番号の種類を数えます。現れるのは0のほかに1と3と5の3種類で、0は根を表す印なので節点の番号ではありません。節点は全部で8個あり、子をもつのは3個ですから、残りの5個が葉になります。判定の軸は、数える対象を親の側にするか子をもたない側にするかと、根を表す0を節点の番号と取り違えないことです。

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

• ア1：親の欄が0になっている節点、つまり根だけを数えた値です。根は2つの子をもつ節点なので、子をもたない節点の個数としては数えられません。
• イ3：配列の値として現れる番号の種類を数えた値で、これは子をもつ側の節点の個数です。求めたいのは残りの側なので、節点の総数からこの個数を引く必要があります。
• エ7：節点の総数から根の1個だけを取り除いた値です。根のほかにも子をもつ節点が2個あるので、その分まで取り除かないと子をもたない節点の個数にはなりません。