平成22年秋期試験問題 午前問6

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
節点1,2,…,n をもつ木を表現するために,大きさnの整数型配列 A[1],A[2],…,A[n] を用意して,節点iの親の節点をA[i]に格納する。節点kが根の場合はA[k]=0とする。表に示す配列が表す木の葉の数は,幾つか。
06.gif

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

この問題の出題歴


Pagetop