基本情報技術者平成22年秋期 午前問6

問6

節点1,2,…,n をもつ木を表現するために,大きさnの整数型配列 A[1],A[2],…,A[n] を用意して,節点iの親の節点をA[i]に格納する。節点kが根の場合はA[k]=0とする。表に示す配列が表す木の葉の数は,幾つか。
06.gif/image-size:265×41
  • 1
  • 3
  • 5
  • 7
  • [出題歴]
  • ソフトウェア開発技術者 H20秋期 問10

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

木構造は要素同士の階層的な関係(親子関係)を表現するためのデータ構造で、木構造で使われる各部分の名前は以下の通りです。
06_1.gif/image-size:300×200
表が示す木構造を考えるには、根から順番に考えて木構造を実際に描いてみるのが解答への近道です。
  1. まずA[1]=0の根を親に持つ子は、2と3の二つです。
  2. 次に3の節点は、4と5の二つの子をもっています。
  3. さらに5の節点は、6,7,8の3つの子をもっています。
この配列で示される木構造を描くと、以下のようになります。
06_2.gif/image-size:250×190
したがって葉の数は、5つということになります。
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop