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

正解 ウ

大きさをキーとする2分探索木なら、要求量以上で最小の空き領域を平均O(log n)で探せます。

最適適合（best-fit）は、要求量以上の空き領域のうち最小のものを選ぶ方式です。空き領域の大きさをキーとする2分探索木では、根から大小を比べて1本の経路をたどるだけで目的の領域が見つかります。平均の探索時間は、空き領域の数をnとしてO(log n)です。連結リストやアドレス順の構造では、条件に合う領域を見つけるまで多くの要素を調べる必要があり、平均O(n)以上かかります。

ア：アドレスをキーとする2分探索木は、大きさの順に並んでいません。最小の適合領域を探すには全ノードを調べる必要があり、O(n)かかります。

イ：大きさ順の片方向連結リストは、先頭から順にたどれば最初の適合領域が最小になります。ただし順次探索なので、平均O(n)かかり2分探索木より遅くなります。

エ：ビットマップは、空いている連続領域を見つけるためにビット列を走査する必要があります。処理時間はメモリの大きさに比例し、最も遅くなります。

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