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

⇄問題文と設問を画面2分割で開く⇱問題PDF

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

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

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

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

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

解答選択欄

  • a:
  • b:
  • c:

解答

  • a=
  • b=
  • c=

解説

aについて〕
問題文のプログラムではSortを再帰的に呼び出して、文字列の長さが1になるまで分割しています。再帰的呼び出しの場合には処理中に終了する条件を設定しておかないと無限にプログラムが続くことになってしまうので注意が必要です。
このためaに条件式は、プログラムSortを続行するか否かを判断するための比較が記されている必要があります。

選択肢の中で比較対象となっているnumは、配列listと共にSortに渡される引数であり配列リストの要素数を保持しています。
〔プログラムの説明〕(2)②の「この再帰的呼出しは、引数で渡される配列listのデータの個数が1になると終了する」より、numの値が1になった場合、再帰的な呼出しを終了することになります。

図「整列処理の流れ」をみればわかるように、最初1回目のSort処理ではnumの値は整列対象の文字列の文字数ですがSort処理で分割されるたびに数が減っていくことになります。

分岐選択処理では、条件式が真の場合に記述された処理を実行することになりますので、numが1より大きい場合はさらにSort処理を続行し文字列を分割、1以下であれば再帰呼出しを終了するという流れになることがわかります。

a=ウ:num>1

bについて〕
問題文中の〔プログラムの説明〕(1)①で説明されているように、プログラムSortでは「配列listに格納されているデータを、先頭からnum÷2個と残りnum-num÷2個に分割して二つの配列に格納」します。

プログラム中aの下の部分は、num1とnum2に配列slist1とslist2の要素数を計算した後、配列slist1に配列の前半部分の文字を格納しています。つまりbには、slist2に配列の後半部分を格納するための処理が入ることになります。

Sortに渡された配列の要素数が例と同じ7だった場合
  • num1=7÷2=3
  • num2=7-3=4
で、slist1の要素数が3、slist2の要素数は4になります。

続く、i:0,i<num1,1・slist1[i]←list[i] の処理は、iが0~2の間だけ繰り返されるので slist1にはlist[0]~list[2]の3要素が格納されています。このことからslist2には、残りのlist[3]~list[6]の4要素が格納されればよいことがわかります。

上記の例ではslist2への要素の格納の処理は、iが0~3の間だけ繰返されます。各選択肢について、list[ ]の添え字が正しい数値(3~6)になるかどうかを確かめてみると、
  • list[ ] の添え字は、iの数値そのまま(0~3)となり誤りです。
  • list[ ] の添え字は、num+i(上記の例では7~10)となり、list[ ]の要素数を超える添え字を指定しまうことになるため誤りです。
  • 正しい。list[ ] の添え字は、3+i(上記の例では3~6)となるため、list[ ]の後半部分(num-num1の部分)を正しくslist2に格納できます。
  • list[ ] の添え字は、num2+i(上記の例では4~7)となり、正しい添え字より一つ後ろにずれてしまうため誤りです。
b=ウ:list[num1+i]

cについて〕
問題文中の(3)Mergeの説明①にて、「配列slist1又はslist2のどちらか一方の要素がなくなるまで、次の②の処理を繰り返す」とあり、この繰返し条件がcに入る語句であると考えられます。

まず「キ」「ク」についてですが、Mergeの開始時にi及びjは0に初期化されており(i+j)の値はループに入る段階で0であることになります。0が(num1+num2)以上になることはなく、常にもループ中の処理が行われないことになるので誤りであることがわかります。
残る選択肢についてですが、cに続く処理は「二つの配列の要素を順に比較して小さい方から順に配列listに格納する」処理で、プログラムを見ると比較後小さかった要素は配列Listに格納され、その要素を保持していた配列slist1又はslist2の添字となる i,jがインクリメントされています(1を加算)。

配列slist1の要素数はnum1で各要素は、slist1[0]~slist1[num1-1]、また配列slist2の要素数はnum2で各要素は、slist2[0]~slist2[num2-1]と表せます。i,jのインクリメント処理によってiがnum1-1を超えた、又はjがnum2-1を超えた場合はどちらかの配列の要素がなくなったことを意味します。
配列の範囲外であるslist1[num1]、slist2[num2]の要素を参照するとプログラムがエラーを起こすので、i=num1又はj=num2となった場合にはループを終了する必要があります。
逆を返すとcに入るループの繰返し条件は、「i がnum1より小さい、かつjがnum2より小さい」ということになります。

