#（ １）アルゴリズムの時間計算量について最も適切な記述を選べ．
(3) 一般に入力サイズを引数とする関数を用いて表される.
#（ ２）問題 P の入力サイズが n であるとき，この問題 P に対するアルゴリズム A の最良時間計算量を T1(n)，最悪時間計算量を T2(n)とすると，T1(n)と T2(n)の関係について最も適切なものを選べ．
(2) 常に T1(n) ＞ T2(n) である．
#（３）データ構造である配列に関し，最も適切な記述を選べ．
(1) 任意の格納場所に対してデータの読み出しと書き込みの時間計算量は O(1)時間である．
#（４）データ構造である連結リストに関し，誤っている記述を選べ．
(2) 同じデータを格納する配列より必要な記憶領域は常に小さい．
#（５）データ構造であるスタックに関し，最も適切な記述を選べ．
(3) 処理要求の順番が遅いものから処理を済ませる．
#（６）データ構造であるキューに関し，最も適切な記述を選べ．
(1) 処理要求の順番が早いものから処理を済ませる．
#（７）データ構造である木に関し，誤っている記述を選べ．
(2) 各節点のレベルはその親のレベルよりも小さい．
#（８）完全２分木に関し，誤っている記述を選べ．
(4) すべての葉が同じレベルにあるとは限らない．
#（９）再帰アルゴリズムに関し，最も適切な記述を選べ．
(4) アルゴリズムを実現する関数内でその関数自身を呼び出す．
#（１０）再帰アルゴリズムの時間計算量に関し，最も適切な記述を選べ．
#（選択肢#（１０）
(3) 再帰木の節点数に比例する．
#（１１）サイズが n のデータに対する線形探索の時間計算量に関し，最も適切なものを選べ．
(2) O(n)
#（１２）サイズが n のソートされたデータに対する２分探索法の時間計算量に関し，最も適切なものを選べ．
(3) O(log n)
#（１３）２分探索法を適用するために必要な入力データの条件について，最も適切な記述を選べ．
(4) 入力データに対して定義されている全順序関係にしたがった順番で並べて配列に格納されている
#（１４）探索アルゴリズムであるハッシュ法に関し，最も適切な記述を選べ．
(2) 入力データから格納場所の位置に変換する関数の出力により，データの格納場所を決定する．
#（１５）探索アルゴリズムであるハッシュ法に関し，最も適切な記述を選べ．
(4) 入力データから格納場所の位置に変換できれば，ハッシュ関数はどんなものでもよい． ???
#（１６）サイズが n の人力に対するハッシュ法による探索に必要な時間計算量#（入力の準備に必要な時間を除く）
O(1)
#（１７）ソートアルゴリズムであるクイックソートに関し，最も適切な記述を選べ．
(3) 基準値を用いて入力を２つの集合に分割し，再帰的にソートを実行する．
#（１８）一般的な入力に対して，いくつかのソートアルゴリズムの実行速度を比較すると，一番高速なアルゴリズムはどれか．
(5) クイックソート
#（１９）分割統治法に関し，最も適切な記述を選べ．
(3) 入力をいくつかの部分問題に分割し，各部分間題を再帰的に解くアルゴリズムである．
#（２０）分割統治法に関し，最も適切な記述を選べ．
(2) 分割，統治，組合せという３つのステップで構成される．
#（２１）マージソートに関し，最も適切な記述を選べ．
(2) データをほぼ同じサイズの２つの集合に再帰的に分割するアルゴリズムである．
#（２２）グリーディ法に関し，最も適切な記述を選べ．
(2) アルゴリズムの実行途中において全体的なことは考えず，局所的に最良の解を選択するアルゴリズムである．
#（２３）グリーディ法に関し，最も適切な記述を選べ．
(2) 常に最適な解が得られる問題もあるが，そうでない問題もある．
#（２４）動的計画法に関し，最も適切な記述を選べ．
(5) 問題を部分問題から解き，その解を記録しておいて再利用する．
#（２５）動的計画法に関し，最も適切な記述を選べ．
(5) 処理の高速化のための手法である．
#（２６）バックトラック法に関し，最も適切な記述を選べ．
(1) すべての解を効率よく列挙するアルゴリズムである．
#（２７）分枝限定法を実現するため，バックトラック法に追加する性質に関し，最も適切なものを選べ．
(2) 不必要な解の列挙を省略する．
#（２８）情報科学の分野で用いられるグラフに関し，最も適切な記述を選べ．
2
??? データの関係を視覚的に表す抽象概念である．
#グラフを格納するための代表的なデータ構造としては，隣接行列と隣接リストがある．
#（２９）辺が少ないグラフを格納する場合，記憶領域の面の観点から最も適切な記述を選べ．
(2) 隣接リストの方が有利である．
#（３０）２つの頂点間に辺があるかないかを頻繁に調べる場合について，最も適切な記述を選べ．
(1) 隣接行列の方が有利である．
#入力データの数が n のアルゴリズムの時間計算量 T(n)が以下のように定義される場合，T(n)のオーダ記法として適切なものはどれか．
#（３１）
T(n)=2T(n-1) (n>=2)
T(1) =c
n=2: T(2) = 2T(1) = 2c
n=3: T(3) = 2T(2) = 4c
n=4: T(4) = 2T(3) = 8c
(7) O(2^n)
#（３２）
T(n)=cn+T(n/2)+T(n/2) (n>=2)
T(1) =c
O(n log n)
#ポインタの値
以下はプログラミング言語 C で記述されたプログラムである。
int a, b;
int *p, *q;
a = 3; b = 2; p = &a; q = &b; b = (*p)+ b;//5
/* step 1 */
q = p; *p =(*q)*3 – (*p);
/* step 2 */
/* step 1 */ で示された時点で、a の値は#（ 3 ）、b の値は#（ 5 ）となる。
/* step 2 */ で示された時点で、a の値は#（ 6 ）、b の値は#（ 5 ）となる。
#空のスタック S に対して以下の操作を順番に実行した.
push(S, 1)→push(S, 5)→push(S, 4)→pop(S)→push(S, 8)→push(S, 7)→pop(S) →pop(S)→pop(S)
push(S, d)は，スタック S にデータ d を格納する，pop(S) スタック S からデータを取り出して出力することを示す．
1 回目，2 回目，3 回目，４回目の pop で出力される値は，
4 7 8 5
#空のキューQ に対して以下の操作を順番に実行した．#（選択肢#（Ｂ））
enqueue(Q, 1)→enqueue(Q, 2)→dequeue(Q)→enqueue(Q, 3)→dequeue(Q)→enqueue(Q, 6)→enqueue(Q, 5)→dequeue(Q) →dequeue(Q)
enqueue (Q, d)は，キューQ にデータ d を格納する，dequeue (S) Q からデータを取り出して出力することを示す．
1，2，3，４回目の dequeue で出力される値は，
1 2 3 6
#フィボナッチ数の実行
定義を下に示す．
F(0) = F(1) = 1
F(n) = F(n-1) + F(n-2)#（n≧2 の場合）
//4( 3(2 – 1) -2( 1 -0 ) ) //9回
// 5 ( 4 3) //3
// (3 2) (2 1) //7
// (2 1) (1 0) (1 0) //13
// (1 0) //15
n は非負の整数とする．
別紙の最後に示すプログラム(1)は再帰呼び出しのみを用いたプログラムであり，プログラム(2)は実行結果を記録し，再利用可能な結果#（配列 fdata）があればそれを用いるプログラムである．
・fib1(4)を実行したとき，再帰呼び出しも含めて，fib1 が呼び出される回数は#（ 9 ）回である．またfib1(5) を実行したとき， fib1 が呼び出される回数は#（ 15 ）回である．空欄の値を示せ.
#（考え方）c1(n)を fib1(n)が呼び出される回数とする c1(0)=1, c1(1)=1, c1(2)=1, c1(3) = 1+ c1(2)+c1(1)となる．
・最初に fib2(4)を実行したとき，再帰呼び出しも含めて，fib2 が呼び出される回数は#（ 5 ）回である．
fib2(4)を実行した後，fib2(5)を実行したした場合，fib2 が呼び出される回数は#（ 1 ）回である．
#以下の空欄に入る適切な C 言語の表現#（変数，式等）を示し，プログラムを完成させよ．
#(1)以下は連結リストの操作を行うアルゴリズムである．
typedef struct record { // レコード#（連結リストの要素）の型の定義
struct record *next ;
int data ;
} record_t ;
record_t* head = NULL; // 連結リストの先頭を示す
static void insert(int x) { // 連結リストの先頭への要素#（値 x）の追加
record_t* rp;
rp = (record_t*)malloc(sizeof(record_t));
rp->data = x;
rp->next = #( head ) ;
head = #（ rp ）;
}
static int remove() {
// 略
}
#(2)以下は２分探索のアルゴリズムである． 探索対象のデータは N 個の要素を持つ配列 D に昇順にソートされた状態で
格納されている．
int x;
// 探索対象のデータ
int a, b, m; // 探索範囲を示す変数
a = 0;
b = N-1;
m = #（ (a+b)/2 ）;
while (a<b) {
if (D[m] == x ) {
printf (“Found at %d¥n”, m );
return;
} else if (D[m] = b ) return;
p = partition(D, a, b);
quicksort( D, #（a）, #（p-1） );
quicksort( D, #（p+1）, #（b） );
} // end of quicksort
static int partition(int D[], int left, int right) {
// 略
} // end of partition
#(4) 以下はマージソートのアルゴリズムである． 探索対象のデータは N 個の要素を持つ配列 D に格納されている．
mergesort (D, a, b) を呼び出すと， D[a]～D[b]をソートする．
static void mergesort(int D[], int a, int b) {
int m;
m = (a+b-1)/2;
if (a<m) mergesort( D, #（a）, #（m） );
if ((m+1)<b) mergesort( D, #（m+1）, #（b） );
merge(D, a, m, b);
// merge は，前の２つの mergesort の呼び出しによりソートされた部分を全体がソートされるようにまとめる．
} // end of mergesort
//——————————————————//
static void merge(int D[], int a, int m, int b) {
// 略
} // end of merge
#ナップサック問題
１からｎまでの番号のついた n 個の荷物があり，番号が i の荷物の重さと価値をそれ wi, vi とする． 荷物を入れるナップサックに入れられるのは，重さの和が C までという制限がある．荷物 i をナップサックにいれる場合 ei = 1, いれない場合を ei = 0 とする．ナップサック問題とは，重さの制約条件#（Σeiwi ≦ C）を満たす範囲で，価値の総和#（ Σeivi ）を最大にする ei#（i=1, .. , n）を求める問題である．
