平成20年秋期試験午前問題 問10

節点の集合が{1,2,…,n}である木を表現するために,大きさnの整数型配列 A[1],A[2],…,A[n] を用意して,節点iの親の節点をA[i]に格納する。節点kが根の場合はA[k]=0とする。表に示す配列が表す木の葉の数は,幾つか。
10.gif

  • 1
  • 3
  • 5
  • 7
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
木構造は要素同士の階層的な関係(親子関係)を表現するためのデータ構造で、木構造で使われる各部分の名前は以下の通りです。
10_1.gif
表が示す木構造を考えるには、根から順番に考えて木構造を実際に描いてみるのが解答への近道です。
  1. まずA[1]=0の根を親に持つ子は、2と3の二つです。
  2. 次に3の節点は、4と5の二つの子をもっています。
  3. さらに5の節点は、6,7,8の3つの子をもっています。
この配列で示される木構造を描くと、以下のようになります。
10_2.gif
したがって葉の数は5つです。

この問題の出題歴


Pagetop