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

No.21

配列A[1],A[2],…,A[n]でA[1]を根とし,A[i]の左側の子をA[2i],右側の子をA[2i+1]とみなすことによって,2分木を表現する。このとき,配列を先頭から順に調べて行くことは,2分木の探索のどれに当たるか。
  • 行きがけ順(先行順)深さ優先探索
  • 帰りがけ順(後行順)深さ優先探索
  • 通りがけ順(中間順)深さ優先探索
  • 幅優先探索
  • [この問題の出題歴]
  • 応用情報技術者 H26秋期 問4
  • 応用情報技術者 H29秋期 問5
  • ソフトウェア開発技術者 H17秋期 問10

分類

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

正解

解説

設問の配列で表された2分木は次のような構造になります。
10.gif/image-size:229×107
この木構造で配列の先頭から順に調べていくと、根から近い順に調べていくことになるため「幅優先探索」が適切です。「深さ優先探索」は、根からできるだけ分岐せずにいちばん深い葉の部分にまで到達してから、ひとつ前の節まで戻り他方の探索を行う方法です。
10_1.gif/image-size:222×133
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop