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

正解

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

正答率 64.1%（574人中 368人が正解）

問題の解説

最適適合（best-fit）は「要求量以上で最も小さい空き領域」を高速に見つけられるデータ構造を選ぶ問題である。探したいのは大きさを基準とした最小の領域なので、空き領域の大きさをキーにした 2 分探索木に格納しておけば、根から要求量と比較しながら降りていくことで O(log n) で目的の領域を見つけられる。これが平均処理時間の最も短い構造であり、ウが正解である。

選択肢ごとの解説

• アアドレスをキーにした 2 分探索木では大きさで整列されていないため、要求量に合う最小の空き領域を探すには全体を走査する必要があり遅い。
• イ大きさ順の連結リストは整列されているが、リストは先頭から順にたどるしかなく探索が O(n) になるため、2 分探索木より平均処理時間が長い。
• ウ大きさをキーにした 2 分探索木なら、要求量と比較しながら木を降りるだけで条件を満たす最小領域を O(log n) で見つけられ、平均処理時間が最も短い。
• エビットマップは各領域の使用・未使用を表すだけで大きさの順序情報を持たず、適合する最小領域を探すにはビット列全体の走査が必要で遅い。