テクノロジ系
春期
応用情報技術者 2023年 春期 問5
5 / 80
要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大 きさをもつ空き領域のうちで最小のものを割り当てる最適適合(best-fit)アルゴリ ズムを用いる場合、空き領域を管理するためのデータ構造として、メモリ割当て時の 平均処理時間が最も短いものはどれか。
正解と解説
表示する
正解 ウ
空き領域の大きさをキーとする2分探索木
最適適合では要求量以上で最小の空き領域を素早く見つける必要があり、空き領域の大きさをキーとする2分探索木ならば目的の大きさに近い領域を対数時間で探索できるので(ウ)が正解です。大きさ順の連結リストやビットマップは線形走査となり、アドレスをキーとする木は大きさ検索に向かず平均処理時間が長くなります。