HOME»基本情報技術者平成27年春期問題»午後問8

基本情報技術者過去問題 平成27年春期 午後問8

⇄問題文と設問を画面2分割で開く⇱問題PDF

問8　データ構造及びアルゴリズム

次のプログラムの説明及びプログラムを読んで，設問1～3に答えよ。

　与えられたn個のデータの中からk番目に小さい値を選択する方法として，クイックソートを応用したアルゴリズムを考える。クイックソートとは，n個のデータをある基準値以下の値のグループと基準値以上の値のグループに分割し(基準値はどちらのグループに入れても構わない)，更にそれぞれのグループで基準値を選んで二つのグループに分割するという処理を繰り返してデータを整列するアルゴリズムである。クイックソートを応用してk番目に小さい値を選択するアルゴリズムでは，データを二つのグループに分割した時点で，求める値はどちらのグループに含まれるかが確定するので，そのグループだけに，更に分割する処理を繰り返し適用する。グループの分割ができなくなった時点で，k番目に小さい値が選択されている。

〔プログラムの説明〕
　n個の数値が格納されている配列xと値kを与えて，k番目に小さい値を返す関数 Select である。ここで，配列xの要素番号は1から始まる。また，配列xの大きさは，配列に格納される数値の個数分だけ確保されているものとする。Select の処理の流れを次に示す。
  • 行番号3～4
    　k番目に小さい値を選択するために走査する範囲(以下，走査範囲という)の左端を Top，右端を Last とし，まず配列全体を走査範囲とする。
  • 行番号5～32
    1. 走査範囲に含まれる要素の数が1以下になるまで，②，③を繰り返す。
    2. 基準値 Pivot を選び，走査範囲内の値で基準値以下のものを左に，基準値以上のものを右に集める(行番号6～24)。
    3. 走査範囲が基準値以下の値から成るグループと基準値以上の値から成るグループに分割されるので，k番目に小さい値が含まれるグループを新たな走査範囲とする(行番号25～30)。
    4. 繰返しが終了したときに，要素 x[k] の値がk番目に小さい値として，選択される。
　Select の引数と返却値の仕様は次のとおりである。

設問1

関数 Select の追跡に関する次の記述中の　に入れる正しい答えを，解答群の中から選べ。

　関数 Select の引数で与えられた配列xの要素番号1～7の内容が3，5，6，4，7，2，1であり，nが7，kが3のとき，配列xの走査範囲の左端 Top と右端 Last の値は次のとおりに変化する。
  • Top と Last の初期値は，それぞれ1と7である。
  • Top＜Last が成り立つ間，次に示す(1)選択処理1回目の①～③，(2)選択処理2回目の①～③，…と実行する。
  • 選択処理1回目
    1. 配列xの走査範囲を二つの部分に分ける基準値 Pivot に配列xの3番目の要素x[3]の値 6 を設定する。次に，iに Top の値 1，jに Last の値 7 を設定する。
    2. 配列xの Top から Last までの走査範囲内にある数値を，6以下の数値のグループと6以上の数値のグループの二つに分ける処理を行う。その結果，配列xの内容は次のとおりになる。
      　3，5，1，4，2，7，6
    3. aを設定して選択処理の2回目に進む。
  • 選択処理2回目
    1. 基準値 Pivot に x[3] の値 1 を設定する。
    2. 配列xの Top から Last までの走査範囲内にある数値を，1以下の数値のグループと1以上の数値のグループの二つに分ける処理を行う。その結果，配列xの内容は次のとおりになる。
      　1，5，3，4，2，7，6
    3. bを設定して選択処理の3回目に進む。
  • 選択処理3回目
    　　　⋮
　この選択処理を繰り返して，Top＜Last でなくなったときに処理を終了する。このとき，関数の返却値 x[k] には与えられた数値の中からk番目に小さい値が選択されている。
a，b に関する解答群
  • Topに値1，Lastに値5
  • Topに値1，Lastに値6
  • Topに値2，Lastに値5
  • Topに値2，Lastに値6
  • Topに値3，Lastに値5
  • Topに値3，Lastに値6

解答選択欄

  • a:
  • b:

解答

  • a=ア
  • b=ウ

解説

