アルゴリズムとデータ構造 中間試験問題 (Aコース)

アルゴリズムとデータ構造 中間試験問題 (B コース)
2014 年 12 月 5 日，担当：井上
注意事項：持ち込み禁止です．机の上には筆記用具と時計，ちり紙等以外は置かないこと．携帯電話は電源を切って鞄等
の中に入れてください．途中退出は 19:55 以後可とします．なお，途中退出する場合は，荷物をすべて持ち，教室前方
で答案用紙を提出，模範解答を受け取ったあと，前のドアから退出すること (再び自分の席に戻らないこと)．
第 2 問以降については，手順を計算用紙などで図示しながら考えるなどして，凡ミスを避けること．また，全て解答を
終わったとしても，十分納得できるまでチェックする時間を惜しまないこと (エンジニアの心得)．
1. 以下の文章中の空欄 (A)～(Y) に入るものを選択肢から
選び，記せ．
 人間のような直感や常識を持たないコンピュータに特定の
問題を解かせようとする場合，問題を解く手順，すなわち
(A) と，その過程におけるデータの管理方法，すなわち
(B) の双方を詳細に記述する必要がある．
 解く問題ごとに (A) は複数存在しうる．その優劣を評価す




る基準の一つは，少ない繰り返し回数で速く問題を解く効
率性である．効率性を定量的に評価するには，問題を解く
のに要する繰り返し回数を問題のサイズ n の関数として求
める．これを (A) の (C) という．ただし，実際の実行時
間には用いるコンピュータや OS などに依存した違いがあ
るため，定数係数などを無視し，(C) がどのような種別の
関数であるかのみを問題とする．例えば (C) が 2n2+4n で
表される場合，1 次の項および定数係数を無視して O(n2)の
ように表記する．これを (C) の (D) という．
優れた (A) の設計においては，最初に思いつくような素朴
な方法から発想を転換した解き方を採用することも必要と
される．例えば 1000 以下の素数を全て求めるというとき，
素朴には各数 n をそれぞれ (E) 以下の全ての数で割って，
割り切れるものがあるかを調べる方法があるが，これとは
全く異なる発想として，1000 までの各数に対応するフラグ
配列を用意し，求まった素数の倍数全てについて一括して
フラグを下ろしていく方法がある．この方法を (F) とい
う．
解析的に求まらない演算では，コンピュータを用いて近似
的に求める方法，すなわち (G) が有効である．ここで問題
となるのは，計算はあくまで近似的であり，計算過程で行
われる四捨五入により生じる (H) や，無限の繰り返しを要
する計算を有限回で打ち切るために生じる (I) などの誤
差要因が存在することである．
解析的に解けない非線形方程式を数値的に解く方法とし
て，解の存在しうる範囲の中央に対して解が左右のどちら
にあるかを調べて範囲を半分に絞っていくことを繰り返す
方法があり，これを (J) という．より効率のよい方法とし
て，解近傍の xi の値に対し，この位置での関数 f (x )の接線
を求め，接線と x 軸との交点を xi+1 とする操作を繰り返す
方法は (K) と呼ばれる．
データ列を特定の基準にしたがって並べ直す作業を (L)
という．その素朴な方法として，隣接データを比較し，順
序が逆の場合に交換を行うという操作をデータ列の末尾か
ら先頭に向かって繰り返す (A) は，(M) と呼ばれる．ま
た，途中まで (L) が完了したデータ列に対し，次のデータ
を適切な位置に挿入する操作を繰り返す (A) は (N) と呼
ばれる．(M) や (N) などの単純な方法では，その (C) の
(D) は (O) である．(N) の発展形として，データ列をと
びのある部分列に分け，予め (N) により (L) する操作を，
とびを徐々に小さくしながら繰り返す方法は (P) と呼ば
れ，その (C) の (D) は (Q) である．
 データ列の中から特定のデータを見つけ出す作業を (R)
という．先頭から順にデータを調べていくという素朴な方
法は (S) と呼ばれるが，データが予め (L) されている場
合に限り，(T) という (A) が使える．この方法は (J) と
同様に，データの存在しうる範囲の中央を調べることで，
目的データが中央より前にあるか後にあるかによって探索
範囲を半分に絞っていく方法であり，その (C) の (D) は
(U) である．
 解くべき問題を，同じ手順で解ける，よりサイズの小さな
副問題に分解し，副問題を先に解くことを考えることがで
きる．このとき問題を解く関数は，副問題を解くために自
分自身の関数を呼び出すという構造を持つ．このような解
き方を (V) という．
 与えられたデータ列を軸と呼ばれる基準値よりも大きなグ
