基本情報技術者 2014年春期午後問08

次のアルゴリズムの説明を読んで、設問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に従って、引数の状況に対応した空きリストの更新処理を実行して、処理を終了する。

〔関数Freeの説明〕　関数Free(

始 点_{p}

終 点_{p}

)の処理手順は、次のとおりである。　なお、引数の値は、-∞ <

始 点_{p}

≦

終 点_{p}

< +∞を満たしているものとする。 (1) 空きリスト中に、

終 点_{i}

始 点_{p}

かつ

終 点_{p}

始 点_{i + 1}

を満たす連続する二つの組{

始 点_{i}

終 点_{i}

}と{

始 点_{i + 1}

終 点_{i + 1}

}が存在すれば(2)へ進む。存在しなければ、“一部又は全体が割当済みでない”を表示して、処理を終了する。 (2) 解放が可能であるので、表2に従って、引数の状況に対応した空きリストの更新処理を実行して、処理を終了する。

設問1：

問題文を見る

　本文中のに入れる正しい答えを、解答群の中から選べ。　 a, bに関する解答群　ア：{

始 点_{i}

終 点_{i + 1}

} 　イ：{

始 点_{i}

終 点_{p}

} 　ウ：{

始 点_{p}

終 点_{i + 1}

} 　エ：{

始 点_{p}

終 点_{p}

}

模範解答

a：ア、b：エ

解説

解答の導き方

空きリスト（空いているセルが連続する範囲を記録した一覧）では、各組の始点から終点までが空きです。セルの位置は整数なので、たとえば終点が

5

の組のすぐ隣は、始点が

6

の組です。

関数Freeでは、解放する範囲が空きリスト中の二つの組の間にあるかを確認します。本文の「終点

_{i}

< 始点

_{p}

」かつ「終点

_{p}

< 始点

_{i + 1}

」という条件から、解放する範囲は左側の空き範囲と右側の空き範囲の間にあります。そのため、解放する範囲と左右の空き範囲がつながるかどうかで、更新方法が決まります。

まず、表2の最初の行を見ます。左側の組の終点が解放範囲の直前で、解放範囲の終点が右側の組の直前なら、三つの範囲はすき間なくつながります。したがって、一つにまとめた範囲は左側の始点から右側の終点までです。空欄aは {

始 点_{i}

終 点_{i + 1}

} となるため、選択肢はアです。

一方、表2の最後の行では、解放範囲と左右の組の間にどちらもすき間があります。この場合、解放した範囲だけで新しい組を作り、左側の組の直後に挿入します。新しい組は {

始 点_{p}

終 点_{p}

} なので、空欄bはエです。

表2の途中の二行も、同じ考え方です。左側だけとつながる場合は、左側の始点から解放範囲の終点までを一つにします。右側だけとつながる場合は、解放範囲の始点から右側の終点までを一つにします。

たとえば本文のFree(6, 7)では、左側の組{3, 5}とはつながりますが、右側の組{9, ＋∞}とはつながりません。

5 = 6 - 1

である一方、

7 + 1 < 9

だからです。そのため、左側の組を{3, 7}に置き換えます。このように、どちらの組とつながるかを確認すれば、表2の更新方法を判断できます。

誤りやすいポイント

空きリストの組は、始点と終点のセルを含む範囲です。隣り合うかどうかは、終点と始点の差が $1$ かどうかで判断します。
解放範囲が左右の組の間にあるからといって、必ず左右の組と一つになるわけではありません。解放範囲の両端が、それぞれの組に隣接するかを確認します。
空欄aでは、左側の始点と右側の終点を使います。解放範囲の始点や終点だけを使うと、つながった空き範囲全体を表せません。
左右どちらともつながらない場合、解放範囲を既存の組に混ぜず、解放範囲そのものを新しい組として追加します。

FAQ

Q: なぜFreeでは、二つの組の間に解放範囲があるかを確認するのですか？
A: 空きリストに載っていないセルは割当済みです。解放範囲が二つの空き範囲の間にあれば、その範囲は空きリストに含まれていないため、割当済みの範囲だと判断できます。

Q: なぜ隣接の条件に

- 1

や

+ 1

が出てくるのですか？
A: セル位置は連続する整数だからです。終点が

5

の範囲の次のセルは

6

なので、終点が始点の

1

手前なら、二つの範囲は隣接しています。

Q: 左側だけとつながる場合、どの範囲を一つにまとめますか？
A: 左側の組の始点から、解放範囲の終点までです。本文の例では、{3, 5}と解放範囲{6, 7}がつながるため、{3, 7}になります。

関連キーワード: 空きリスト、区間管理、動的割当て、データ構造、境界条件

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問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：ウ

