平成29年度 秋期 応用情報技術者 問5

正解 エ

配列の添字順は、根から深さ（レベル）ごとに左から右へ並ぶので、先頭から調べると幅優先探索になります。

A[1]が根で、A[i]の子がA[2i]とA[2i+1]なので、深さ1はA[2]とA[3]、深さ2はA[4]〜A[7]です。深さkの節点は、添字が2^kから2^(k+1)−1の範囲に左から順に並びます。したがって、A[1]、A[2]、A[3]、A[4]…と先頭から調べると、根に近い階層から順に、同じ階層の節点を左から右へたどることになります。これは幅優先探索の順序です。

ア：行きがけ順は、節点を調べてから左の部分木、右の部分木へ進む深さ優先探索です。順序はA[1]、A[2]、A[4]…となり、A[3]より先にA[4]を調べます。

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

ウ：通りがけ順は、左の部分木、節点、右の部分木の順に調べる深さ優先探索です。最初に調べるのは最も左下の節点で、A[1]ではありません。

出典：平成29年度 秋期 応用情報技術者試験 問5