問題プレビューID: 4fd48642応用情報技術者試験 2017年(平成29年度)秋期 午前

問 5
応用情報技術者試験 2017年(平成29年度)秋期 午前

配列 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] とする添字付けでは,添字の小さい順に並べると,根,根の子,孫というように,階層(深さ)の浅いノードから順に並びます。したがって配列を先頭から順に調べることは,同じ深さのノードを左から順にたどる幅優先探索に相当します。

  • ア: 行きがけ順は,根を調べた後に左部分木,右部分木の順に深くたどる探索で,配列の順とは一致しません。
  • イ: 帰りがけ順は,左右の部分木を調べた後に根を調べる探索で,配列の順とは一致しません。
  • ウ: 通りがけ順は,左部分木,根,右部分木の順に調べる探索で,2 分探索木の整列順とは一致しますが,この配列の順とは一致しません。
  • エ: 深さの浅い方から順に,同じ深さでは左から右へ調べる点が配列の添字順と一致するので,幅優先探索が正解です。

関連問題

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