答え ウ
【解説】
未使用領域の管理方法の違いで、割り当てる領域の決定に必要な時間を考える。(未使用領域の個数はNとする。)
ア |
アドレスで整列したデータ構造の場合、大きさで選択を行うため、全データをチェックしなくてはならないため、処理計算量はO(N)である。 |
イ |
片方向連結リストの場合、先頭から順に大きさをチェックするため、処理計算量はO(N)である。 |
ウ |
大きさで整列したデータ構造の場合、処理計算量は木の状態にもよるが最短でO(log2N)である。(最悪値はO(N)) |
エ |
アドレスに対応したビットマップの場合、全データをチェックしなくてはならないため、処理計算量はO(N)である。 |
したがって、メモリ割り当ての処理時間が最も短いデータ構造は『
空き領域の大きさをキーとする2分探索木』(ウ)になる。