問5応用情報技術者 平成31年度 春期

解説

正解は3。最適適合は「要求量以上で最小の空き領域」を探す方式なので、空き領域を大きさで探索できる構造がよい。大きさをキーにした2分探索木なら、要求量と比べながら木を根から下へたどるだけで該当領域に届き、平均の探索時間は空き領域数nに対しておよそlog nに比例する。

• 1は、アドレスをキーにした木で、大きさの条件では探索できず、結局ほぼ全部を調べることになる。
• 2は、大きさ順の連結リストなので先頭から順にたどる必要があり、平均でnに比例する時間がかかる。
• 4は、ビットマップでは空き領域の大きさを調べるために連続する空きビットを走査する必要があり、時間がかかる。

根拠：データ構造と探索の計算量（2分探索木は平均O(log n)、連結リストはO(n)）。