ループと小さなグループに大きく分割し，分割された各々
のグループを更に (V) によって分割していくことで，(L)
を実現する (A) を (W) という．その (C) の (D) は
(X) である．
 データの一時置き場 (バッファ) として利用される (B)
のうち，最初に入れたデータから順にデータ取り出しを行
う方式 (FIFO 方式) によるものを (Y) といい，インター
ネット上のストリーミング音声の再生におけるバッファリ
ングなどに利用することができる．
選択肢
直接選択法, 数値計算, 番兵, 漸化式, サーチ, 逐次探索,
コンパイル, ニュートン法, エラトステネスのふるい,
フィールド, スタック, 2 分探索, n3, オーバーフロー, n ,
バブル・ソート, n1.25, 台形則, クイック・ソート, 丸め誤差,
シンプソン則, キュー, 打ち切り誤差, 浮動小数点, ソート,
プログラム, パターンマッチング, アルゴリズム, 構造体,
メモリ空間, 2 分法, データ構造, 数値積分, ポインタ, n,
オーダ, マージ・ソート, 再帰, n log n, n2, レコード, 計算量,
桁落ち, 基本挿入法, オイラー法, n n , 2 分探索, 漸化式,
ユークリッドの互除法, シェル・ソート, ヒープ・ソート,
ハッシュ, log n．
(裏面に続く)
2. 以下は，教科書に書かれた直接選択法のソース・コードで
ある．ただし，太字部分を変更した．変更部分は，データ列の
表示の関数化，およびソートの途中経過の表示に関するもので
ある．これについて，以下の問に答えよ．
#include <stdio.h>
#define N 6
void disp(int a[])
{
int i;
}
void main(void)
{
int a[]={80,41,35,90,40,20};
int min,s,t,i,j;
for (i=0;i<(A);(B)){
disp(a);
min=a[i];
s=(C);
for (j=(D);j<N;j++){
if ((E)){
min=(F);
s=j;
}
}
t=a[i];a[i]=a[s];a[s]=t;
}
disp(a);
}
(1) 空欄 (A)～(F) に入るものを記せ．
(2) プログラム実行時の表示内容を記せ (disp(a)の呼び出
し位置に注意すること)．
3. 自然数 i に対して以下のような漸化式で記述できる数列 ki
があるとする．
1
ki
ki
(i
1
ki
3
特定のデータに対して特定のアルゴリズムを使用した場合の
表示例は以下のとおりである (用いるアルゴリズム等によっ
て，表示順や表示内容は異なりうる)．このように，3 人以上の
同年齢のグループが存在するときは一度に表示することを考
え，当然ながら同じ人が 2 回以上表示されないようにせよ．
Ann さんと Juliet さんと Mari さんとは同年齢 (18 歳)．
for (i = 0; i < N; i++)
printf("%d ", a[i]);
printf("¥n");
ki
適宜減点していく ので注意 (例えば,「p[i] と同年齢の人を全
て探す」のような表現は具体性が不足しており，
「どう探すの
か」に関する具体的な記述が必要である)．
1,2, 3)
(otherwise)
(1) この数列の第 n 項を再帰的に求める関数を C 言語で記せ．
ただし関数のプロトタイプは以下のとおりとする：
long fib2(int n);
(2) 作成した関数の冒頭に下記を追加したとき，fib2(5)を呼
び出した際の画面出力はどうなるかを記せ．
printf(“fib2(%d) called.¥n”, n);
4. 以下の構造体配列に，N 人の人々の名前と年齢のデータが
入力されているとする．
struct person{
char name[20];
int age;
} p[N];
このとき，同年齢の人々を表示するアルゴリズムを考案し，詳
細に 記せ．ただし，コンピュータには人間のような直感や常識
はないことを考慮し，事細かに手順を記すこと．曖昧な表現は
Nancy さんと Candy さんとは同年齢 (16 歳)．
Eluza さんと Ema さんとは同年齢 (17 歳)．
※ アルゴリズムの表記方法の例として，バブル・ソートの場
合の表記例を以下に示す．
(1) i を 0～N-2 まで増やしながら (2) を繰り返す．
(2) j を N-1 から i+1 まで減らしながら (3) を繰り返す．
(3) a[j]<a[j-1]のとき，a[j]と a[j-1]を交換する．
※ 赤字になっている部分は，試験中に訂正として伝えた部分
です．
以上