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

問題本文

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

選択肢

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

正解

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

解説

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

選択肢ごとの解説

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