基本情報技術者試験の練習問題 - 第 10 回 この問題は平成 19 年度春期の問題から抜粋しています 問 1 次のプログラムの説明及びプログラムを読んで, 設問 1~3 に答えよ プログラムの説明 整数型の 1 次元配列の要素 A[0],,A[N](N>0) を, 挿入ソートで昇順に整列する副プログラム InsertSort である (1) 挿入ソートの手順は, 次のとおりである (i) まず,A[0] と A[1] を整列し, 次に A[0] から A[2] までを整列し, その次に A[0] から A[3] までというように, 整列する区間の要素を一つずつ増やしていき, 最終的に A[0] から A[N] までを整列する (ii) 整列する区間が 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 の引数の仕様を表に示す プログラム
設問 1 プログラム中の [ a に関する解答群 b,c に関する解答群 設問 2 次の記述中の [ 1 次元配列 A[ ] の内容例を図に示す プログラム中のβの行が実行される回数は, 図の例 1 では [ d ] 回, 例 2 では [ e ] 回となる また, プログラム中のα の条件式を A[Idx2] Tmp とした場合, 例 3 のように配列要素の中に同じ値が複数含まれるときには [ f ] d,e に関する解答群ア 2 イ 3 ウ 4 エ 19 オ 20 カ 21 f に関する解答群ア整列が正しく行われなくなるイ整列は正しく行われ, 元の条件式の場合と比べて実行ステップ数は多くなるウ整列は正しく行われ, 元の条件式の場合と比べて実行ステップ数は変わらないエ整列は正しく行われ, 元の条件式の場合と比べて実行ステップ数は少なくなる 設問 3 次の記述中の [ n 個のランダムなデータを整列する場合, 挿入ソートの計算量は O(n 2 ), クイックソートの平均的な計算量 は O(nlog 2 n) なので,n の値が大きくなるとクイックソートの計算量の方が総じて小さくなる InsertSort のほかに, クイックソートで昇順に整列する副プログラム QuickSort を作成し, ランダムな 1,000
個のデータを何組か用意して, それぞれの組に対してInsertSortとQuickSortの実行時間を測定したところ, QuickSortの平均実行時間がInsertSortの 1/10 であった この結果を基にして,1,000,000 個のデータを整列したときの平均的な実行時間を計算すると,QuickSortがInsertSortの約 1/[ g ] と推定できる ここで, log 2 1000 10,log 2 1000000 20 とする 解答群 ア 500 イ 1,000 ウ 5,000 エ 10,000 オ 50,000 カ 500,000 問 2 プログラム設計に関する次の記述を読んで, 設問 1~3 に答えよ ある会員情報が入ったマスタファイルの内容を, 毎月末にトランザクションファイルの内容によって更新し, 新 マスタファイルに出力する更新プログラムを作成する ファイルの説明 (1) マスタファイル及びトランザクションファイルのレコード様式は同じで, 次の項目からなる (2) 会員番号は,5 けたの数字であり, 必須の項目である 最大値 99999 の会員番号をもつ会員は存在しない (3) マスタファイル及びトランザクションファイルは, 会員番号をキーとして, 昇順に整列されている (4) マスタファイルには, 同一の会員番号をもつレコードが複数存在することはない トランザクションファイルにも, 同一の会員番号をもつレコードが複数存在することはない (5) トランザクションファイルは, 新規会員追加に用いるレコード及び既に登録されている会員の会員情報変更に用いるレコードからなる (6) 会員情報変更に用いるレコードは, 変更する項目に空白以外のデータが格納され, 変更しない項目には, 空白が格納されている 処理の説明 マスタファイルのレコードを M, トランザクションファイルのレコードを T として, 次のキー突合せ処理を行う (1) M と同一の会員番号をもつ T があるとき,T の空白以外の項目で M の対応する項目を更新し,T の空白の項目に対応した M の項目は更新せずに新マスタファイルに出力する (2) M と同一の会員番号をもつ T がないとき,M をそのまま新マスタファイルに出力する (3) T と同一の会員番号をもつ M がないとき,T を新マスタファイルに出力する 更新プログラムの流れを図 1 に示す 突合せキー K M 及びK T には, それぞれ,Mの会員番号の値及びTの会員番号の値, 又はそれぞれのファイルを読み終わったことを表す最大値 99999 を格納する
設問 1 図 1 において, キー突合せによるマスタファイルの更新処理は, 破線で囲んだ部分で実現している 図 1 中の [ 解答群 ア M' 入カ処理イ M 入カ処理ウ T 入カ処理
設問 2 次の記述中の [ この更新プログラムに会員情報の削除処理を追加するため, 次の (1)~(5) を行う (1) トランザクションファイルのレコード様式に, 更新区分という項目を追加する (2) 更新区分が U の場合を新規登録及び変更とし, D の場合を削除とする (3) 図 1 のαとβの処理を,(1) のレコード様式の変更に対応するように変更する (4) 主処理を図 2 のとおりに変更する (5) T 入カ処理については, ファイルを読み終わったとき, 更新区分に U を代入する処理を追加する ここで, 図 2 のエラー処理 1 及び 2 は, エラーとなったレコードに関する情報を表示する 条件 X2 は, [ c ] である エラー処理 2 は,[ d ] 場合に実行される c に関する解答群 d に関する解答群ア更新区分に誤りがあるイ削除しようとする会員番号をもつレコードがマスタファイルに存在しないウ新規登録しようとする会員番号をもつレコードがマスタファイルに存在するエ変更しようとする会員番号をもつレコードがマスタファイルに存在しない
設問 3 次の記述中の [ トランザクションファイル中に同一の会員番号をもつレコードが複数あってもよいようにする 複数ある場合, レコードの発生順に処理する そのために, 次の (1),(2) の変更を行うことにした (1) トランザクションファイルのレコード様式に発生日時という項目を追加する (2) 図 2 の更新プログラムとは別にトランザクションファイルの処理に, 整列プログラムとレコード集約プログラムを追加して, 新たにトランザクションファイルを生成する 整列プログラムは, レコードを整列キーの昇順に並べ替える ここで, 第 1 整列キーは [ e ], 第 2 整列キーは [ f ] である レコード集約プログラムの主な機能は, 次の二つである (i) 会員番号が同じ入カレコードで, 更新区分がすべて U のときには, 空白以外の変更項目の内容を作業領域に上書きし, 最後の状態を出力する (ii) 更新区分が D のレコードが見つかったときには, そのレコードを出力する それ以降にも同一の会員番号のレコードが存在したときには, それらは処理せずエラーとする これらのプログラムの実行順序は, 次のとおりである 実行順序 : [ g ]
e,f に関する解答群ア会員番号イ更新区分ウサービス等級エ発生日時 g に関する解答群ア更新プログラム 整列プログラム レコード集約プログラムイ更新プログラム レコード集約プログラム 整列プログラムウ整列プログラム 更新プログラム レコード集約プログラムエ整列プログラム レコード集約プログラム 更新プログラムオレコード集約プログラム 更新プログラム 整列プログラムカレコード集約プログラム 整列プログラム 更新プログラム 問 3 次の C プログラムの説明及びプログラムを読んで, 設問 1,2 に答えよ プログラムの説明 リーグ戦の勝敗表を出力するプログラムである (1) 勝敗表の出力例を図 1 に示す (2) チームの勝敗情報は構造体 RECORD で表現する 引き分けはないものとする 全チームの勝敗情報は構造体 RECORD の配列 team に格納されている チーム名, 勝ち数, 負け数はあらかじめ格納されているが, 勝率は格納されていない (3) プログラム中の関数 calcaverage と print の仕様は次のとおりである void calcaverage( ) 機能 : 全チームの勝率を計算し, それぞれのメンバ average に格納する 試合数が 0 の場合, 勝率は 0.0 とする void print( ) 機能 : 勝敗表を出力する
プログラム 1 設問 1 プログラム 1 中の [ a に関する解答群 b に関する解答群
設問 2 順位の項目を加え, 勝率の高いチームから順に出力する関数 printrank を作成した 勝率順の勝敗表の 出力例を図 2 に示す 勝率が同率の場合は同順位とする 処理手順は次のとおりである (1) TEAMNUM 個の要素をもつポインタ配列 pteam を定義する (2) 配列 team の各要素のアドレスを, 先頭要素から順番に配列 pteam の各要素に格納する これによって要素番号 i に対応するチームの勝率 team[i].average は,pTeam[i]->average によっても参照できる (3) 配列 team 自体を整列する代わりに配列 pteam の要素を整列して, 勝率順の勝敗表を出カする 次の関数があらかじめ定義されているものとする void sort(record *pteam[teamnum]) 機能 : TEAMNUM 個の要素からなり, 各要素が RECORD 型の構造体へのポインタである配列 pteam の要素を, 勝率の降順になるように整列する プログラム 2 中の [
プログラム 2 c に関する解答群 d に関する解答群 e に関する解答群