解説

解答の導き方

空きリストは、空いているセルの範囲を「始点と終点の組」で表します。配列は、番号を使って値をしまっておく場所です。このプログラムでは、

I

番目の組の始点を始点[I]に、終点を終点[I]に格納しています。また、組の個数は

N

です。

まず、表1の4通りの状況を、空き範囲のどこを割り当てるかに分けて考えます。割当てる範囲の始点を始点P、終点を終点Pとします。

空き範囲の全部を割り当てる場合
空き範囲の組を取り除きます。組を詰める処理は、問題文のプログラムに示されています。
空き範囲の先頭側を割り当てる場合
条件は、始点[I]＝始点Pかつ終点P＜終点[I]です。割当てた部分のすぐ後ろから、空き範囲が残ります。
例えば、空き範囲が{3, 8}で、Alloc(3, 5)を行うと、残る空き範囲は{6, 8}です。したがって、残った範囲の始点である終点P＋1を始点[I]に設定します。
よって、cには「始点[I] ← 終点P + 1」を選びます。
空き範囲の末尾側を割り当てる場合
条件は、始点[I]＜始点Pかつ終点P＝終点[I]です。割当てた部分の手前に、空き範囲が残ります。
例えば、空き範囲が{3, 8}で、Alloc(5, 8)を行うと、残る空き範囲は{3, 4}です。したがって、残った範囲の終点である始点P−1を終点[I]に設定します。
よって、dには「終点[I] ← 始点P − 1」を選びます。
空き範囲の途中を割り当てる場合
条件は、始点[I]＜始点Pかつ終点P＜終点[I]です。割当てる部分の前後に、空き範囲が二つ残ります。
例えば、空き範囲が{3, 8}で、Alloc(5, 6)を行うと、{3, 4}と{7, 8}が残ります。プログラムは、元の組を前側の範囲{3, 4}にし、その直後に後ろ側の範囲{7, 8}を挿入します。

挿入場所には、すでに後続の組があるかもしれません。そのため、後続の組を1つ後ろへ移動させて場所を空けます。移動先はL＋1ですから、始点[I+1]から順に前向きに移動すると、移動元の値を先に上書きするおそれがあります。そこで、末尾の組から逆向きに移動します。

ループは $L = N$ から始め、 $L \geq I + 1$ の間、 $L$ を1ずつ減らします。つまり、「L：N, L ≧ I+1, −1」のウが当てはまります。移動が終わったら、始点[I+1]と終点[I+1]に後ろ側の範囲を設定し、 $N$ を1増やします。

誤りやすいポイント

空き範囲の先頭側を割り当てるときに、残る範囲の終点を変えようとしないでください。先頭部分がなくなるため、変えるのは始点[I]です。
空き範囲の末尾側を割り当てるときは、残る範囲の始点ではなく終点[I]を変えます。
セル位置は連続する整数です。そのため、割当てた範囲の隣に残るセルは、始点P−1または終点P＋1です。
組を挿入するための移動は、後ろから行います。前から移動すると、まだ移していない組の値を上書きする可能性があります。
途中への挿入では、後続の組がない場合もあります。その場合、 $L = N$ から始めたループの条件が最初から成り立たず、移動を行わずに新しい組を設定できます。

FAQ

Q: なぜ、割当て範囲の隣の位置に「＋1」や「−1」を使うのですか？
A: セル位置は整数で連続しているためです。終点Pの次のセルは終点P＋1、始点Pの前のセルは始点P−1になります。

Q: 途中に組を挿入するとき、なぜ後ろから移動するのですか？
A: 移動先が移動元より1つ後ろだからです。前から移すと、移動先にある次の組を上書きしてしまうことがあります。後ろから移せば、まだ移していない値を保ったまま場所を空けられます。

Q: 途中への挿入で、

N

を1増やすのはなぜですか？
A: それまで1つだった空き範囲が、割当てによって前後の2つに分かれるため、空きリストの組が1つ増えるからです。

関連キーワード: 配列、空きリスト、区間、挿入、シフト操作、メモリ管理

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問3：

問題文を見る

　次の記述中のに入れる適切な答えを、解答群の中から選べ。　　このアルゴリズムでは、空きリスト{ {

始 点_{1}

終 点_{1}

}, {

始 点_{2}

終 点_{2}

}, …, {

始 点_{N}

終 点_{N}

} }の

始 点_{1}

に値-∞を、

終 点_{N}

