問題プレビューID: 0f328c0c応用情報技術者試験 2014年(平成26年度)秋期 午前

問 4
応用情報技術者試験 2014年(平成26年度)秋期 午前

配列 A[1]A[1],A[2]A[2],⋯\cdots,A[n]A[n] で,A[1]A[1] を根とし,A[i]A[i] の左側の子を A[2i]A[2i],右側の子を A[2i+1]A[2i+1] とみなすことによって,2 分木を表現する。このとき,配列を先頭から順に調べていくことは,2 分木の探索のどれに当たるか。

解説

正解は「エ」です。

A[i]A[i] の左の子を A[2i]A[2i],右の子を A[2i+1]A[2i+1] とする表現では,配列の添字は木の深さの浅い順(同じ深さでは左から順)に並びます。したがって配列を先頭から順に調べることは,根に近い頂点から順に,同じ深さの頂点をすべて調べてから次の深さへ進む探索になります。これは幅優先探索です。

  • ア・イ・ウ: 行きがけ順・帰りがけ順・通りがけ順はいずれも深さ優先探索であり,部分木を深くたどってから戻るため,配列の添字順とは一致しません。

よって正解は「エ」です。

関連問題

本文が同じ・似ている問題を表示しています