応用情報技術者試験 応用情報技術者試験 令和3年度春期 午前 問6: 配列 A[1]，A[2]，…，A[n] で，A[1] を根とし，A[i] の左側の子を A[2i]，右側の子を A[2i+1] とみなすことによって，2 分木を

正解

エ. 幅優先探索

正答率 41.3%（361人中 149人が正解）

問題の解説

この配列表現では、A[1]が根（深さ1）、A[2]・A[3]が深さ2、A[4]〜A[7]が深さ3…と、添字の順に同じ深さのノードが左から並ぶ。したがって配列を先頭から順に調べると、根から1階層ずつ同じ深さのノードを左から右へたどることになり、これは木を浅い階層から順に横方向にたどる幅優先探索に相当する。よって正解はエである。

選択肢ごとの解説

• ア行きがけ順（先行順）は「ノード→左部分木→右部分木」の順に深く潜りながらたどる深さ優先探索であり、配列を先頭から順に読む順序とは一致しないため誤り。
• イ帰りがけ順（後行順）は「左部分木→右部分木→ノード」の順にたどる深さ優先探索であり、配列の添字順とは一致しないため誤り。
• ウ通りがけ順（中間順）は「左部分木→ノード→右部分木」の順にたどる深さ優先探索であり、配列の添字順とは一致しないため誤り。
• エ配列の添字順は根から深さの浅い順に、各階層を左から右へたどる並びであり、これは幅優先探索の訪問順そのものなので正しい。