アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20120122 実施分 問5
節点 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 |
- ア 1
- イ 3
- ウ 5
- エ 7
出典：基本情報技術者試験 科目A免除 修了試験 20120122 実施分 問5
答えと解説を見る
正解：ウ
覚える知識
親配列表現された木の葉の数
親配列表現では、どの節点の親としても現れない節点が葉である。
この問題で必要なこと
親配列に一度も現れない節点が葉。親として現れるのは0,1,3,5なので、葉は2,4,6,7,8の5個。
ひっかけ
根(0)や親として現れる節点を葉に含める数え間違い。
この知識の出題：本試験系 1 回・免除試験 2 回（公開問題での観測値）