「AP過去問令和6年度春期午前問5」の版間の差分

2025年9月22日 (月) 19:57時点における版

問5(問題文)

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

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

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

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

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

回答・解説

AP過去問令和6年度春期午前問4前の問題へ

AP過去問令和6年度春期午前問6次の問題へ

AP過去問令和6年度春期午前問題に戻る

@@ 8行目: / 8行目: @@
 =='''問5(問題文)'''==
-　正の整数Mに対して、次の二つの流れ図に示すアルゴリズムを実行したとき、結果xの値が等しくなるようにしたい。aに入れる条件として、適切なものはどれか。
+　要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合(best-fit)アルゴリズムを用いる場合、空き領域を管理するためのデータ構造として、メモリ割当て時の平均処理時間が最も短いものはどれか。
-[[ファイル:AP R6 1Spring AMQ5 Fig1.png|400px|thumb|none|]]
+ア　空き領域のアドレスをキーとする2分探索木
+イ　空き領域の大きさが小さい順の片方向連結リスト
-ア　n ＜ M
+ウ　空き領域の大きさをキーとする2分探索木
-イ　n ＞ M－1
+エ　アドレスに対応したビットマップ
-ウ　n ＞ M
-エ　n ＞ M＋1
 =='''回答・解説'''==
-　まずは左のフローチャートの処理を眺めてみます。
-　例えばM=3の処理の場合を考えてみましょう。
-　xに1を格納した後
-　初期値がMで増分が-1で終わり値が1の変数nを使うループの宣言があって次の処理が
-　x = n * xですから最初の演算は
-= 3 * 1　次は
-= 2 * 3　次は
-= 1 * 6　で処理終了です。
-　階乗の計算をしていますね。M=3のときは3! = 6を求めています。
-　では右のフローチャートをみてみましょう。
-　xに1、nに1を格納した後ループに突入します。
-　x = x * n ですから
-= 1 * 1 次に、n = n + 1、ですから
-= 1 + 1、この繰り返しで
-= 1 * 2 　　　3 = 2 + 1、次に
-= 2 * 3 　　　4 = 3 + 1、ここで処理を止めなければなりません。
-　このときnは4になっていて、Mは3ですから、このときはじめて成立する条件は
-　n > M です。 4 > 3 が成立するので、YESの方の分岐に進むことができます。
-　したがって、
-<span style = "background:linear-gradient(transparent 75%, #7fbfff 75%); font-weight:bold; ">
-ウ　n > M</span>
-　が答えです。