平成31年春期試験午前問題 問5

情報処理技術者試験合格率アップセミナー
要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合(best-fit)アルゴリズムを用いる場合,空き領域を管理するためのデータ構造として,メモリ割当て時の平均処理時間が最も短いものはどれか。

  • 空き領域のアドレスをキーとする2分探索木
  • 空き領域の大きさが小さい順の片方向連結リスト
  • 空き領域の大きさをキーとする2分探索木
  • アドレスに対応したビットマップ
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
  • キー値がアドレスでは適切な空き領域をもつものを探索することができません。
  • 要求サイズが小さい場合は早く探索できますが、要求サイズが大きくなればなるほどリストをたどる回数が増え非効率になります。
  • 正しい。要求サイズとキー値を比較しながら2分探索木の枝をたどることで効率よく探索することができます。
  • ビットマップインデックスは値の種類が少ない場合には有効ですが、範囲指定検索には適していません。

この問題の出題歴


Pagetop