基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成26年 春期 基本情報技術者 午後 問08
問08   必須問題

問8 次のアルゴリズムの説明を読んで,設問1〜3に答えよ。

 セルを1列に連続して並べた領域がある。この領域中のセルについて,割当てと解放の処理を行う。

 各セルには,セル位置を指定するための連続する整数が対応している。 領域のセル数や,対応する整数の範囲には,特に制限がない。

 各セルは,“空き”又は“割当済み”のいずれかの状態にある。現在, 領域中のどのセルが“空き”の状態にあるかという情報を,空きリストとして保持している。

 関数 Alloc (始点,終点) は,引数で指定した始点から終点までの連続した“空き”セルを “割当済み”として,空きリストから取り除く。関数 Free (始点,終点) は, 引数で指定した始点から終点までの連続した“割当済み”セルを“空き”として, 空きリストに戻す。

[空きリストの説明〕

 空きリストの形式を,次に示す。

  { { 始点 1 ,終点 1 },{ 始点 2 ,終点 2 }, …,{ 始点 N ,終点 N } }

{ 始点 i ,終点 i } (始点 i ≦終点 i ) は, 一つの連続した“空き”セルの先頭位置と終端位置の組(以下,組という)で, 始点 1 <始点 2 <…<始点 N である。

 割当て・解放の処理と空きリストの状態の例を,次の (1) 〜 (3) に示す。 ここで,セル 中の数字は,セル位置を表す。 また, は“空き”を, は“割当済み”を,それぞれ表す。

(1) 領域の初期状態は,全セルが空いている。空きリストは { {−∞,+∞} } で表す。

 ここで,記号“−∞”は,領域中のどのセル位置の値よりも小さい整数を表し, 記号“+∞”は,領域中のどのセル位置の値よりも大きい整数を表すものとする。 また,セル位置 −∞〜+∞ のうち,領域外の部分には“空き”セルが並んでいるものとする。

(2) 関数 Alloc で“割当済み”としたセルは,空きリストから取り除く。例えば,(1) の 初期状態から,Alloc (1,2) と Alloc (6,8) を実行すると,次のようになる。

 実行後,空きリスト中の組の個数は3となる。

(3) 関数 Free で解放したセルは,空きリストに戻す。例えば,(2) の実行後の 状態から,Free (6,7) を実行すると,次のようになる。

 実行後,解放された“空き”セルの組 {6,7} は,実行前の“空き”セルの 組 {3,5} とつながって一つの連続した“空き”セルの組 {3,7} となるので, 空きリスト中の組の個数は3となる。

〔関数 Alloc の説明〕

 関数 Alloc (始点 P ,終点 P ) の処理手順は,次のとおりである。

 なお,引数の値は,−∞<始点 P ≦終点 P <+∞ を 満たしているものとする。

(1) 空きリスト中に,始点 i ≦始点 P かつ終点 P ≦終点 i を 満たす組{始点 i ,終点 i }が存在すれば (2) へ進む。 存在しなければ,“一部又は全体が割当済み”を表示して,処理を終了する。

(2) 割当てが可能であるので,表1に従って,引数の状況に対応した空きリストの 更新処理を実行して,処理を終了する。

表1 関数 Alloc の空きリスト更新処理

〔関数 Free の説明〕

 関数 Free (始点 P ,終点 P ) の処理手順は,次のとおりである。

 なお,引数の値は,−∞<始点 P ≦終点 P <+∞ を満たしているものとする。

(1) 空きリスト中に,終点 i <始点 P かつ 終点 P <始点 i+1 を 満たす連続する二つの組{始点 i ,終点 i }と{始点 i+1 ,終点 i+1 }が 存在すれば (2) へ進む。存在しなければ,“一部又は全体が割当済みでない”を表示して,処理を終了する。

(2) 解放が可能であるので,表2に従って,引数の状況に対応した空きリストの更新処理を実行して, 処理を終了する。

表2 関数 Free の空きリスト更新処理

設問1 本文中の に入れる正しい答えを, 解答群の中から選べ。

a,b に関する解答群

ア {始点 i ,終点 i+1 }       イ {始点 i ,終点 p

ウ {始点 p ,終点 i+1 }       エ {始点 p ,終点 p

解答 a ←クリックすると正解が表示されます

解答 b ←クリックすると正解が表示されます

基本情報技術者試験


設問2 次のプログラム中の に入れる正しい答えを, 解答群の中から選べ。

 関数 Alloc の説明に基づいて,プログラムを作成した。

 空きリスト中の現在の組の個数は大域整数型変数 N に格納されている。 空きリスト{{始点 1 ,終点 1 },{始点 2 ,終点 2 },…, {始点 N ,終点 N }}については, 始点 i (i:1,2,…,N)の値は大域整数型配列 始点 の要素 始点 [i] に, 終点 i (i:1,2,…,N)の値は大域整数型配列 終点 の要素 終点 [i] に, それぞれ格納されている。これらの配列は,十分に大きいものとする。

〔プログラム〕

c,d に関する解答群 ア 始点[I] ← 始点 P−1      イ 始点[I] ← 終点 P+1

ウ 終点[I] ← 始点 P−1      エ 終点[I] ← 終点 P+1

e に関する解答群

ア I+1,L < N,1      イ I+1,L ≦ N,1

ウ N,L ≧ I+1,−1      エ N,L > I+1,−1

解答 c ←クリックすると正解が表示されます

解答 d ←クリックすると正解が表示されます

解答 e ←クリックすると正解が表示されます

基本情報技術者試験


設問3 次の記述中の に入れる適切な答えを, 解答群の中から選べ。

 このアルゴリズムでは,空きリスト{{始点 1 ,終点 1 }, {始点 2 ,終点 2 },…,{始点 N ,終点 N }}の 始点 1 に値−∞を,終点 N に値+∞をそれぞれ設定している。 このような設定をすることの利点の一つに, という特徴が 挙げられる。

 また,このアルゴリズムでは,空きリスト中の組の個数が変化する。 領域中のセル数が E 個であるとする。このとき,空きリスト中の組の個数は, 最大で となる。 また,E 個の全てのセルが“割当済み”となったとき,空きリスト中の組の 個数は, となる。ここで,整数同士の除算では, 商の小数点以下を切り捨てる。

f に関する解答群

ア 空きリストが空(組の個数が0)にならない

イ 関数 Free の実行時に空きリスト中の組の個数が2以上であることが保証される

ウ 始点 1 又は終点 N の値が変わらない限り領域中に“空き”セルが残っている

エ 領域中の一つの連続した“空き”セルが幾ら長くても一つの組で表せる

g,h に関する解答群

ア 1       イ 2       ウ E÷2+1

エ (E+1)÷2+1       オ E+1       カ E+2

解答 f ←クリックすると正解が表示されます

解答 g ←クリックすると正解が表示されます

解答 h ←クリックすると正解が表示されます


[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]