令和5年度春期 応用情報技術者試験 午前 問5

正解：ウ

AI解説

best-fitは要求サイズ以上で最小の空き領域を選ぶ方式であり、大きさ順に高速な探索・挿入・削除を行うには「大きさをキーとした2分探索木」が平均処理時間の面で最も適している。 ア: アドレスをキーにした2分探索木は空き領域の位置管理には向くが、大きさ順の検索を必要とするbest-fitの探索には不適切である。 イ: 大きさ順の片方向連結リストは探索・挿入がO(n)の線形時間を要し、木構造に比べて処理時間が長くなる。 ウ: 正解。大きさをキーとする2分探索木なら、要求量以上で最小の領域をO(log n)程度で探索でき、挿入・削除も効率的に行える。 エ: アドレスに対応したビットマップはアドレス単位の使用状況管理には向くが、大きさ順の検索には不向きで効率が悪い。 💡 best-fit(最小の適合領域)・first-fit(最初に見つかった適合領域)・worst-fit(最大の領域)という3方式と、それぞれに適したデータ構造(木構造・リストなど)をセットで覚える。