データ構造 (全31問中9問目)
No.9
配列A[1]，A[2]，…，A[n]でA[1]を根とし，A[i]の左側の子をA[2i]，右側の子をA[2i＋1]とみなすことによって，2分木を表現する。このとき，配列を先頭から順に調べていくことは，2分木の探索のどれに当たるか。
出典：平成26年秋期 問4
- [この問題の出題歴]
- 応用情報技術者 H29秋期 問5
- ソフトウェア開発技術者 H17秋期 問10
- ソフトウェア開発技術者 H19春期 問10
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
エ
解説
この配列で表される2分木構造は次のようになります。
この木構造で配列の先頭から順に調べていくと、根から近い順に調べていくことになるため「幅優先探索」が適切です。「深さ優先探索」は、根からできるだけ分岐せずにいちばん深い葉の部分にまで到達してから、ひとつ前の節まで戻り他方の探索を行う方法です。