令和5年度 春期 応用情報技術者試験 午前 問5

• ア: 空き領域のアドレスをキーとする2分探索木
  誤り。アドレス順で管理しても、空き領域のサイズ順にはなっていないため、最適適合アルゴリズムには非効率です。

• イ: 空き領域の大きさが小さい順の片方向連結リスト
  誤り。小さい順に探索できますが、リストを一つずつ辿る必要があるため、要素数が増えると非効率になり、平均処理時間が長くなります。

• ウ: 空き領域の大きさをキーとする2分探索木
  正しい。2分探索木を使用すれば、空き領域の大きさをキーに効率的に検索できます。探索範囲を2分の1に絞り込むことを繰り返すため、平均処理時間はlog2N回の検索で済み、最も効率的です。

• エ: アドレスに対応したビットマップ
  誤り。ビットマップは空き領域の有無を示すだけで、サイズ順での検索には向きません。

答え

ウ: 空き領域の大きさをキーとする2分探索木