プログラムを見ると、Top=1、Last=nを初期値として、TopがLastより小さい間、以下の処理を繰り返しています。基本的な流れを確認しておきましょう。
10～12行目
x[i] が Pivot 以上になるまで i を進めます。
13～15行目
x[j] が Pivot 以下になるまで j を戻します。
16～18行目
i が j 以上ならばループを抜け、25～30行目のTopとLastを再設定する処理に移ります。
19～23行目
x[i] と x[j] を交換します。その後、iに1を足し、jから1を引きます。
15～30行目
iがk以下ならば探索範囲の先頭を j+1 に変更し、jがk以上ならば探索範囲の末尾を i-1 に変更します。
〔aについて〕
配列xの要素は[3，5，6，4，7，2，1]で、k=3なので、1回目の選択処理では Pivot の値が x[3]=6 になります。
  1. iが1から3まで進み、jは7のままです。
    3，5，6(i)，4，7，2，1(j)
  2. x[i] と x[j] を交換（赤字部分）し、i+1、j-1を行うと、以下のようになります。
    3，5，1，4(i)，7，2(j)，6
  3. iが7の位置まで進み、jは6の位置のままです。
    3，5，1，4，7(i)，2(j)，6
  4. x[i] と x[j] を交換し、i+1、j-1を行うと、以下のようになります。
    3，5，1，4，2(j)，7(i)，6
  5. x[i]≧6、x[j]≦6なので、iとjはどちらも移動しません。
  6. i≧j となったのでbreak文でループを抜けます。この時点で、i=6、j=5です。
  7. i＞3 なのでTopは1のまま、j≧3 なのでLastには i-1、すなわち「6－1＝5」が格納されます。
したがって、選択処理1回目の最後では、Topに1、Lastに5を設定して次のループに進みます。

∴a＝ア：Topに値1，Lastに値5

〔bについて〕
配列xの要素は[3，5，1，4，2，7，6]なので、2回目の選択処理では Pivot の値が x[3]=1 になります。
  1. iは1のまま、jは5から3まで戻ります。
    3(i)，5，1(j)，4，2，7，6
  2. x[i] と x[j] を交換し、i+1、j-1を行うと、以下のようになります。
    1，5(i,j)，3，4，2，7，6
  3. iは2のまま、jは1まで戻ります。
    1(j)，5(i)，3，4，2，7，6
  4. i≧j となったのでbreak文でループを抜けます。この時点で、i=2、j=1です。
  5. i≦3 なのでTopには j+1、すなわち「1＋1＝2」が格納されます。j＜3 なのでLastは5のままです。
したがって、選択処理2回目の最後では、Topに2、Lastに5を設定して次のループに進みます。

∴b＝ウ：Topに値2，Lastに値5

設問2

次の記述中の　に入れる正しい答えを，解答群の中から選べ。

　引数で与えられた配列xの要素番号1～7の内容が1，3，2，4，2，2，2であり，nが 7，kが 3 のとき，選択処理が終了するまでにプログラム中のαの部分はc回実行され，γの部分はd回実行される。
c，d に関する解答群
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

解答選択欄

  • c:
  • d:

解答

  • c=イ
  • d=エ

解説

〔c，dについて〕
配列xの要素は[1，3，2，4，2，2，2]で、k=3なので、1回目の選択処理では Pivot の値が x[3]=2 になります。設問1と同じように処理をトレースしていきます。
  1. Topに1を、Lastに7を設定します（α）。
  2. iが1から2まで進み、jは7のままです。
    1，3(i)，2，4，2，2，2(j)
  3. x[i] と x[j] を交換し、i+1、j-1を行うと、以下のようになります。
    1，2，2(i)，4，2，2(j)，3
  4. iとjともに変化せずそのままの位置です。
    1，2，2(i)，4，2，2(j)，3
  5. x[i] と x[j] を交換し、i+1、j-1を行うと、以下のようになります。
    1，2，2，4(i)，2(j)，2，3
  6. iとjともに変化せずそのままの位置です。
    1，2，2，4(i)，2(j)，2，3
  7. x[i] と x[j] を交換し、i+1、j-1を行うと、以下のようになります。
    1，2，2，2(j)，4(i)，2，3
  8. x[i]≧2、x[j]≦2なので、iとjともに移動せずそのままの位置です。
  9. i≧j となったのでbreak文でループを抜けます。この時点で、i=5、j=4です。
  10. i＞3 なのでTopは1のまま、j≧3 なのでLastには i-1、すなわち「5－1＝4」が格納されます。
