データ構造 (全29問中17問目)

No.17

節点の集合が{1,2,…,n}である木を表現するために,大きさnの整数型配列 A[1],A[2],…,A[n] を用意して,節点iの親の節点をA[i]に格納する。節点kが根の場合はA[k]=0とする。表に示す配列が表す木の葉の数は,幾つか。
10.gif/image-size:276×42
  • [この問題の出題歴]
  • 基本情報技術者 H22秋期 問6

分類

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

正解

解説

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

Pagetop