情報処理技術者試験の過去問と解説なら「情報処理試験.jp」
[広告] 身体のケア
桜の情報開花予想千鳥ヶ淵隅田公園弘前公園魚の旬年賀はがき
コンサートワクワク学校アルバム大野智櫻井翔相葉雅紀二宮和也松本潤

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

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

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

〔プログラムの説明〕

 n 個の数値が格納されている配列 x と値 k を与えて,k 番目に小さい値を返す関数 Select である。ここで,配列 x の要素番号は1から始まる。また, 配列 x の大きさは,配列に格納される数値の個数分だけ確保されているものとする。 Select の処理の流れを次に示す。

(1) 行番号 3 〜 4

 k 番目に小さい値を選択するために走査する範囲(以下,走査範囲という)の左端を Top,右端を Last とし,まず配列全体を走査範囲とする。

A行番号 5 〜 32

@ 走査範囲に含まれる要素の数が1以下になるまで,A,Bを繰り返す。

A 基準値 Pivot を選び,走査範囲内の値で基準値以下のものを左に, 基準値以上のものを右に集める(行番号 6 〜 24)。

B 走査範囲が基準値以下の値から成るグループと基準値以上の値から成るグループに分割されるので, k 番目に小さい値が含まれるグループを新たな走査範囲とする(行番号 25 〜 3Ø )。

C 繰返しが終了したときに,要素 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回目の@〜B,(2) 選択処理2回目の @〜B,…と実行する。
(1) 選択処理1回目

@ 配列 x の走査範囲を二つの部分に分ける基準値 Pivot に配列 x の3番目の 要素 x[3] の値 6 を設定する。次に,i に Top の値 1,j に Last の値 7 を設定する。

A 配列 x の Top から Last までの走査範囲内にある数値を,6 以下の数値の グループと 6 以上の数値のグループの二つに分ける処理を行う。その結果, 配列 x の内容は次のとおりになる。

3, 5, 1, 4, 2, 7, 6

B を設定して選択処理の2回目に進む。

(2) 選択処理2回目 @ 基準値 Pivot に x[3] の値 1 を設定する。

A 配列 x の Top から Last までの走査範囲内にある数値を,1 以下の数値の グループと 1 以上の数値のグループの二つに分ける処理を行う。 その結果,配列 x の内容は次のとおりになる。

1, 5, 3, 4, 2, 7, 6

B を設定して選択処理の3回目に進む。

(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

情報処理試験.jp


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

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

c,d に関する解答群

ア 1       イ 2       ウ 3       エ 4       オ 5       カ 6

情報処理試験.jp


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

 プログラム中のβの行 x[i] < Pivot を誤って x[i] ≦ Pivot とした。 この場合,引数で与えられた配列 x の要素番号 1 〜 6 の内容が 1,1,1,1,1,1 であり, n が 6,k が 3 のとき, 。また,引数で与えられた配列 x の 要素番号 1 〜 6 の内容が 1,3,2,4,2,2 であり,n が 6,k が 3 のとき,

e,f に関する解答群

ア Last に値 0 が設定される       イ Pivot に値 0 が設定される

ウ Top に値 0 が設定される       エ 処理が終了しない

オ 配列の範囲を越えて参照する


[←前の問題] [次の問題→] [問題一覧表] [分野別] [情報処理試験.jpのTOP]