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

問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以下になるまで,A,Bを繰り返す。
    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回目の@〜B,(2)選択処理2回目の@〜B,…と実行する。
  • 選択処理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=

解説

この設問の解説はまだありません。

設問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=

解説

この設問の解説はまだありません。

設問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=

解説

この設問の解説はまだありません。
【27年春期 午後問題】
 問1 問2 問3 問4 問5 問6 問7 問8 問9 問10 問11 問12 問13
© 2010-2019 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop