応用情報技術者試験 平成29年秋期試験午前問題問5 平成30年秋期試験午前問題問6 と木構造まとめ

木構造は､階層構造を持つデータで広く用いられる他、データの探索や整列などの用途にも使われるデータ構造です
図1

図2

完全2分木
図3

図4

完全2分木とは、上から順に左詰めで要素を埋めていって､その深さの要素が埋め尽くされるまでは次の深さに行かない…といった構造の2分木のこと。

2分木の走査
2分木に含まれるデータを対象として探索を行う場合､その木構造をたどり節点をもれなく巡回する必要が出てきます｡このように､順に調べていくことを走査と言います。2分木の走査方法には大きく分けて2つの方法があります。
図5

応用情報技術者試験
平成29年秋期試験午前問題　問5

配列A[1]，A[2]，…，A[n]で，A[1]を根とし，A[i]の左側の子をA[2i]，右側の子をA[2i＋1]とみなすことによって，2分木を表現する。このとき，配列を先頭から順に調べていくことは，2分木の探索のどれに当たるか。

(ア)行きがけ順(先行順)深さ優先探索
(イ)帰りがけ順(後行順)深さ優先探索
(ウ)通りがけ順(中間順)深さ優先探索
(エ)幅優先探索

図5より
正解　エ

この問題の出題歴
* 応用情報技術者 H26秋期 問4
* ソフトウェア開発技術者 H17秋期 問10
* ソフトウェア開発技術者 H19春期 問10
応用情報技術者試験
平成30年秋期試験午前問題　問6

葉以外の節点はすべて二つの子をもち，根から葉までの深さがすべて等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。

(ア)枝の個数がnならば，葉を含む節点の個数もnである。
(イ)木の深さがnならば，葉の個数は2n-1である。
(ウ)節点の個数がnならば，深さはlog2nである。
(エ)葉の個数がnならば，葉以外の節点の個数はn－1である。

正解　エ
図4のような図を思い浮かべればよい。

この問題の出題歴
* 応用情報技術者 H23特別 問6
* 応用情報技術者 H25秋期 問6
* ソフトウェア開発技術者 H17春期 問9
* ソフトウェア開発技術者 H20春期 問9