平成31年春期試験問題 午前問5
問5解説へ
要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合(best-fit)アルゴリズムを用いる場合，空き領域を管理するためのデータ構造として，メモリ割当て時の平均処理時間が最も短いものはどれか。
- 空き領域のアドレスをキーとする2分探索木
- 空き領域の大きさが小さい順の片方向連結リスト
- 空き領域の大きさをキーとする2分探索木
- アドレスに対応したビットマップ
広告
解説
- 空き領域のアドレスをキーとして探索しても、求める空き領域を見つけることはできません。
- 先頭から順にさがしていくので、要求量が小さい場合は早く探索できますが、要求量が大きくなるほどリストをたどる回数が増え非効率になります。N個の領域から探索する場合の平均探索回数はN＋12回です。
- 正しい。空き領域の大きさがキーになっていれば、探索範囲を2分の1に絞ることを繰り返して、効率よく目的の空き領域を探索することができます。N個の領域から探索する場合の平均探索回数は log2N 回で「イ」よりも少なくなります。
- ビットマップインデックスは取り得る値が少ない場合に有効な方法ですが、●以上や●以下などの範囲を指定して検索することはできません。
広告