ソフトⅡコース担当 ブログのおにーさまこと高橋です。
今回は、平成26年度春期基本情報技術者試験午後問8、アルゴリズム問題の解説です。
連続領域から領域を割り当てるAlloc関数、及び割り当てられている領域を解放するFree関数に関する問題です。問題文中の「空きリストの説明」に書いてあるように、連続領域中の空き領域の開始位置、終了位置が空きリストに格納されています。
Alloc関数は、引数で指定した範囲が空き領域であれば、その領域を割り当てます。問題では、空きリストから指定領域を除きます。空き領域にある空き領域範囲の開始位置、終了位置と、引数の開始位置、終了位置との関係から、表1にある4つのパターンが考えられます。4パターンを処理した場合のリストの状態は、次の図のようになります。
（図をクリックで拡大します）
黄色部分が割り当て済みの領域、白色部分が空き領域です。赤色部分がAllocによって割り当てられる領域です。赤の矢印で、空きリストの要素が、どのように変更されるかを表しています。
Free関数は、引数で指定した範囲が割り当て済みであれば、その領域を解放します。問題では、空きリストに加えます。空き領域にある空き領域範囲の開始位置、終了位置と、引数の開始位置、終了位置との関係から、表2にある4つのパターンが考えられます。4パターンを処理した場合のリストの状態は、次の図のようになります。
（図をクリックで拡大します）
問題の表2と図を比べると、空欄aには、図では{5,6}{15,17}が{5,17}にまとまっていることから、{始点i,終点i+1}が入ります。アが正解です。また空欄bには、{5,6}の直後に{10,12}が挿入されていることから、{始点p,終点p}が入ります。エが正解です。
Allocの図と比較すると、空欄cの部分は図の2つ目のパターンに該当します。始点に第2引数に1を加えた値を格納しているので、「始点[I]←終点P+1」が入ります。イが正解です。
空欄dの部分は図の3つ目のパターンに該当します。終点に第1引数から1を引いた値を格納しているので、「終点[I]←始点P-1」が入ります。ウが正解です。
空欄eの部分は図の4つ目のパターンに該当します。リストの後ろから1つずらします。図では[3][2]をずらしているので、I+1番目までをずらせばよいです。「N,L≧I+1,-1」が入ります。ウが正解です。
それでは、続きは次週ということで。
2014年（平成26年度）春期の解説
- 平成26年度 春 基本情報技術者試験 【問13】（その2）
- 平成26年度 春 基本情報技術者試験 【問13】（その1）
- 平成26年度 春 基本情報技術者試験 【問12】（その2）
- 平成26年度 春 基本情報技術者試験 【問12】（その1）
- 平成26年度 春 基本情報技術者試験 【問6】
- 平成26年度 春 基本情報技術者試験 【問7】（その2）
- 平成26年度 春 基本情報技術者試験 【問7】（その1）
- 平成26年度 春 基本情報技術者試験 【問4】
- 平成26年度 春 基本情報技術者試験 【問5】
- 平成26年度 春 基本情報技術者試験 【問9】
- 平成26年度 春 基本情報技術者試験 【問8】（その2）
- 平成26年度 春 基本情報技術者試験 【問3】（その3）
- 平成26年度 春 基本情報技術者試験 【問8】（その1）
- 平成26年度 春 基本情報技術者試験 【問3】（その2）
- 平成26年度 春 基本情報技術者試験 【問3】（その1）
- 平成26年度 春 基本情報技術者試験 【問1】
- 平成26年度 春 基本情報技術者試験 【問2】
- Date：
- この記事を
友だちに教える - LINE
- - HatenaBookmark
- GooglePlus
