データ構造 (全29問中25問目)

No.25

要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ未使用領域のうちで最小のものを割り当てる最良適合(best-fit)アルゴリズムを用いる場合,未使用領域を管理するためのデータ構造として,メモリ割当て時の処理時間が最も短いものはどれか。
  • 空き領域のアドレスをキーとする2分探索木
  • 空き領域の大きさが小さい順の片方向連結リスト
  • 空き領域の大きさをキーとする2分探索木
  • アドレスに対応したビットマップ
  • [この問題の出題歴]
  • ソフトウェア開発技術者 H15春期 問12

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

  • キー値がアドレスでは適切な空き領域をもつものを探索することができません。
  • 要求サイズが小さい場合は早く探索できますが、要求サイズが大きくなればなるほどリストをたどる回数が増え非効率になります。
  • 正しい。要求サイズとキー値を比較しながら2分探索木の枝をたどることで効率よく探索することができます。
  • ビットマップインデックスは値の種類が少ない場合には有効ですが、範囲指定検索には適していません。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop