アルゴリズムとプログラミング
平成22年度 秋期 基本情報技術者試験 午前 問6
節点 1，2，…，n をもつ木を表現するために，大きさ n の整数型配列 A[1]，A[2]，…，A[n] を用意して，節点 i の親の番号を A[i] に格納する。節点 k が根の場合は A[k]=0 とする。表に示す配列が表す木の葉の数は，幾つか。
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| A[i] | 0 | 1 | 1 | 3 | 3 | 5 | 5 | 5 |
答えを選ぶ
出典：平成22年度 秋期 基本情報技術者試験 午前 問6（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：ウ
覚える知識
親配列表現された木の葉の数
木で子を持たない節点が葉であり、親配列表現では配列値として一度も現れない節点番号が葉に当たる。
この問題で必要なこと
A[i]が節点iの親を表す配列で、どの節点の親にもなっていない節点が葉である。親として現れるのは1,3,5なので、葉は2,4,6,7,8の5個。
ひっかけ
根(A[k]=0)を数えたり、親として現れる節点数(3)を葉数と取り違える。
この知識の出題：本試験系 1 回・免除試験 2 回（公開問題での観測値）