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

PR広告

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

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

設問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 を設定する。

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

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

③【 a 】を設定して選択処理の2回目に進む。

(2) 選択処理2回目

① 基準値 Pivot に x[3] の値 1 を設定する。

② 配列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

解説

配列xの変化を追います。基準値(Pivot)はx[3] = 6なので、配列の左側から6以上の数値、配列の右側から6以下の数値を探します。

配列x {3, 5, 6, 4, 7, 2, 1}

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

配列x {3, 5, 1, 4, 7, 2, 6}

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

配列x {3, 5, 1, 4, 7, 2, 6}

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

配列x {3, 5, 1, 4, 2, 7, 6}

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

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

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

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

ここが「③【 a 】を設定して選択処理の3回目に進む。」の部分に該当します。答えは「Topに値1、Lastに値5を設定して選択処理の2回目に進む。」となり、【 a 】には「ア : Topに値1、Lastに値5」が入ります。

Top = 1, Left = 5, k = 3, Pivot = x[3] = 1 として再度プログラムが実行されます。

配列x {3, 5, 1, 4, 2, 7, 6}

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

配列x {3, 5, 1, 4, 2, 7, 6}

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

配列x {1, 5, 3, 4, 2, 7, 6}

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

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

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

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

ここが「③【 b 】を設定して選択処理の3回目に進む。」の部分に該当します。答えは「Topに値2、Lastに値5を設定して選択処理の3回目に進む。」となり、【 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

解説

設問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」が入ります!

設問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 が設定される
  • エ : 処理が終了しない
  • オ : 配列の範囲を越えて参照する

解説

配列x {1, 1, 1, 1, 1, 1}のとき、プログラム中のβの行 x[i]<Pivot を誤って x[i]≦Pivot とした場合、左側から走査するときにx[i]<Pivotであれば、i = 1のときにループを抜け、次の処理に移行しますが、 x[i]≦Pivotの場合、次の値を見に行きます(i = 2となる)これらは、iが進んでも同様です。最後のi = 6のときにも次の値x[7]を参照します。これは配列の範囲を越えています。従って【 e 】には「オ : 配列の範囲を越えて参照する」が入ります!

配列x {1, 3, 2, 4, 2, 2} n = 6, k = 3のとき、プログラム中のβの行 x[i]<Pivot を誤って x[i]≦Pivot とした場合、x[3] = 2となり、Pivotは2です。

x[i]<Pivot であれば、左側から走査するときに数値が2以上であれば、交換対象としますが、誤って x[i]≦Pivot としているので、3以上の数値しか、交換対象としません。右側からの走査は、今までと変わらず2以下となります。

上記を前提すると、左側はx[2] = 3(i = 2)、右側はx[6] = 2(j = 6)を交換対象とします。交換後の配列xは{1, 2, 2, 4, 2, 3}となります。

次に左側からi = 3から走査を開始します。3以上となるのはx[4] = 4(i = 4)となり、右側はj = 5から走査を開始します。2以下となるのはx[5] = 2(j = 5)となり、この2つの値を交換します。すると、配列xは{1, 2, 2, 2, 4, 3}となります。

次に左側からi = 5から走査を開始します。3以上となるのはx[5] = 4(i = 5)となり、右側はj = 4から走査を開始します。2以下となるのはx[4] = 2(j = 4)となりますが、i ≧ j となっているためにループを抜けます。

この場合、i = 5であるため、i ≦ k が成り立たない(k = 3)ので、Topはそのままです。

また、j = 4であるため、k ≦ j が成り立つ(k = 3)ので、Leftは、i - 1の値、5 - 1 = 4となります。

Top = 1, Left = 4となり1回目のループ終了

2回目のループです。配列x {1, 2, 2, 2, 4, 3}の左側から3以上の数を走査します。x[5] = 4となります。右側から2以下の数値を走査します。x[4] = 2となります。ここで i ≧ j となっているためにループを抜けます。この場合、i = 5であるため、i ≦ k が成り立たない(k = 3)ので、Topはそのままです。また、j = 4であるため、k ≦ j が成り立つ(k = 3)ので、Leftは、i - 1の値、5 - 1 = 4となります。

値は2回目のループが始まった時から変わりません。もう一度プログラムを動作させても、同じことを繰り返します。従って【 f 】には「エ : 処理が終了しない」が入ります.

タグ: ,,,

PR広告

フェイスブックコメント

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

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

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

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

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

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

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

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

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