選択処理2回目に入ります。Pivot は1回目と同じ2です。
  1. Topに1を、Lastに4を設定します（α）。
  2. iが1から2まで進み、jは4のままです。
    1，2(i)，2，2(j)，4，2，3
  3. x[i] と x[j] を交換し、i+1、j-1を行うと、以下のようになります。
    1，2，2(i,j)，2，4，2，3
  4. x[i]≧2、x[j]≦2なので、iとjともに移動せずそのままの位置です。
  5. i≧jとなったのでbreak文でループを抜けます。この時点で、i=3、j=3です。
  6. i≦3 なのでTopなのでTopには j+1、すなわち「3＋1＝4」が格納されます。j≧3なのでLastには i-1、すなわち「3－1＝2」が格納されます。
Top＜Lastが偽となるので選択処理は終了し、関数の返却値として x[3]の値である2が返されます。

αの処理は選択処理を行った回数だけ実行されるので2回、γの処理は配列要素の交換を行った回数だけ実行されるので4回となります。

∴c＝イ：2
　d＝エ：4

設問3

次の記述中の　に入れる正しい答えを，解答群の中から選べ。

　プログラム中のβの行 x[i]＜Pivot を誤って x[i]≦Pivot とした。この場合，引数で与えられた配列xの要素番号1～6の内容が1，1，1，1，1，1であり，nが 6，kが 3 のときe。また，引数で与えられた配列xの要素番号1～6の内容が1，3，2，4，2，2であり，n が6，k が3のとき，f。
e，f に関する解答群
  • Lastに値 0 が設定される
  • Pivotに値 0 が設定される
  • Topに値 0 が設定される
  • 処理が終了しない
  • 配列の範囲を越えて参照する

解答選択欄

  • e:
  • f:

解答

  • e=オ
  • f=エ

解説

〔eについて〕
x[i]≦Pivot とすると配列要素の値がPivotを超えるまで i が進むことになります。配列要素が[1，1，1，1，1，1]、Pivotが1の場合、iは配列要素の末尾(n)を越えて増加し、定義外の要素である x[7] を参照することになります。これにより参照エラーを起こします。

∴e＝オ：配列の範囲を越えて参照する

〔fについて〕
配列要素が[1，3，2，4，2，2]の場合、次のように処理が進みます。

選択処理1回目の Pivot は x[2]=2 です。
  1. Topに1を、Lastに6を設定します。
  2. iが1から2の位置まで進み、jは6のままです。
    1，3(i)，2，4，2，2(j)
  3. x[i] と x[j] を交換（赤字部分）し、i+1、j-1を行うと、以下のようになります。
    1，2，2(i)，4，2(j)，3
  4. iが4の位置まで進み、jは5のままです。
    1，2，2，4(i)，2(j)，3
  5. x[i] と x[j] を交換（赤字部分）し、i+1、j-1を行うと、以下のようになります。
    1，2，2，2(j)，4(i)，3
  6. x[i]≧2、x[j]≦2なので、iとjともに移動せずそのままの位置です。
  7. i≧j となったのでbreak文でループを抜けます。この時点で、i=5、j=4です。
  8. i＞3 なのでTopは1のまま、j≧3なのでLastには i-1、すなわち「5－1＝4」が格納されます。
選択処理の2回目に入ります。Pivot は2です。
  1. Topに1を、Lastに4を設定します。
  2. iが1から5の位置まで進み、jは4のままです。
    1，2，2，2(j)，4(i)，3
  3. x[i]≧2、x[j]≦2なので、iとjともに移動せずそのままの位置です。
  4. i≧j となったのでbreak文でループを抜けます。この時点で、i=5、j=4です。
  5. i＞3 なのでTopは1のまま、j≧3 なのでLastには i-1、すなわち「5－1＝4」が格納されます。
選択処理の3回目に移りますが、TopとLastの値、配列要素が選択処理2回目開始時点と同一なので以後同じ処理が永久に続きます。つまり、処理が終了しません。

∴f＝エ：処理が終了しない

平成27年春期 午後問題一覧

問1　問2　問3　問4　問5　問6　問7　問8　問9　問10　問11　問12　問13　採点講評
© 2010-2024　基本情報技術者試験ドットコム　All Rights Reserved.
▲
Pagetop