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