平成19年 春期 基本情報技術者 午後 問04
問04 挿入ソートで整列する副プログラム次のプログラムの説明及びプログラムを読んで,設問1〜3に答えよ。
〔プログラムの説明〕 整数型の1次元配列の要素 A[0],… ,A[N](N > 0)を, 挿入ソートで昇順に整列する副プログラム InsertSort である。 (1) 挿入ソートの手順は,次のとおりである。 @ まず,A[0] と A[1] を整列し,次に A[0] から A[2] までを整列し, その次にA[0] から A[3] までというように,整列する区間の要素を一つずつ増やしていき, 最終的に A[0] からA[N] までを整列する。 A 整列する区間が A[0] から A[M](1 ≦ M ≦ N)までのとき, A[M] を既に整列された列 A[0],…,A[M−1] 中の適切な位置に挿入する。 その手順は次のとおりである。 (a) A[M] の値を,作業領域 Tmp に格納する。 (b) A[M−1] から A[0] に向かって Tmp と比較し, Tmp よりも大きな値を順次隣(要素番号の大きい方)に移動する。 (c) (b) で最後に移動した値の入っていた配列要素に Tmp の内容を格納する。 (b) で移動がなかった場合には A[M] に格納する。 (2) 副プログラム InsertSort の引数の仕様を表に示す。 表 InsertSort の引数の仕様
〔プログラム〕
設問1 プログラム中の に入れる正しい答えを, 解答群の中から選べ。
a に関する解答群 ア Idx1 イ Idx1 + 1 ウ Idx1 − 1 b,c に関する解答群 ア A[Idx2] ← A[Idx2+1] イ A[Idx2] ← A[Idx2−1] ウ A[Idx2] ← Tmp エ A[Idx2+1] ← A[Idx2] オ A[Idx2+1] ← Tmp カ A[Idx2−1] ← A[Idx2] キ A[Idx2−1] ← Tmp
設問2 次の記述中の に入れる正しい答えを, 解答群の中から選べ。 1 次元配列 A[ ] の内容例を図に示す。 プログラム中のβの行が実行される回数は,図の例1では 回,例2では 回となる。 また,プログラム中のαの条件式を A[Idx2] ≧ Tmp とした場合, 例3のように配列要素の中に同じ値が複数含まれるときには 。
図 1次元配列 A[ ] の内容例 d,e に関する解答群 ア 2 イ 3 ウ 4 エ 19 オ 20 カ 21 f に関する解答群 ア 整列が正しく行われなくなる イ 整列は正しく行われ,元の条件式の場合と比べて実行ステップ数は多くなる ウ 整列は正しく行われ,元の条件式の場合と比べて実行ステップ数は変わらない エ 整列は正しく行われ,元の条件式の場合と比べて実行ステップ数は少なくなる
設問3 次の記述中の に入れる正しい答えを, 解答群の中から選べ。 n 個のランダムなデータを整列する場合, 挿入ソートの計算量は O ( n 2 ), クイックソートの平均的な計算量は O ( n log 2 n )なので, n の値が大きくなるとクイックソートの計算量の方が総じて小さくなる。
InsertSort のほかに,クイックソートで昇順に整列する副プログラム QuickSort を作成し,
ランダムな 1,000 個のデータを何組か用意して,それぞれの組に対して InsertSort と
QuickSort の実行時間を測定したところ,QuickSort の平均実行時間が InsertSortの
であった。
この結果を基にして,1,000,000 個のデータを整列したときの平均的な実行時間を計算すると,
QuickSort が InsertSort の約 と推定できる。
解答群 ア 500 イ 1,000 ウ 5,000 エ 10,000 オ 50,000 カ 500,000
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
©2004-2024 情報処理試験.jp
|
プライバシーポリシー・著作権・リンク
|
お問合わせ
| ||||||||||||