問題プレビューID: 6dc5cedd応用情報技術者試験 2019年(平成31年度)春期 午前

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

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

解説

正解は「ウ」です。

最適適合(best-fit)方式では,要求量以上の大きさをもつ空き領域のうち最小のものを探す必要があります。空き領域の「大きさ」をキーとする 2 分探索木で管理すれば,要求量以上で最小の領域を対数時間(O(log⁡n)O(\log n))で探索でき,平均処理時間が最も短くなります。

  • ア: アドレスをキーにしても,空き領域が大きさの順に並ぶとは限らず,最適適合の探索を効率化できません。
  • イ: 大きさ順の片方向連結リストは,目的の領域にたどり着くまで先頭から順にたどる必要があり,線形時間(O(n)O(n))がかかります。
  • エ: ビットマップはアドレスの使用状況を表すには適しますが,大きさで最小の空き領域を探すには線形探索が必要です。

関連問題

本文が同じ・似ている問題を表示しています