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

【正解】ウ

最適適合では、要求された大きさ以上の空き領域のうち、最も小さい領域を探します。そのため、探索の基準となる空き領域の大きさをキーにした2分探索木が適しています。要求量をキーとして探索すると、要求量以上となる最小のキーを効率よく見つけられます。平衡に近い2分探索木では、空き領域がn個あるときの平均探索時間はO（log n）です。割当て後に領域を削除したり、残った領域を新しい大きさで登録したりする処理も、平均O（log n）で行えます。

アのアドレスをキーとする2分探索木は誤りです。アドレス順の管理は、解放時に隣接する空き領域を探して結合する処理には役立ちます。しかし、大きさを基準に要求量以上の最小領域を探すには、多数の節を調べる必要があります。

イの大きさが小さい順の片方向連結リストは誤りです。先頭から順に調べれば条件を満たす最初の領域が最適適合になりますが、途中の要素へ直接移動できないため、平均探索時間はO（n）です。

エのアドレスに対応したビットマップは誤りです。これはメモリを一定単位に分け、各単位の使用中又は空きをビットで管理する方式です。必要量以上の連続した空き部分を探し、更に最小の部分を選ぶには広い範囲を走査する必要があります。

【ポイント】 最適適合は割当て後の余りを小さくできますが、小さな空き領域が増える外部断片化を招くことがあります。 2分探索木の計算量は平均O（log n）ですが、偏った木ではO（n）になるため、実装では平衡木が有効です。