応用情報技術者試験 |
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 → 5→6 → 7 →