平成22年度 春期 午前 問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
答えと解説を見る
✓ これが正解エC，B，A
解説
割当て済みが最小の媒体を選ぶと C、B、A の順です。
三つの媒体は容量が同じで、初めはすべて空きの状態です。ですから空き領域が最大の媒体を選ぶという規則は、その時点で割り当て済みの合計が最も小さい媒体を選ぶ、と言い換えられます。こう読み替えると容量そのものの数値は使わずに済み、合計の小さいほうから順に選んでいくアルゴリズムとして 1 行 1 回で追えるようになります。空きが等しいときは条件により A、B、C の順に選びます。90、30、40、40、70、30 という順でファイル領域の割当てを 6 回追うと、はじめは三つとも 0 なので A が 90 を受け、次は B と C が 0 で並ぶので B が 30、続いて C が 40、以降も合計の小さい順に B が 40、C が 70、B が 30 を受けます。割当ての合計は A が 90、B が 100、C が 110 となり、大きい順に並べた正解は C、B、A です。要求の合計 300 と三つの合計が一致することで確かめられます。
ほかの選択肢はなぜ違うのか
- アA，B，C：最初の 90 という大きな要求を受けた媒体が、そのまま最大になると見た並びです。その媒体は以後ずっと合計が最も大きいままなので一度も選ばれず、6 回終わったときにはかえって最小になります。
- イA，C，B：先頭を 90 の要求を受けた媒体としている点は同じで、残る二つの順序だけを入れ替えた並びです。合計は 90、100、110 と分かれるため、先頭に置いた媒体が最大になることはありません。
- ウB，A，C：90 の要求を受けた媒体を 2 番目に置いた並びです。その媒体の合計は 90 で三つのうち最も小さく、100 と 110 のどちらよりも下になるので、真ん中の順位に来ることはありません。
この問題の用語
- アルゴリズム問題を解くための、決まった手順や考え方そのものです。同じ問題でも手順によって、処理にかかる時間や必要な記憶量が変わります。
出典：平成22年度 春期 応用情報技術者試験 午前 問20
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）