総視聴再生時間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

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

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

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

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

一覧に戻る

タグ: ,,,

PR広告

フェイスブックコメント

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

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

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

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

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

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

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

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

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