2008年(平成20年) 秋期 ソフトウェア開発技術者 午前 問10

節点の集合が{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

答え　ウ

【解説】
表を示す配列

i 1 2 3 4 5 6 7 8
A[i ] 0 1 1 3 3 5 5 5
から、1が根で、2と3の親が1、4と5の親が3、6と7と8の親が5であるので、これを図にすると

になる。
これで、葉を数えると、葉は子のない要素なので2、4、6、7、8の5個(ウ)である。

【キーワード】
・木

【キーワードの解説】

戻る 一覧へ 次へ