[平成２６年度春] 午後 問8解説

[問題文・解答]

平成２６年度４月に実施された基本情報技術者試験の午後試験の問題・解答はIPA公式ページからダウンロード出来ます。（以下リンク）

[H26春 午後 問題文]　　　[H26春 午後 解答]

[問題概要]

この問題は必須問題です。
出題分野はデータ構造及びアルゴリズムで、問題の題材は空き領域の管理です。
セルを１列に並べた領域について空きセルの管理（割当・解放）をするプログラムについて問われます。専門知識は不要で、問題文をよく理解すれば解答可能な問題です。

[設問1]

a) 終点_i=始点_p-1かつ終点_p+1=始点_i+1の状況は、空きセルの間の領域を全て解放する場合です。空きリスト上は2つの組{ 始点_i, 終点_i }及び{ 始点_i+1, 終点_i+1 }とその間の領域をまとめて１つの空き領域とするため、これらの２組を{ 始点_i, 終点_i+1 }で置き換えればよいため「ア」が正解です。

b) 終点_i<始点_p-1かつ終点_p+1<始点_i+1の状況は、空きセルの間に割当領域を挟んで新たに空きセルを追加する処理となるため、組{ 始点_p, 終点_p }を挿入すればよく「エ」が正解となります。

[答] a) ア　b) エ

[設問2]

c) cの部分は表1の始点_i=始点_pかつ終点_p<終点_iの状況の処理であり、現在の空きセル区間の前半部分を割り当てる場合です。この場合、組{ 始点_i, 終点_i }を組{ 終点_p+1, 終点_i }で置き換えればよいため「イ」が正解です。

d) dの部分は表1の始点_i<始点_pかつ終点_p=終点_iの状況の処理であり、現在の空きセル区間の後半部分を割り当てる場合です。この場合、組{ 始点_i, 終点_i }を組{ 始点_i, 始点_p-1 }で置き換えればよいため「ウ」が正解です。

e) eの部分は１つの組を２つの組で置き換える際に後ろの組のインデックスを１つずつ後ろにずらしていく処理です。現在の組情報を消去しないために処理は最後尾（N)から前に進むように実施し、I+1まで行う必要があるため「ウ」が正解です。

[答] c) イ　d) ウ　e) ウ

[設問3]

f) 始点に-∞、終点に+∞を設定することで、少なくとも空きリストに１つの組{-∞, +∞}があるため「ア」が正解です。
イ：∞の設定に関わらず、保証されません。
ウ：使用状況によっては領域中の実際の空きセルは無くなります。
エ：∞の設定に関わらず、連続した長い空きセルは一つの組で表せます。

g) 空きリスト中の組の個数が最大となるのは、セルが１つおきに割り当てられている場合です。この場合、空きリストの個数はセルの総数÷2+1となります。ただし、設問中に整数同士の序算は庄野小数点以下を切り捨てるとあることから「エ」が正解です。

h) 全てのセルが割当済みとなった場合、空きリストは組{-∞, -1}と組{E+1, +∞}の2組となるため「イ」が正解です。

[答] f) ア　g) エ　h) イ

上記の解説は問題と解答を元に自分なりの考え方を記述しており、間違っている部分もあるかと思いますので、ご了承願います。また、誤りについては正しい考え方をご指摘・ご教授頂けると助かります。