必ず受かる情報処理技術者試験

当サイトは、情報処理技術者試験に合格するためのWebサイトです。
ITパスポート試験,基本情報技術者,応用情報技術者,高度試験の過去問題と解答及び詳細な解説を掲載しています。
  1. トップページ
  2. 応用情報技術者
  3. 平成29年度秋季問題一覧
  4. 平成29年度秋季問題5-解答・解説-分析

平成29年度秋季問題

問題5

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

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

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

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

解答:エ

<解説>

  1. nを7とした場合の2分木の構造は次のようになる。
  2. したがって、A[1]→A[2]→A[3]→A[4]・・・という順序で検索することになるため幅優先探索となる。

    ※なお深さ優先探索の場合は次のようになる。