テクノロジ系
春期
応用情報技術者 2019年 春期 問5
5 / 80
要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の 大きさをもつ空き領域のうちで最小のものを割り当てる最適適合(best-fit)アルゴ リズムを用いる場合、空き領域を管理するためのデータ構造として、メモリ割当て 時の平均処理時間が最も短いものはどれか。
正解と解説
表示する
正解 ウ
空き領域の大きさをキーとする2分探索木
ベストフィットは要求量以上で最小の空き領域を探すため,空き領域の大きさをキーにした2分探索木で管理すると,目的の領域を高速に探索でき平均処理時間が最短になります(ウ)。アドレスをキーにした木(ア)やビットマップ(エ),線形リスト(イ)では大きさ順の探索が非効率です。