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

正解

エ. 幅優先探索

正答率 41.8%（366人中 153人が正解）

問題の解説

この表現では、根が A[1]、その子が A[2] と A[3]、さらにその子が A[4]〜A[7] というように、根に近い節点ほど小さい添字が付く。配列を先頭から順に調べると、根に近い節点から深さごとに左から右へ調べることになり、これは幅優先探索（レベル順の探索）に当たる。

選択肢ごとの解説

• ア行きがけ順は、節点を調べてから左の部分木、右の部分木へ進む深さ優先探索である。A[1] の次に A[2]、A[4] と深く進むので、配列の順と一致しない。
• イ帰りがけ順は、左右の部分木を調べ終えてから節点を調べる深さ優先探索で、根は最後になる。根が先頭になる配列の順とは一致しない。
• ウ通りがけ順は、左の部分木、節点、右の部分木の順に調べる深さ優先探索で、根は途中になる。根が先頭になる配列の順とは一致しない。
• エ正しい。根に近い節点から深さごとに左から右へ調べるので、添字の小さい順に調べることと一致する。