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


キーワード
・木

キーワードの解説
  • 木(木構造)
    グラフの一種で、グラフの木を使ったデータ構造が木構造である。
    通常は親を持たない根と、親と子を持つ節点、子を持たない葉とそれを結ぶ枝からなる。

    木の特徴としては、任意の2点結ぶ経路が一つである。

もっと、「木構造」について調べてみよう。

戻る 一覧へ 次へ