平成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
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 の値は次のとおりに変化する。
A 配列 x の Top から Last までの走査範囲内にある数値を,6 以下の数値の グループと 6 以上の数値のグループの二つに分ける処理を行う。その結果, 配列 x の内容は次のとおりになる。 B を設定して選択処理の2回目に進む。 A 配列 x の Top から Last までの走査範囲内にある数値を,1 以下の数値の グループと 1 以上の数値のグループの二つに分ける処理を行う。 その結果,配列 x の内容は次のとおりになる。
B を設定して選択処理の3回目に進む。 : この選択処理を繰り返して,Top < Last でなくなったときに処理を終了する。 このとき,関数の返却値 x[k] には与えられた数値の中から k 番目に小さい値が 選択されている。 a,b に関する解答群 ウ Top に値 2,Last に値 5 エ Top に値 2,Last に値 6 オ Top に値 3,Last に値 5 カ Top に値 3,Last に値 6
設問2 次の記述中の に入れる正しい答えを, 解答群の中から選べ。 引数で与えられた配列 x の要素番号 1 〜 7 の内容が 1,3,2,4,2,2,2 であり, n が 7,k が 3 のとき,選択処理が終了するまでにプログラム中のαの部分は 回実行され, γの部分は 回実行される。 c,d に関する解答群
設問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 に関する解答群 ウ Top に値 0 が設定される エ 処理が終了しない オ 配列の範囲を越えて参照する
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
©2004-2024 情報処理試験.jp
|
プライバシーポリシー・著作権・リンク
|
お問合わせ
|