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

正解

エ. 幅優先探索

正答率 66.9%（598人中 400人が正解）

問題の解説

配列の添字の順は、根のA[1]、深さ1のA[2]とA[3]、深さ2のA[4]〜A[7]と、浅い階層から順に左から右へ並ぶ。配列を先頭から調べることは、根に近い節点から階層ごとに訪れることで、幅優先探索(レベル順)に当たる。深さ優先探索の三つの順序では、子の部分木を先にたどるので、添字の順にはならない。

選択肢ごとの解説

• ア行きがけ順は、根の次に左の部分木を端まで先にたどる。7個の節点なら添字は1、2、4、5、3、6、7の順になり、添字の昇順とは異なる。
• イ帰りがけ順は、左右の部分木をたどり終えてから根を調べる。根が最後になるので、先頭の根から始まる添字順とは合わない。
• ウ通りがけ順は、左の部分木、根、右の部分木の順に調べる。根が途中になるので、先頭の根から始まる添字順とは合わない。
• エ正しい。添字順は、根、深さ1の節点、深さ2の節点と、浅い階層から左から右へ並ぶので、幅優先探索の訪問順そのものである。