問題プレビューID: a4589dcb応用情報技術者試験 2023年(令和5年度)春期 午前

問 5
応用情報技術者試験 2023年(令和5年度)春期 午前

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

解説

正解は「ウ」です。

最適適合(best-fit)アルゴリズムは,「要求量以上の大きさをもつ空き領域のうち最小のもの」を選ぶ方式です。この選択を効率よく行うには,空き領域を「大きさ」で検索できる構造が必要です。空き領域の大きさをキーとする 2 分探索木を用いれば,要求量以上の最小の領域を平均 O(log⁡n)O(\log n) で見つけられ,割当て時の平均処理時間を最も短くできます。

  • ア: アドレスをキーにしても大きさによる検索はできないため,最適適合には不向きです。
  • イ: 大きさ順の片方向連結リストでは,小さい方から順にたどって要求量以上になる最初の領域を探す必要があり,平均 O(n)O(n) の時間がかかります。
  • エ: ビットマップはアドレス単位の使用状況しか表せず,大きさによる検索には適しません。

関連問題

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