応用情報技術者 2010年 春期 午前2 問20
問題文
三つの媒体A〜Cに次の条件でファイル領域を割り当てた場合、割り当てた領域の総量が大きい順に媒体を並べたものはどれか。
〔条件〕
(1) ファイル領域を割り当てる際の媒体選択アルゴリズムとして、空き領域が最大の媒体を選択する方式を採用する。
(2) 割当て要求されるファイル領域の大きさは、順に90, 30, 40, 40, 70, 30 (Mバイト)であり、割り当てられたファイル領域は、途中で解放されない。
(3) 各媒体は容量が同一であり、割当て要求に対して十分な大きさをもち、初めはすべて空きの状態である。
(4) 空き領域の大きさが等しい場合には、A, B, Cの順に選択する。
選択肢
ア：A, B, C
イ：A, C, B
ウ：B, A, C
エ：C, B, A（正解）
🔒 解説は解答すると表示されます
最大空き領域アルゴリズム【午前2解説】
正解の理由
与えられた割当方式は「空き領域が最大の媒体を選ぶ」方式（いわゆるワーストフィット）であり、媒体の容量が同じで初期は全て空であるため、各時点で「最も割当済み容量が小さい媒体」が選ばれます。各要求（90, 30, 40, 40, 70, 30）を順に適用すると、割当の最終合計はA=90, B=100, C=110となり、合計が大きい順はC > B > Aです。したがって正解は エ（C, B, A）です。
解法ステップ
アルゴリズムの要点：容量が同じなら「空きが最大＝割当済みが最小」。空きが等しい場合はA→B→Cの順序で選ぶ。
順に割り当てて状態を更新します（ここでは各媒体の「割当済み合計」を示す）。
- 要求90:
- 初期A=0,B=0,C=0（全て同じ→優先順A）
- 90をAに割当 → A=90, B=0, C=0
- 要求30:
- 割当済みが最小なのはBとC（0）。優先順でBを選択。
- 30をBに割当 → A=90, B=30, C=0
- 要求40:
- 最小はC（0） → Cに割当
- 40をCに割当 → A=90, B=30, C=40
- 要求40:
- 現在の割当済みはA=90, B=30, C=40。最小はB（30）なのでBを選択。
- 40をBに割当 → A=90, B=70, C=40
- 要求70:
- 現在A=90, B=70, C=40。最小はC（40）なのでCを選択。
- 70をCに割当 → A=90, B=70, C=110
- 要求30:
- 現在A=90, B=70, C=110。最小はB（70）なのでBを選択。
- 30をBに割当 → A=90, B=100, C=110
最終合計：A=90, B=100, C=110。順序はC(110) > B(100) > A(90) → エ。
選択肢別の誤答解説
- ア: A, B, C
誤り。Aが最大、Bが次、Cが最小とする並びですが、実際はCが最終的に最大（110）です。途中の選択基準の適用ミス（例えば4回目の40を誤ってCに割当てるなど）に注意。 - イ: A, C, B
誤り。CとBの最終合計を逆にしている解釈で、5〜6回目の割当判断順序を取り違えた可能性があります。 - ウ: B, A, C
誤り。Bを最大と見なしていますが、最終値はB=100、A=90、C=110でありCが最大です。 - エ: C, B, A
正しい。上記の手順で得られる最終合計に一致します。
（補足：4回目の40MB割当のように、各ステップで「現在の割当済みが最小の媒体」を確実に選ぶことが正解導出の鍵です）
よくある誤解
- 「空きが最大」＝「既に割当が大きい媒体を選ぶ」と誤解する
実際は同容量なら空きが最大なのは割当済みが最も小さい媒体です。逆に考えると誤答しやすいポイントです。 - 同値時の優先順を忘れる
初回などで全て同じ場合にA→B→Cの順序ルールを適用しないと異なる枝分かれを生みます。 - ステップごとの状態更新を省略する
各要求ごとに割当済み値を更新して判断することを怠ると、途中の選択で誤ることがあります。
補足コラム
この方式は一般に「ワーストフィット（Worst-fit）」と呼ばれ、断片化を避ける目的で用いられることがあります。対義語は「ベストフィット（空きが最小の場所へ）」や「ファーストフィット（先に見つかった空きへ）」です。今回の問題では容量が十分に大きく初期が空なので、割当判断は「割当済み合計の大小比較」と同義になります。実装上は各媒体の現在割当量を管理しておき、要求ごとに最小値（または優先順位での先頭）を選べば良いでしょう。
FAQ
Q1: 容量が異なる場合はどう判断しますか？
A1: 実際には「空き容量」を直接比較します（容量 − 割当済み）。今回のように総容量が十分大きく同一なら割当済みの最小値比較で同等です。
A1: 実際には「空き容量」を直接比較します（容量 − 割当済み）。今回のように総容量が十分大きく同一なら割当済みの最小値比較で同等です。
Q2: 解放（deallocation）があると結果は変わりますか？
A2: はい。解放があると各時点の空き量が変化するため、以降の割当先が変わり得ます。問題文で「途中で解放されない」と明記している点に注意してください。
A2: はい。解放があると各時点の空き量が変化するため、以降の割当先が変わり得ます。問題文で「途中で解放されない」と明記している点に注意してください。
Q3: 試験ではどのように速く解けばよいですか？
A3: 各媒体の現在割当合計だけを追えば良いので、紙にA,B,Cの値を逐次更新していくと速く正確に解けます。特に同値時の優先ルールを先に確認しておくこと。
A3: 各媒体の現在割当合計だけを追えば良いので、紙にA,B,Cの値を逐次更新していくと速く正確に解けます。特に同値時の優先ルールを先に確認しておくこと。
関連キーワード: 最大空き領域, ワーストフィット, メモリ割当て, ファイル配置, アルゴリズム
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！