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

平成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 の引数の仕様

  引数    データ型 入力/出力 意味
A[ ] 整数型 入出力 整列対象の1次元配列
N 整数型 入力 整列する区間の最後の要素番号

〔プログラム〕

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

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

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

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

基本情報技術者試験


設問2 次の記述中の に入れる正しい答えを, 解答群の中から選べ。

1 次元配列 A[ ] の内容例を図に示す。 プログラム中のβの行が実行される回数は,図の例1では 回,例2では 回となる。 また,プログラム中のαの条件式を A[Idx2] ≧ Tmp とした場合, 例3のように配列要素の中に同じ値が複数含まれるときには


    図 1次元配列 A[ ] の内容例

d,e に関する解答群

ア 2        イ 3        ウ 4

エ 19        オ 20       カ 21

f に関する解答群

ア 整列が正しく行われなくなる

イ 整列は正しく行われ,元の条件式の場合と比べて実行ステップ数は多くなる

ウ 整列は正しく行われ,元の条件式の場合と比べて実行ステップ数は変わらない

エ 整列は正しく行われ,元の条件式の場合と比べて実行ステップ数は少なくなる

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

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

解答 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 の約 と推定できる。
ここで,log 2 1000 ≒ 10,log 2 1000000 ≒ 20 とする。

解答群

ア 500         イ 1,000       ウ 5,000

エ 10,000       オ 50,000       カ 500,000

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


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