応用情報技術者 2023年 春期 午前2 問05
問題文
要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合(best-fit)アルゴリズムを用いる場合、空き領域を管理するためのデータ構造として、メモリ割当て時の平均処理時間が最も短いものはどれか。
選択肢
ア：空き領域のアドレスをキーとする2分探索木
イ：空き領域の大きさが小さい順の片方向連結リスト
ウ：空き領域の大きさをキーとする2分探索木（正解）
エ：アドレスに対応したビットマップ
要求に応じて可変量のメモリを割り当てる最適適合アルゴリズム【午前2 解説】
要点まとめ
- 結論：最適適合アルゴリズムでは空き領域の大きさをキーにした2分探索木が平均処理時間を最短にします。
- 根拠：最適適合は要求サイズ以上の最小空き領域を探すため、大きさ順に高速検索できるデータ構造が有効です。
- 差がつくポイント：単純なリストやアドレス順管理では探索に時間がかかり、ビットマップはサイズ検索に不向きです。
正解の理由
最適適合アルゴリズムは「要求サイズ以上で最小の空き領域」を割り当てるため、空き領域の大きさをキーにした2分探索木を使うと、要求サイズに最も近い空き領域を高速に探索できます。2分探索木は平均の探索時間で済み、連結リストのように全探索する必要がありません。アドレス順の管理やビットマップはサイズ検索に適しておらず、処理時間が長くなります。
よくある誤解
空き領域のアドレス順管理が高速と思いがちですが、最適適合ではサイズ順の検索が重要です。ビットマップは空き・使用の判別に便利ですが、サイズ検索には不向きです。
解法ステップ
- 最適適合アルゴリズムの目的を確認する（要求サイズ以上の最小空き領域を探す）。
- 空き領域の管理方法を考える（サイズ順かアドレス順か）。
- サイズ順で高速に探索できるデータ構造を選ぶ（2分探索木が適切）。
- 各選択肢の特徴を比較し、サイズをキーにした2分探索木を選択する。
選択肢別の誤答解説
- ア: 空き領域のアドレスをキーにした2分探索木は、サイズ検索に不向きで最適適合の探索効率が悪い。
- イ: 大きさ順の片方向連結リストはサイズ順だが探索が線形で遅い。
- ウ: 空き領域の大きさをキーとする2分探索木はサイズ検索が高速で最適適合に最適。
- エ: ビットマップは空き・使用の判別に便利だが、サイズ検索には適さず処理時間が長くなる。
補足コラム
最適適合アルゴリズムはメモリの断片化を抑える効果がありますが、探索に時間がかかることが課題です。2分探索木以外にもAVL木や赤黒木などの自己平衡2分探索木を用いることで、さらに安定した高速検索が可能です。
FAQ
Q: なぜアドレス順の管理ではなくサイズ順が重要ですか？
A: 最適適合は要求サイズ以上の最小空き領域を探すため、サイズ順に管理しないと効率的な探索ができません。
A: 最適適合は要求サイズ以上の最小空き領域を探すため、サイズ順に管理しないと効率的な探索ができません。
Q: ビットマップはどんな場合に有効ですか？
A: 固定サイズのブロック管理や空き・使用状態の判別に有効ですが、可変サイズの空き領域検索には不向きです。
A: 固定サイズのブロック管理や空き・使用状態の判別に有効ですが、可変サイズの空き領域検索には不向きです。
関連キーワード: メモリ管理、最適適合、2分探索木、空き領域管理、メモリ割り当て
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！