令和5年度 春期 応用情報技術者試験 午前 問5
テクノロジアルゴリズム
この問題は2023(R5)春 応用情報技術者 午前に出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。
本ページの問題文・選択肢は、原本の体裁を Web 表示用に正規化しています（改行・記号・数式・図表参照の調整）。設問の趣旨および正解に影響する変更は加えていません。
要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合（best-fit）アルゴリズムを用いる場合, 空き領域を管理するためのデータ構造として, メモリ割り当て時の平均処理時間が最も短いものはどれか。
解答・解説を読む
正解: 選択肢ウ
最適適合（best-fit）アルゴリズムは、要求されたサイズ以上の空き領域の中で、最も小さい領域を割り当てる方式です。
この処理を高速に行うためには、空き領域を大きさ（サイズ）を基準にして検索できるデータ構造が必要です。
各選択肢の解説
- ア：空き領域のアドレスをキーとする2分探索木
アドレスをキーにしているため、サイズによる検索には適さず、最適な空き領域を見つけるためには全ノードを探索する必要があります。 - イ：空き領域の大きさが小さい順の片方向連結リスト
サイズの小さい順に並んでいるため、先頭から順に調べて最初に条件を満たした空き領域が最適となります。しかし、線形探索となるため、平均処理時間は空き領域の数 に対して となります。 - ウ：空き領域の大きさをキーとする2分探索木
サイズをキーにした2分探索木を用いることで、条件を満たす最小の空き領域を平均 の計算量で高速に検索できます。したがって、平均処理時間が最も短くなります。 - エ：アドレスに対応したビットマップ
ビットマップを順次走査して連続した空き領域のサイズを確認する必要があるため、検索に多大な時間がかかります。