データ構造 (全53問中33問目)
No.33
節点1，2，…，n をもつ木を表現するために，大きさnの整数型配列 A[1]，A[2]，…，A[n] を用意して，節点iの親の節点をA[i]に格納する。節点kが根の場合はA[k]＝0とする。表に示す配列が表す木の葉の数は，幾つか。
出典：平成22年秋期 問6
- 1
- 3
- 5
- 7
- [出題歴]
- ソフトウェア開発技術者 H20秋期 問10
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
ウ
解説
木構造は要素同士の階層的な関係(親子関係)を表現するためのデータ構造で、木構造で使われる各部分の名前は以下の通りです。
表が示す木構造を考えるには、根から順番に考えて木構造を実際に描いてみるのが解答への近道です。
したがって葉の数は、5つということになります。
- まずA[1]=0の根を親に持つ子は、2と3の二つです。
- 次に3の節点は、4と5の二つの子をもっています。
- さらに5の節点は、6，7，8の3つの子をもっています。