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

要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。
要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最良適合(best-fit)アルゴリズムを用いる場合、空き領域を管理するためのデータ構造として、メモリ割り当て時の処理時間が最も短いものはどれか。

 ア  空き領域のアドレスをキーとする2分探索木
 イ  空き領域の大きさが小さい順の片方向連結リスト
 ウ  空き領域の大きさをキーとする2分探索木
 エ  アドレスに対応したビットマップ


答え ウ


解説
未使用領域の管理方法の違いで、割り当てる領域の決定に必要な時間を考える。(未使用領域の個数はNとする。)

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


キーワード
・2分探索木

キーワードの解説

戻る 一覧へ 次へ