平成31年度 春期 応用情報技術者試験 問5

解説

正解は3です。 最適適合（best-fit）は、要求量以上の空き領域のうち最も小さいものを割り当てる方式です。 したがって、空き領域を「大きさ」で素早く探せるデータ構造が有利です。 【選択肢別解説】 1：× アドレスをキーとする2分探索木では、大きさによる検索ができません。 条件に合う最小の領域を探すには、木全体をたどる必要があり時間がかかります。 2：× 大きさ順の連結リストなら、先頭から見て最初に要求量以上となった領域が最適な領域です。 しかし先頭から順にたどる線形探索になるので、平均処理時間は2分探索木より長くなります。 3：○ 大きさをキーとする2分探索木なら、木の高さに比例する手間で要求量以上の最小の領域を見つけられます。 平衡していれば探索回数はおよそlog n回に抑えられ、最も速くなります。 4：× ビットマップはメモリの単位ごとに使用中か空きかを表すだけです。 必要な大きさの連続した空きを見つけるにはビット列を走査する必要があり、遅くなります。 【ポイント】 「何をキーに探すか」がデータ構造選びの基本です。 best-fitは大きさで探すので大きさをキーにし、隣の領域との結合を考えるときはアドレスをキーにします。