平成26年度秋期 応用情報技術者試験 午前 問4

正解：エ

AI解説

A[1]を根、A[i]の子をA[2i]とA[2i+1]とする配列表現は、完全2分木を「浅い階層から順に、同じ深さでは左から右へ」並べたものである(ヒープと同じ表現)。したがって配列を先頭から順に調べることは、根に近いレベルから順に同じ深さの節点を横に走査すること、すなわち幅優先探索に当たる。 ア: 行きがけ順(先行順)は「根→左部分木→右部分木」とたどる深さ優先探索であり、配列の添字順とは一致しない。 イ: 帰りがけ順(後行順)は「左部分木→右部分木→根」とたどる深さ優先探索である。 ウ: 通りがけ順(中間順)は「左部分木→根→右部分木」とたどる深さ優先探索で、2分探索木では昇順に取り出せる順序である。 エ: 正解。添字1,2,3,…の順はレベル(深さ)順・左から右の走査であり、幅優先探索に相当する。 💡 「A[2i]とA[2i+1]が子」はヒープの配列表現と同じで、添字順=レベル順と覚える。深さ優先3種(先行・中間・後行)は根を訪れるタイミングで区別する。