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

正解

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

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

問題の解説

最適適合は、要求量以上で最小の空き領域を探す方式である。空き領域の大きさをキーとする 2 分探索木なら、木をたどって要求量以上で最小のものを、平均 の手間で見つけられる。ほかの構造では、空き領域の個数に比例する探索が必要になり、割当て時の平均処理時間が長くなる。

選択肢ごとの解説

• アアドレス順に並ぶため、大きさでは探せない。最小の適合領域を見つけるには、全ての空き領域を調べる必要がある。
• イ小さい順なので最初に見つかる適合領域が最適だが、先頭から順にたどるため、探索時間が空き領域の数に比例する。
• ウ正しい。大きさをキーにした探索木なら、要求量以上で最小の領域を木をたどるだけで見つけられ、平均処理時間が最も短い。
• エビットマップは各単位が使用中か空きかを表すだけで、領域の大きさを直接は分からない。空きの連続を順に調べるため時間が掛かる。