平成29年度秋期 応用情報技術者試験 午前 問5
配列 A[1]，A[2]，…，A[n] で，A[1] を根とし，A[i] の左側の子を A[2i]，右側の子を A[2i＋1] とみなすことによって，2 分木を表現する。このとき，配列を先頭から順に調べていくことは，2 分木の探索のどれに当たるか。
- ア 行きがけ順（先行順）深さ優先探索
- イ 帰りがけ順（後行順）深さ優先探索
- ウ 通りがけ順（中間順）深さ優先探索
- エ 幅優先探索
解答・解説を見る
正解：エ
AI解説
A[1]を根、A[i]の子をA[2i]とA[2i+1]とする配列表現では、A[1]がレベル1、A[2]〜A[3]がレベル2、A[4]〜A[7]がレベル3というように、配列の添字順がそのまま木のレベル(深さ)順・同一レベル内では左から右の順になっている。したがって配列を先頭から順に調べることは、浅い節から順に探索する幅優先探索に当たる。 ア: 行きがけ順(先行順)は根→左部分木→右部分木の順にたどる深さ優先探索であり、配列順とは一致しない。 イ: 帰りがけ順(後行順)は左部分木→右部分木→根の順にたどる深さ優先探索である。 ウ: 通りがけ順(中間順)は左部分木→根→右部分木の順にたどる深さ優先探索で、2分探索木から昇順にデータを取り出すときに使う。 エ: 正解。配列の先頭からの走査はレベル順の走査であり、幅優先探索に相当する。 💡 「A[i]の子がA[2i],A[2i+1]」はヒープで使われる完全2分木の配列表現。この形式では添字順=レベル順=幅優先、と覚えてしまうとよい。
出典：平成29年度 秋期 応用情報技術者試験 午前 問5 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。