総視聴再生時間43万分以上(2017年5月13日現在)の動画で基本情報技術者試験の過去問&キーワード解説!スキマ時間に動画!〜これじょIT〜

PR広告

平成27年度春 基本情報技術者試験 午後 問8 データ構造及びアルゴリズム 設問2

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

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

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

〔プログラムの説明〕

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

(1) 行番号3~4

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

(2) 行番号5~32

① 走査範囲に含まれる要素の数が1以下になるまで、②、③を繰り返す。

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

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

④ 繰返しが終了したときに、要素 x[k] の値がk番目に小さい値として、選択される。

 Select の引数と返却値の仕様は次のとおりである。

平成27年度春 基本情報技術者試験 午後 問8 データ構造及びアルゴリズム 図

【プログラム】

(行番号)

1  ○整数型: Select(整数型: x[], 整数型: n, 整数型: k)
2  ○整数型: Top, Last, Pivot, i, j, work
3  ・Top ← 1 /* 走査範囲の左端の初期値を設定 */
4  ・Last ← n /* 走査範囲の右端の初期値を設定 */
5  ■Top < Last 
6  |・Pivot ← x[k] /* ここからα /*
7  |:i ← Top /* ここもα */
8  |:j ← Last /* ここまでα */
9  |■true
10 ||■x[i] < Pivot /* ここはβ */
11 |||・i ← i + 1
12 ||■
13 ||■Pivot < x[j] /* ここはβ */
14 |||・j ← j - 1
15 ||■
16 ||▲i ≧ j
17 |||・break
18 ||▼
19 ||・work ← x[i] /* ここからγ */
20 ||・x[i] ← x[j]
21 ||・x[j] ← work
22 ||・i ← i + 1
23 ||・j ← j - 1
24 |■
25 |▲i ≦ k
26 ||・Top ← j + 1
27 |▼
28 |▲k ≦ j
29 ||・Last ← i - 1
30 |▼
31 ■
32 ・return x[k]

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

解説

設問1と同じように配列の動きに着目します。配列x {1, 3, 2, 4, 2, 2, 2}

基準値(Pivot)はx[3] = 2なので、配列の左側から2以上の数値、配列の右側から2以下の数値を探します。(α1回目)※2以下なので「2」も含まれます。

配列x {1, 3, 2, 4, 2, 2, 2}

左から(i=1)2以上の数値はx[2]=3、右から(j=7)2以下の数値はx[7]=2 これらを交換します。(γ1回目)

配列x {1, 3, 2, 4, 2, 2, 2}

となります。次に、左側は「3番目から(i=3)」2以上の数値、右側は「6番目から(j=6)」2以下の数値を探します。

配列x {1, 2, 2, 4, 2, 2, 3}

左から(i=3)2以上の数値はx[3]=2、右から(j=6)2以下の数値はx[6]=2 これらを交換します。(γ2回目)

配列x {1, 2, 2, 4, 2, 2, 3}

となります。次に、左側は「4番目から(i=4)」2以上の数値、右側は「5番目から(j=5)」2以下の数値を探します。

配列x {1, 2, 2, 4, 2, 2, 3}

左から(i=4)2以上の数値はx[4]=4、右から(j=5)2以下の数値はx[5]=2 これらを交換します。(γ3回目)

配列x {1, 2, 2, 2, 4, 2, 3}

となります。次に、左側は「5番目から(i=5)」2以上の数値、右側は「4番目から(j=4)」2以下の数値を探しますが、プログラムをみると左側からの番号iが、右側の番号j以上になると(i≧j)、ループを抜けます。

ループを抜けた後、TopとLeftの値を更新します。

i≦kのときはTopの値がj+1となります。現状i=5、k=3なので、TopはそのままTop = 1となります。

k≦jのときはLeftの値がi-1となります。現状j=4、k=3なので、i=5であるためLeftにはi-1=5-1=4が入ります。

Top = 1, Left = 4, k = 3, Pivot = x[3] = 2 として再度プログラムが実行されます。(α2回目)

配列x {1, 2, 2, 2, 4, 2, 3}

基準値(Pivot)はx[3] = 2なので、配列の左側(Top = 1)から2以上の数値、配列の4番目(Left = 4)から2以下の数値を探します。

配列x {1, 2, 2, 2, 4, 2, 3}

左から(i=1)2以上の数値はx[2]=2、右から(j=4)2以下の数値はx[4]=2 これらを交換します。(γ4回目)

配列x {1, 2, 2, 2, 4, 2, 3}

となります。次に、左側は「3番目から(i=3)」2以上の数値、右側も「3番目から(j=3)」1以下の数値を探します。i+1, j-1となったあとプログラムをみると左側からの番号iが、右側の番号j以上になると(i≧j)、ループを抜けます。

このあと、Top>Leftとなり、終了。

答えは「引数で与えられた配列xの要素番号1~7の内容が1, 3, 2, 4, 2, 2, 2であり、nが 7、kが 3 のとき、選択処理が終了するまでにプログラム中のαの部分は4回実行され、γの部分は2回実行される。」なので、【 c 】に「イ : 2」【 d 】に「エ : 4」が入ります!

平成27年度春 基本情報技術者試験 午後 問8 データ構造及びアルゴリズム 目次

  1. 問題文とキーワード
  2. 設問1
  3. 設問2
  4. 設問3

一覧に戻る

タグ: ,,,

PR広告

フェイスブックコメント

平成28年度秋 基本情報技術者試験 午後 テキスト・動画解説

平成28年度秋 基本情報技術者試験 午前 テキスト・動画解説

平成28年度春 基本情報技術者試験 午後 テキスト・動画解説

平成28年度春 基本情報技術者試験 午前 テキスト・動画解説

平成27年度秋 基本情報技術者試験 午後 テキスト・動画解説

平成27年度春 基本情報技術者試験 午後 テキスト・動画解説

平成27年度春 基本情報技術者試験 午前 テキスト・動画解説

平成26年度秋 基本情報技術者試験 午前 テキスト・動画解説

平成26年度春 基本情報技術者試験 午前 テキスト・動画解説