| 基本情報技術者試験 |
2010年度 ＝ 平成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
|
ウ
木構造において、親をもたない節点が根で、子をもたない節点が葉です。
与えられた表から、以下のことが分かります。
- 根は節点1。
- 節点２と３の親は、節点１。
- 節点４と５の親は、節点３。
- 節点６と７と８親は、節点５。
そのため、木構造は下図のようになります。
子をもたない葉は、黄色で示した節点2、4、6、7、8の5個です。
