令和3年度 春期 応用情報技術者 問6

正解 エ

配列の添字順は、根から深さごとに左から右へ並ぶので、配列を先頭から調べることは幅優先探索に当たります。

A[1]が根で、その子がA[2]とA[3]、さらにその子がA[4]〜A[7]です。深さdの節点は、添字2^dから2^(d+1)−1に、左から右の順で並びます。そのため、配列を先頭から順に調べると、根、深さ1の節点、深さ2の節点と、浅い階層から1段ずつ左から右へたどります。これは幅優先探索の順序です。

ア：行きがけ順は、節点、左部分木、右部分木の順にたどる深さ優先探索です。根の次にA[2]、その次はA[4]となり、A[3]は後回しです。

イ：帰りがけ順は、左部分木、右部分木、節点の順にたどる深さ優先探索です。根のA[1]が最後になります。

ウ：通りがけ順は、左部分木、節点、右部分木の順にたどる深さ優先探索です。左端の葉から始まり、A[1]は先頭になりません。

出典：令和3年度 春期 応用情報技術者試験 問6