平成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個(ウ)である。


キーワード
・木

キーワードの解説

戻る 一覧へ 次へ