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

最適適合（best-fit）アルゴリズムは、要求されたサイズ以上の空き領域の中で、最も小さい領域を割り当てる方式です。
この処理を高速に行うためには、空き領域を大きさ（サイズ）を基準にして検索できるデータ構造が必要です。

各選択肢の解説

• ア：空き領域のアドレスをキーとする2分探索木
  アドレスをキーにしているため、サイズによる検索には適さず、最適な空き領域を見つけるためには全ノードを探索する必要があります。
• イ：空き領域の大きさが小さい順の片方向連結リスト
  サイズの小さい順に並んでいるため、先頭から順に調べて最初に条件を満たした空き領域が最適となります。しかし、線形探索となるため、平均処理時間は空き領域の数 $n$ に対して $O(n)$ となります。
• ウ：空き領域の大きさをキーとする2分探索木
  サイズをキーにした2分探索木を用いることで、条件を満たす最小の空き領域を平均 $O(\log n)$ の計算量で高速に検索できます。したがって、平均処理時間が最も短くなります。
• エ：アドレスに対応したビットマップ
  ビットマップを順次走査して連続した空き領域のサイズを確認する必要があるため、検索に多大な時間がかかります。