データ構造 (全40問中3問目)
No.3
要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合(best-fit)アルゴリズムを用いる場合，空き領域を管理するためのデータ構造として，メモリ割当て時の平均処理時間が最も短いものはどれか。
出典：令和5年春期 問5
- 空き領域のアドレスをキーとする2分探索木
- 空き領域の大きさが小さい順の片方向連結リスト
- 空き領域の大きさをキーとする2分探索木
- アドレスに対応したビットマップ
- [出題歴]
- 応用情報技術者 H31春期 問5
- ソフトウェア開発技術者 H15春期 問12
- ソフトウェア開発技術者 H18春期 問11
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
ウ
解説
- 空き領域のアドレスをキーとして探索しても、求める空き領域を見つけることはできません。
- 先頭から順にさがしていくので、要求量が小さい場合は早く探索できますが、要求量が大きくなるほどリストをたどる回数が増え非効率になります。N個の領域から探索する場合の平均探索回数はN＋12回です。
- 正しい。空き領域の大きさがキーになっていれば、探索範囲を2分の1に絞ることを繰り返して、効率よく目的の空き領域を探索することができます。N個の領域から探索する場合の平均探索回数は log2N 回で「イ」よりも少なくなります。
- ビットマップインデックスは取り得る値が少ない場合に有効な方法ですが、●以上や●以下などの範囲を指定して検索することはできません。