基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

〔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)

例である図「整列処理の流れ」に処理の順番を書き入れていくと以下のようになります。(Sort(list、1)となる部分は処理が行われないので記述を省略してあります。)プログラム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

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

まず、下図の例で二つの配列を整列して結合する副プログラムMergeの見ていきます。

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]の要素が格納されるので正しい処理です。

∴エ