問題
要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合（best-fit）アルゴリズムを用いた場合に、空き領域を管理するためのデータ構造として、メモリ割当て時の平均処理時間が最も短いものはどれか。
選択肢
- 1空き領域のアドレスをキーとする 2 分探索木
- 2空き領域の大きさが小さい順の片方向連結リスト
- 3空き領域の大きさをキーとする 2 分探索木
- 4アドレスに対応したビットマップ
正解
3. 空き領域の大きさをキーとする 2 分探索木
詳しい解説を見る解説を閉じる
解説
best-fit では「要求量以上で最小の空き領域」を毎回探す必要がある。空き領域の大きさをキーとした 2 分探索木にしておけば、要求量以上で最小の領域を平均 O(log n) で効率よく探索できる。よってウが正解。大きさ順の連結リストは線形探索で O(n)、アドレスをキーとする木やビットマップでは大きさ順の検索に向かない。（出典: 令和5年度 春期 応用情報技術者試験 午前 問5）
一問一答
全400問を繰り返し学習