FE22春後問8

FE22春後問8

基本情報技術者試験平成22年度春午後問8


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


プログラムの説明〕

 プログラム Sort は配列に格納された整数値のデータを再帰的に分割し,分割したデータの値の大小を比較しながら併合していくことでデータを昇順に整列するプログラムである。Sort は併合に副プログラム Merge を使用する。


(1)num 個(num≧1)のデータを配列 list に格納して Sort を呼び出すと,整列された結果が配列 list に返却される。
(2)Sortでは,次の手順で配列 list に格納された整数値のデータを整列する。
[1] 配列 list に格納されているデータを,先頭から num / 2 個と残り num - num / 2 個とに分割して,二つの配列 slist1 と slist2 に格納し,それぞれの配列に対して再帰的に Sort を呼び出す。ここで,配列 slist1 と slist2 の大きさは省略されているが,必要な領域は確保されている。この再帰的な呼出しは,引数で渡される配列 listデータの個数が 1 になると終了する。
[2] Merge を使用し,二つの配列 slist1 と slist2 を併合して一つの配列 list にする。
(3)Merge では,次の手順で,整列済の二つの配列 slist1 と slist2 を併合し,整列した一つの配列 list を作成する。  
[1] 配列 slist1 又は slist2 のどちらか一方の要素がなくなるまで,次の [2] を繰り返す。
[2] 配列slist1とslist2の要素を順に比較して,小さい方から順に配列listに格納する。
[3] 配列 slist1 又は slist2 の残った要素を配列 list に追加する。
(4)Sort と Merge の引数の仕様を表 1,2 に示す。配列の添字は 0 から始まる。

表1 Sortの引数の仕様

引数名/返却値 データ 入力/出力 意味
list[ ] 整数型 入力及び出力 データが格納されている 1 次元配列
num 整数型 入力 配列 listデータの個数


表2 Mergeの引数の仕様

引数名/返却値 データ 入力/出力 意味
slist1[ ] 整数型 入力 整列済のデータが格納されている 1 次元配列
num1 整数型 入力 配列 slist1 のデータの個数
slist2[ ] 整数型 入力 整列済のデータが格納されている 1 次元配列
num2 整数型 入力 配列 slist2 のデータの個数
list[ ] 整数型 出力 併合したデータを格納する 1 次元配列


 次のデータを例にして,整列処理の流れを図に示す。

 配列 listデータ:5,7,4,2,3,8,1

f:id:tamagopanda:20100819230332p:image

プログラム

f:id:tamagopanda:20100819231348p:image

f:id:tamagopanda:20100819231349p:image


設問1

 プログラム中の [   ] に入れる正しい答えを,解答群の中から選べ。

a に関する解答群
ア num ≧ 0
イ num ≧ 1
ウ num > 1
エ num > 2
b に関する解答群
ア list[i]
イ list[num+i]
ウ list[num1+i]
エ list[num2+i]
c に関する解答群
ア (i < num1)and(j < num2)
イ (i < num1)or(j < num2)
ウ (j < num1)and(i < num2)
エ (j < num1)or(i < num2)
オ (i+j)<(num1+num2)
カ (i+j)≦(num1+num2)
キ (i+j)>(num1+num2)
ク (i+j)≧(num1+num2)

設問2

 最初に与えられた配列 listデータが次の場合,プログラム Sort のαにおける配列 list の内容の移り変わりとして正しい答えを,解答群の中から選べ。

  配列 listデータ: 3,8,2,7,5,1

 なお,解答群の“→”は,内容が左から右へ移り変わっていくことを示している。

解答群
ア 2 → 3 → 2,3 → 2,3,8 → 1 → 5 → 1,5 → 1,5,7 → 1,2,3,5,7,8
イ 3 → 8 → 3,8 → 2,3,8 → 7 → 5 → 7,5 → 1,5,7 → 1,2,3,5,7,8
ウ 2,8 → 2,3,8 → 1,5 → 1,5,7 → 1,2,3,5,7,8
エ 3,8 → 2,3,8 → 7,5 → 1,5,7 → 1,2,3,5,7,8
オ 2,3,8 → 1,5,7 → 1,2,3,5,7,8
カ 3,8,2 → 7,5,1 → 1,2,3,5,7,8

設問3

 副プログラム Merge のβ部分と同じ結果を得る処理として正しい答えを,解答群の中から選べ。

解答群

f:id:tamagopanda:20100819232554p:image:leftf:id:tamagopanda:20100819232552p:image


f:id:tamagopanda:20100819232553p:image:leftf:id:tamagopanda:20100819232551p:image




問題掲載者による注意書き

  • 実際の問題文をテキスト化するにあたり,表記の難しい部分を以下のように置き換えている。
    • 丸 1,丸 2 (○の中に数字が入っている)で表記されていた文字は,機種依存文字のため, [1] ,[2] の様に置き換えた。(下線 [1],[2]等)
    • 空欄[ a ][ b ][ c ]等は,実際の問題文中では,四角で囲まれた,a,b,c だったが,[ ]で置き換えた。