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

解説

正解は3です。 最適適合（best-fit）は、要求量以上の空き領域のうち最も小さいものを選ぶ方式です。 したがって、空き領域を「大きさ」ですばやく検索できるデータ構造が有利です。 【選択肢別解説】 1：× アドレスをキーとする2分探索木は、アドレスでの検索は速いものの、大きさの条件では検索できません。 最小の適合領域を探すには全節点を調べる必要があります。 2：× 大きさの小さい順の片方向連結リストなら、先頭からたどって最初に要求量以上になった領域が答えになります。 しかし連結リストは途中へ飛べないため、平均で要素数に比例した時間がかかります。 3：○ 大きさをキーとする2分探索木なら、要求量と比較しながら木をたどるだけで、要求量以上で最小の領域を見つけられます。 木の高さに比例する時間、平均で要素数の対数に比例する時間で済むので最も短くなります。 4：× ビットマップはメモリの各単位が使用中か空きかを表すものです。 連続した空き領域の大きさを求めるには全体を走査する必要があり、時間がかかります。 【ポイント】 探索のキーには「何で探すか」を選ぶのが原則です。 最適適合なら大きさ、アドレス順の併合処理ならアドレスをキーにします。