問題プレビューID: fad31d32応用情報技術者試験 2021年(令和3年度)春期 午前

問 6
応用情報技術者試験 2021年(令和3年度)春期 午前

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

解説

正解は「エ」です。

配列の添字を 2 分木の親子関係に対応させると,配列を先頭から順に調べることは,根から順に同じ深さの節を左から右へたどることに相当します。これは幅優先探索(レベル順探索)に当たります。

  • ア: 行きがけ順(先行順)は,節を訪れてから左部分木,右部分木の順にたどる深さ優先探索です。
  • イ: 帰りがけ順(後行順)は,左右の部分木をたどった後に節を訪れる深さ優先探索です。
  • ウ: 通りがけ順(中間順)は,左部分木,節,右部分木の順にたどる深さ優先探索です。

関連問題

本文が同じ・似ている問題を表示しています