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

正解

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

正答率 42.2%（277人中 117人が正解）

問題の解説

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

選択肢ごとの解説

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