要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。
要求量以上の大きさをもつ未使用領域のうちで最小のものを割り当てる最良適合(best-fit)アルゴリズムを用いる場合、未使用領域を管理するためのデータ構造として、メモリ割り当て時の処理時間が最も短いものはどれか。
| ア | 空き領域のアドレスをキーとする2分探索木 |
| イ | 空き領域の大きさが小さい順の片方向連結リスト |
| ウ | 空き領域の大きさをキーとする2分探索木 |
| エ | アドレスに対応したビットマップ |
答え ウ
【解説】
未使用領域の管理方法の違いで、割り当てる領域の決定に必要な時間を考える。(未使用領域の個数はNとする。)
| ア | アドレスで整列したデータ構造の場合、大きさで選択を行うため、全データをチェックしなくてはならないため、処理計算量はO(N)である。 |
| イ | 片方向連結リストの場合、先頭から順に大きさをチェックするため、処理計算量はO(N)である。 |
| ウ | 大きさで整列したデータ構造の場合、処理計算量は木の状態にもよるが最短でO(log2N)である。(最悪値はO(N)) |
| エ | アドレスに対応したビットマップの場合、全データをチェックしなくてはならないため、処理計算量はO(N)である。 |
【キーワード】
・2分探索木
- 2分探索木
節の子の数が2以下になるように構成された2分木の一種で、節の左の子は節のよりも小さな節になっていて、右の子は節よりも大きな節になる。
2分探索木は節の追加のときに木の再構築を行う必要がないため、節(要素)の追加が容易であることが特徴である。また、節を削除するときも木の再構築は一部分で行える。
木の中で一番右の節が木の中の最大値で、一番左の節が最小値になる。
もっと、「二分探索木」について調べてみよう。
戻る
一覧へ
次へ