c=ア:(i<num1) and (j<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→ 5,7 → 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

解答選択欄

  •  

解答

  •  

解説

例である図「整列処理の流れ」に処理の順番を書き入れていくと以下のようになります。(Sort(list、1)となる部分は処理が行われないので記述を省略してあります。)
pm08_5.png/image-size:458×321
プログラムSortのαにおける配列listの内容は、副プログラムMergeの返却値である配列となっているので、データが、

 4,7→4,5,7→2,3→1,8→1,2,3,8→1,2,3,4,5,7,8

というように移り変わっていくことになります。

同じように、配列list のデータ:3,8,2,7,5,1について考えてみると、
  1. "3,8,2,7,5,1"→"3,8,2" と "7,5,1"に分割
  2. "3,8,2"→"3" と "8,2"に分割
  3. "8,2"→"8" と "2"に分割
  4. "8"と"2"をMerge→"2、8"
  5. "3"と"2、8"をMerge→ "2、3、8"
  6. 最初に戻り"7,5,1"→"7" と "5,1"に分割
  7. "5,1"→"5" と "1"に分割
  8. "5"と"1"をMerge→"1,5"
  9. "7"と"5,1"をMerge→"1,5,7"
  10. "2,3,8"と"1,5,7"をMerge→ "1,2,3,5,7,8"
処理中で太字になっている箇所が、Mergeによって返却されたα時点での配列List[]の内容になります。

∴ウ:2,8→2,3,8→1,5→1,5,7→1,2,3,5,7,8

設問3

副プログラム Merge のβ部分と同じ結果を得る処理として正しい答えを,解答群の中から選べ。
解答群
  • pm08_4a.png/image-size:209×122
  • pm08_4i.png/image-size:211×122
  • pm08_4u.png/image-size:209×121
  • pm08_4e.png/image-size:211×121

解答選択欄

  •  

解答

  •  

解説

枠線で囲まれたβの部分は、問題文中の副プログラムMergeの説明③「配列slist1又はslist2の残った要素を配列listに追加する」処理です。

まず、下図の例で二つの配列を整列して結合する副プログラムMergeの見ていきます。
pm08_6.png/image-size:297×70
  1. "4, 5, 7"をslist1, "1, 2, 3, 8"をslist2とします。
  2. "4"と"1"を比較して小さい"1"をlist[0]に格納。jをインクリメント。
  3. "4"と"2"を比較して小さい"2"をlist[1]に格納。jをインクリメント。
  4. "4"と"3"を比較して小さい"3"をlist[2]に格納。jをインクリメント。
  5. "4"と"8"を比較して小さい"4"をlist[3]に格納。iをインクリメント。
  6. "5"と"8"を比較して小さい"5"をlist[4]に格納。iをインクリメント。
  7. "7"と"8"を比較して小さい"7"をlist[5]に格納。iをインクリメント。iが3となりループが終了します。
ここまでが副プログラムMergeの前半部分の処理で、この時点での変数の値は、num1=3, num2=4, i=3, j=3, list[ ] =(1, 2, 3, 4, 5, 7)です。

前半の繰返し処理は終了しましたが、slist2の"8"がlist[ ]に格納されずに残ったままになっています。β部分は、この残った要素をlist[ ]に追加する処理が行われます。
正しい整列処理では、list[6]にslist2[3](=8)が格納されればよいので、list[ ]の添字に注意して各選択肢の処理を比較してみると、
  • list[j]は、list[3]となります。既に整列済みのlist[3]にslist[3]の要素を上書きすることになってしまうので誤りです。
  • list[j+num2]は、list[3+4]=list[7]となります。list[7]は配列の範囲外となるので誤りです。
  • list[i+num2]は、list[3+4]=list[7]となります。list[7]は配列の範囲外なるので誤りです。
  • list[j+num1]は、list[3+3]=list[6]となります。正しい位置にslist2[3]の要素が格納されるので正しい処理です。
∴エ

平成22年春期 午後問題一覧

問1 問2 問3 問4 問5 問6 問7 問8 問9 問10 問11 問12 問13 採点講評
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop