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

解説

最適適合（best-fit）では「要求量以上の大きさをもつ空き領域のうち最小のもの」を探す必要があります。空き領域の大きさをキーとする2分探索木で管理すれば，この条件を満たす領域を木の高さ，すなわち領域数 n に対して log n に比例する時間で探索できます。線形探索が必要な連結リストやビットマップ，大きさの順序が反映されないアドレスキーの木より平均処理時間が短くなります。

選択肢ごとの解説

• ア誤り。アドレスをキーとする2分探索木では大きさの順序が反映されないため，条件を満たす最小の領域を見つけるには全ての空き領域を走査する必要があります。
• イ誤り。大きさが小さい順の片方向連結リストは先頭から順に走査するので，平均で領域数に比例した時間がかかります。
• ウ正しい。大きさをキーとする2分探索木なら，要求量以上で最小の空き領域を木の高さ（log n）に比例する時間で探索できます。
• エ誤り。ビットマップは各ブロックの使用・未使用を1ビットで表すだけなので，最小の空き領域を求めるにはビットマップ全体を走査する必要があります。