[応用情報技術者試験] メモリ割当て時の平均処理時間が最も短いものはどれか。

応用情報技術者試験の過去問を解くだけの書き溜め型の勉強記事です。
少なくとも一日一問以上ずつ問いていくので、気軽に読んでください。

広告

先に出典: 平成31年度 春期 応用情報技術者試験 午前 問5

問題

問題文

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

ap_kakomon_5

(いい感じのLaTeXプラグインを入れるまでは当面スクショします)

回答

(ウ) 空き領域の大きさをキーとする2分探索木

自己解説

自分的ポイントは、
最も短いものを選ぶので、間違っているものから除外する方針がいいと思う。
選択肢によっては、正解以外すべて非適合の可能性があるので。

(ア)空き領域のアドレスをキーとする2分探索木

不正解。
アドレスをキーにしてしまうと空き領域についての情報は引っ張ってこれない。

(イ)空き領域の大きさが小さい順の片方向連結リスト

小さい領域を要求するときは早いけど、大きい領域を要求し始めると遅くなるよね。
なので不正解

(ウ)空き領域の大きさをキーとする2分探索木

正解。
(エ)も値の種類が少ない数なら適合ですが、(ウ)の方が最適。

(エ)アドレスに対応したビットマップ

範囲指定検索には適していないので不正解。

問題の著作権について

その他の項目で下記の質問に対し、
許諾、使用料の必要性がないとのことなのでありがたく使わせていただきます。

試験の過去問題の使用方法(申請方法、使用料等)について教えてください。
 当機構で公表している過去の試験問題の使用に関し、許諾や使用料は必要ありません。



次回は、問6です。
じゃあね〜〜。