分野別過去問題テクノロジ系　データ構造 No.9

データ構造(全40問中9問目)

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

出典：平成31年春期　問 5

正解　ウ問題へ

分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：データ構造

解説

空き領域のアドレスをキーとして探索しても、求める空き領域を見つけることはできません。
先頭から順にさがしていくので、要求量が小さい場合は早く探索できますが、要求量が大きくなるほどリストをたどる回数が増え非効率になります。N個の領域から探索する場合の平均探索回数はN＋12回です。
正しい。空き領域の大きさがキーになっていれば、探索範囲を2分の1に絞ることを繰り返して、効率よく目的の空き領域を探索することができます。N個の領域から探索する場合の平均探索回数は log₂N 回で「イ」よりも少なくなります。
ビットマップインデックスは取り得る値が少ない場合に有効な方法ですが、●以上や●以下などの範囲を指定して検索することはできません。