平成20年秋期試験問題 午前問10
問10解説へ
節点の集合が{1，2，…，n}である木を表現するために，大きさnの整数型配列 A[1]，A[2]，…，A[n] を用意して，節点iの親の節点をA[i]に格納する。節点kが根の場合はA[k]＝0とする。表に示す配列が表す木の葉の数は，幾つか。
- 1
- 3
- 5
- 7
広告
解説
木構造は要素同士の階層的な関係(親子関係)を表現するためのデータ構造で、木構造で使われる各部分の名前は以下の通りです。
表が示す木構造を考えるには、根から順番に考えて木構造を実際に描いてみるのが解答への近道です。
したがって葉の数は5つです。
- まずA[1]=0の根を親に持つ子は、2と3の二つです。
- 次に3の節点は、4と5の二つの子をもっています。
- さらに5の節点は、6，7，8の3つの子をもっています。
広告