応用情報技術者試験 応用情報技術者試験 令和5年度春期 午前 問5: 要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合（best-fit）アルゴリズ

正解

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

正答率 42.0%（281人中 118人が正解）

問題の解説

最適適合では、要求量以上で最小の空き領域をすばやく見つける必要がある。空き領域の大きさをキーにした 2 分探索木なら、大小を比べて枝をたどるだけで目的の領域に行き着き、時間は木の深さ（領域数の対数）に比例する。ほかの方式は、領域を端から順に調べるため、領域数に比例した時間がかかる。

選択肢ごとの解説

• アアドレス順に並ぶ木では、大きさの条件で枝を絞れない。最小の適合領域を見つけるには全領域を調べる必要があり、領域数に比例した時間がかかる。
• イ大きさ順のリストは、先頭から順にたどって最初に見つかる適合領域が最適適合になるが、たどる回数は平均で領域数に比例する。
• ウ正しい。大きさをキーにした 2 分探索木は、要求量以上で最小の領域を木の深さ分の比較で見つけられ、平均処理時間が最も短い。
• エビットマップは番地ごとの使用・未使用を 1 ビットで表すだけで、大きさ順には並ばない。最小の適合領域を探すには全体を走査する必要がある。