データ構造(全33問中25問目)

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

出典:平成19年春期 問10

  • 行きがけ順(先行順)深さ優先探索
  • 帰りがけ順(後行順)深さ優先探索
  • 通りがけ順(中間順)深さ優先探索
  • 幅優先探索
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
設問の配列で表された2分木は次のような構造になります。
10.gif
この木構造で配列の先頭から順に調べていくと、根から近い順に調べていくことになるため「幅優先探索」が適切です。「深さ優先探索」は、根からできるだけ分岐せずにいちばん深い葉の部分にまで到達してから、ひとつ前の節まで戻り他方の探索を行う方法です。
10_1.gif

この問題の出題歴


Pagetop