応用情報技術者試験 応用情報技術者試験 令和5年度春期 午前 問5: 要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合（best-fit）アルゴリズ

問題本文

要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合（best-fit）アルゴリズムを用いる場合，空き領域を管理するためのデータ構造として，メモリ割当て時の平均処理時間が最も短いものはどれか。

選択肢

• ア.空き領域のアドレスをキーとする 2 分探索木
• イ.空き領域の大きさが小さい順の片方向連結リスト
• ウ.空き領域の大きさをキーとする 2 分探索木
• エ.アドレスに対応したビットマップ

正解

ウ. 空き領域の大きさをキーとする 2 分探索木

解説

最適適合（best-fit）では「要求量以上で、かつ最小の空き領域」を高速に見つける必要があります。空き領域の大きさをキーとする 2 分探索木にしておけば、要求量以上で最も小さい大きさを木の探索で O(log n) でたどり着けるため、平均処理時間が最短になります。一方、大きさ順の連結リストでは先頭から順にたどるため O(n)、アドレスをキーにした探索木やビットマップでは「大きさで最小を探す」用途に向かず効率が悪くなります。

選択肢ごとの解説

• ア.アドレスをキーにした 2 分探索木はアドレス順に整列されているだけで、要求量以上で最小の「大きさ」を直接探せない。結局すべての領域の大きさを調べる必要があり遅いため誤り。
• イ.大きさが小さい順に並んだ連結リストは、先頭から要求量以上になる最初のノードを順にたどるしかなく平均 O(n) かかるため、2 分探索木より遅い。
• ウ.大きさをキーとする 2 分探索木は、要求量以上で最小の大きさをもつ領域を O(log n) で探索できるため、割当て時の平均処理時間が最も短く正しい。
• エ.ビットマップは各領域の使用・未使用を 1 ビットで表すもので、要求量以上で最小の連続空き領域を探すには全体を走査する必要があり、best-fit には不向きで遅いため誤り。