応用情報技術者試験 2017年度 = 平成29年度・秋期 午前 問5

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

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

解答



解説

 横型探索とも呼ばれる幅優先探索(breadth-first search)は、レベルの低い点から始めて、左側から右側へ、それが終わると次のレベルへとたどっていく方法です。
 n が7であれば、探索は、以下のようになります。

     → 1 →
      /  \
  → 2    3 →
   / \   / \ 
 4  56  7 →



BohYoh.comトップページへ