令和3年度春期 応用情報技術者試験 午前 問6
配列A[1]，A[2]，…，A[n]で，A[1]を根とし，A[i]の左側の子をA[2i]，右側の子をA[2i＋1]とみなすことによって，2分木を表現する。このとき，配列を先頭から順に調べていくことは，2分木の探索のどれに当たるか。
- ア 行きがけ順（先行順）深さ優先探索
- イ 帰りがけ順（後行順）深さ優先探索
- ウ 通りがけ順（中間順）深さ優先探索
- エ 幅優先探索
解答・解説を見る
正解：エ
AI解説
配列でA[2i]、A[2i+1]を子とする完全二分木表現において、配列を添字の昇順(先頭から順)にたどることは、根から始めて各階層を上から下へ、同じ階層内では左から右へ順にたどることに相当する。これは深さ優先探索ではなく、階層(レベル)ごとに探索する幅優先探索に当たる。 ア: 行きがけ順(先行順)深さ優先探索は、根→左部分木→右部分木の順に再帰的にたどる方式であり、配列の添字を単純に昇順にたどる操作とは一致しない。 イ: 帰りがけ順(後行順)深さ優先探索は、左部分木→右部分木→根の順にたどる方式であり、同様に配列の添字順とは一致しない。 ウ: 通りがけ順(中間順)深さ優先探索は、左部分木→根→右部分木の順にたどる方式であり、配列の添字順とは一致しない。 エ: 正しい。配列を先頭(添字の小さい方)から順にたどることは、木を階層ごとに上から下、左から右へたどる幅優先探索に相当する。 💡 配列表現の二分木では、添字iの子が2i, 2i+1になることから、添字順=階層順(幅優先)になるという対応関係を覚えておくと、木の走査方式を問う問題に素早く対応できる。
出典：令和3年度 春期 応用情報技術者試験 午前 問6 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。