に値+∞をそれぞれ設定している。このような設定をすることの利点の一つに、fという特徴が挙げられる。　また、このアルゴリズムでは、空きリスト中の組の個数が変化する。領域中のセル数がE個であるとする。このとき、空きリスト中の組の個数は、最大でgとなる。また、E個の全てのセルが“割当済み”となったとき、空きリスト中の組の個数は、hとなる。ここで、整数同士の除算では、商の小数点以下を切り捨てる。　 fに関する解答群　ア：空きリストが空（組の個数が0）にならない　イ：関数Freeの実行時に空きリスト中の組の個数が2以上であることが保証される　ウ：

始 点_{1}

又は

終 点_{N}

の値が変わらない限り領域中に“空き”セルが残っている　エ：領域中の一つの連続した“空き”セルが幾ら長くても一つの組で表せる　 g, hに関する解答群　ア：1 　イ：2 　ウ：E ÷ 2 + 1 　エ：(E + 1) ÷ 2 + 1 　オ：E + 1 　カ：E + 2

模範解答

f：ア、g：エ、h：イ

解説

解答の導き方

f：端の「空き」をどう扱うかを考えます。

空きリストは、連続した“空き”セルのまとまりを一つの組で表します。問題文では、領域の外側も“空き”セルとして扱い、最初の組の始点を

- \infty

、最後の組の終点を

+ \infty

にしています。これらは実際のセル位置ではなく、領域の外側まで空きが続くことを示す境界の目印です。

関数Allocの引数は有限のセル位置なので、領域の外側まで割当て済みにすることはありません。そのため、領域内のセルがすべて“割当済み”になっても、領域の外側の“空き”は残ります。空きリストの組がすべてなくなることはないので、fは「空きリストが空（組の個数が0）にならない」です。

一方、関数Freeを呼び出したときに、空きリストの組が必ず2以上とはいえません。例えば、最初の状態では組は1つです。この状態でFreeを呼び出しても、解放できる条件を満たさず、エラーになります。したがって、イのように「関数Freeの実行時」に常に2以上と保証されるわけではありません。

g：空きリストの組を最大にする並びを考えます。

空きの組が隣り合っている場合、その間には少なくとも1つの“割当済み”セルが必要です。また、最初と最後の組は領域の外側の空きも含められますが、その間にある組は領域内に少なくとも1つの“空き”セルが必要です。

空きリストの組が

N

個あるとすると、間の

N - 2

個の組には少なくとも

N - 2

個の“空き”セルが必要です。また、組と組の間には少なくとも

N - 1

個の“割当済み”セルが必要です。これらは別々のセルなので、領域のセル数

E

について、

E \geq (N - 2) + (N - 1) = 2 N - 3

となります。これを

N

について整理すると、

N \leq ⌊ \frac{E + 3}{2} ⌋ = ⌊ \frac{E + 1}{2} ⌋ + 1

です。ここで、

⌊ ⌋

は小数点以下を切り捨てることを表します。空きセルと割当済みセルをできるだけ交互に並べると、この上限に達します。したがって、最大の組の個数は、選択肢の「

(E + 1) \div 2 + 1

」です。

h：領域内のセルがすべて“割当済み”の場合を考えます。

領域内には“空き”セルがありませんが、領域の外側は“空き”のままです。領域の左側の空きと右側の空きは、領域内の“割当済み”セルに隔てられているため、別々の組になります。よって、空きリスト中の組の個数は2です。

誤りやすいポイント

“割当済み”セルが増えると、空きリストの組の個数が必ず減ると考えないようにします。空きが分断されると、組の個数は増えることがあります。
領域内のセルがすべて“割当済み”でも、領域外の空きが残ります。そのため、空きリストが空になるわけではありません。
gの計算では、領域の外側にある空きも最初と最後の組に含まれることを忘れないようにします。また、整数同士の除算は小数点以下を切り捨てます。

FAQ

- \infty

と

+ \infty

は、実際に割当てや解放をするセル位置ですか？
A: いいえ。領域の外側まで“空き”が続くことを示す境界の目印です。関数の引数は有限のセル位置なので、この外側を割当ての対象にはしません。

Q: 空きリストの組の個数は、領域内の空きセルの数ですか？
A: いいえ。組の個数は、連続した“空き”セルのまとまりの数です。連続した空きが長くても、まとまりが一つなら組も一つです。

Q: 全てのセルが“割当済み”なのに、空きリストに組が残るのはなぜですか？
A: 領域の外側のセルは“空き”として扱うためです。領域内の“割当済み”セルを挟んで、左側と右側の空きが別の組として残ります。

関連キーワード: 空きリスト、連続区間、番兵、境界値、整数除算

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

基本情報技術者 2014年 春期 午後 問08

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

.css-epvm6{white-space:nowrap;}設問1：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問2：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問3：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

基本情報技術者 2014年春期午後問08

設問1：