令和5年度 春期 応用情報技術者試験 午前 問5
テクノロジ／ソフトウェア要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合（best-fit）アルゴリズムを用いる場合，空き領域を管理するためのデータ構造として，メモリ割当て時の平均処理時間が最も短いものはどれか。
出典：令和5年度 春期 応用情報技術者試験 午前 問5
- ア空き領域のアドレスをキーとする 2 分探索木
- イ空き領域の大きさが小さい順の片方向連結リスト
- ウ空き領域の大きさをキーとする 2 分探索木
- エアドレスに対応したビットマップ
正解：ウ
解説
最適適合（best-fit）では「要求量以上で最小の空き領域」を効率よく見つける必要があります。空き領域の大きさをキーとする 2 分探索木を使えば，要求量以上の最小の領域を平均 O(log n) で探索できるため，平均処理時間が最も短くなります。
選択肢ごとの解説
- ア誤り。アドレスをキーとする 2 分探索木では，大きさの条件を満たす領域を探すのに全ノードを調べる必要があり，O(n) 掛かります。
- イ誤り。大きさ順の片方向連結リストでは先頭から順にたどる線形探索となり，平均 O(n) 掛かります。
- ウ正しい。大きさをキーとする 2 分探索木なら，要求量以上で最小の空き領域を平均 O(log n) で見つけられます。
- エ誤り。ビットマップは領域の使用・未使用をビットで表すもので，要求量以上の最小空き領域を探すには連続する空きビットを走査する必要があり，効率が悪くなります。