基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成14年 春期 基本情報技術者 午後 問04
問04   擬似言語の記述形式

 次のプログラムの説明,擬似言語の記述形式の説明及びプログラムを読んで, 設問1,2に答えよ。

〔プログラムの説明〕

 整数型の1次元配列Aの A[Min] から A[Max] まで( 0 ≦Min<Max)を, クイックソートで整列する副プログラム QuickSort である。

(1) 整列の手順は,次のとおりである。

@ A[Min+1] から A[Max] まで,A[Min] と値が異なる要素を順次探し, 最初に見つかった要素の値と A[Min] の値のうち大きい方を基準値 (Pivot) として選ぶ。 配列の要素がすべて同じ値の場合は,整列処理を終了する。 この基準値を選ぶ処理には,副プログラム FindPivot を用いる。

A Pivot 未満の値の要素がすべて A[Min], … , A[i−1] (Min<i≦Max) にあり, Pivot 以上の値の要素がすべて A[i], … , A[Max] にあるように要素を並べ替える。 この処理には,副プログラム Arrange を用いる。

B A[Min], … , A[i−1] と A[i], … , A[Max] をそれぞれ新しい配列とみなして, QuickSortを再帰的に適用して整列する。

(2) 各副プログラムの引数の仕様を表に示す。

  表1 QuickSort の引数

変数名 入力/出力       意  味
A入出力整列対象の 1次元配列
Min入力整列する範囲の先頭の要素番号
Max入力整列する範囲の最後の要素番号

  表2 FindPivot の引数

変数名 入力/出力       意  味
A入力整列対象の 1次元配列
Min入力整列する範囲の先頭の要素番号
Max入力整列する範囲の最後の要素番号
Ret出力 基準値が格納されている要素の要素番号を返す。 ただし,A[Min], … , A[Max] がすべて同じ値の場合は,−1を返す。

  表3 Arrange の引数

変数名 入力/出力       意  味
A入出力整列対象の1次元配列
Min入力整列する範囲の先頭の要素番号
Max入力整列する範囲の最後の要素番号
Pivot入力基準値
Ret出力 A[Min], … , A[i−1] の値が Pivot 未満となり, A[i], … , A[Max] の値が Pivot 以上となるように要素を並べ替え,i の値を返す。

〔擬似言語の記述形式の説明〕

〔プログラム〕

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

a,b に関する解答群

ア K      イ L      ウ Max      エ Min

c,d に関する解答群

ア Ret ← A[K]      イ Ret ← A[Max]     ウ Ret ← A[Min]

エ Ret ← K       オ Ret ← Max      カ Ret ← Min

解答 a ←クリックすると正解が表示されます

解答 b ←クリックすると正解が表示されます

解答 c ←クリックすると正解が表示されます

解答 d ←クリックすると正解が表示されます

基本情報技術者試験


設問2  整数型の1次元配列要素 A[0] から A[9] までを QuickSort を用いて整列したときの,引数の内容を表4にまとめた。 表中の に入れる正しい答えを,解答群の中から選べ。

表4 QuickSort の呼出し回数と引数の内容

呼出し回数   A   Min   Max
  1 回目   0   9
  2 回目   0   4
  3 回目   
  :   :   :   :
  n 回目   9   9

e に関する解答群

f,g に関する解答群

ア 0      イ 1      ウ 2

エ 3      オ 4      カ 5

解答 e←クリックすると正解が表示されます

解答 f←クリックすると正解が表示されます

解答 g←クリックすると正解が表示されます

[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]