Document

2014 年度
アルゴリズムとデータ構造１
特別試験
出題：土屋孝文
2015 年 2 月 20 日金曜日 3 限実施
一切の持込不可
問１線形探索：整数型配列中に 43 があれば「43 があったよ」と出力し、43 が 1 つもなかったときは「43 がなかったよ」と出力する
プログラムを示す。１、２、３、４を解答しなさい。（選択問題）
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int N = 20;
int a[] = {27, 31, 39,39,43,46,51,53,61,64,71,71,79,85,91,102,106,109,123};
int main (void) {
int i;
int flag = １;
set_array();
for (２)
if (３) {
printf("a[%d]に 43 があったよ¥n", i);
４;
}
if (flag == 0)
printf ("43 がなかったよ¥n");
return 0;
}
問2
線形探索の実行時間のオーダーは O (n)である。
（１）
O(n)とは、どういう意味か。説明しなさい。
（２）
線形探索の実行時間のオーダーが O(n)であるとする分析を説明しなさい。
問 3 二分探索：昇順に整列化されているデータなら、線形探索よりも二分探索を用いるほうがよい。二分探索は、どんな手続き（ア
ルゴリズム）なのか、以下の 20 個のデータの中に 43 があるかどうかをみつける例をもちいて、説明しなさい。(変数 low, high, mid
を使ってください)
コメント：この方法の場合、データが 4 倍になると、実行時間は 2 回増える（2 回しか増えない）
。データが 8 倍になると、実行時間は 3 回増える。デ
ータが N 倍になると、実行時間は log2N 回 (たとえば、log28=3) になる。つまり、データ量 N の増加に対して、実行時間は log N に比例して増加す
る。
1000 個の相異なる要素が、キーの昇順に整列された表がある。外部から入力したキーによってこの表を 2 分探索して、該当す
問４
るキーの要素を取り出す。このときのキーの比較回数は最大 10 回である。ただし、該当するキーは必ず表中にあるものとする。なぜ
10 回かを説明しなさい。
問 5 右は、二分探索のアルゴリズム（疑似コード）である。(A)と(B)のコードを書きなさい。
問6
自然数 n に対して、次のように再帰的に定義される関数 f1(n)を考える。
f1(n) :
if
n <= 1
(A)
f 1(4)を求めよ
(B)
再帰条件を日本語で表現せよ
then
return 1
else
return
n + f1(n-1)
問 7 整数型配列 {9,3, 1,8, 2} を昇順に整列する。以下の問に答えなさい
選択ソートを行うと、次の操作結果は、１である。その次は 2 である。
バブルソートを行うと、次の操作結果は、３である。その次は４である。
挿入ソートを行うと、次の操作結果は、５である。その次は６である。
問 8 バブルソートの時間計算量は、O (n2)である。教科書を参考にしながら分析しよう。
アルゴリズムを具体的に記述すると、以下のようになる (p 46 改変)。
（A[0] ～ A[n-1]まで n 個の配列の要素を昇順に並び替える）
bubble-sort() {
for (i = 0 ; i < n ; i++) {
/* i は０番目から、n-1 番目まで */
for (j = n -1 ; j > i ; j--) {
/* j は n-1 から、i+1 *まで */
if (A[j-1] > a[j]) {
/* 前の方が大きい隣同士があれば */
swap(A[j]), A[j-1]);
/* 値を交換する */
}
}
}
}
バブルソートのアルゴリズムで一番計算の手間がかかるのは、二重ループで行われる隣接要素の比較である。順に考えていこう。
（Ａ） n = 5（たとえば{9,3, 1,8, 2}）のとき、最小値が先頭(添え字 0)に移動するまでの比較回数は 4 回となる。その説明をしなさい。
（Ｂ）
2 番目に小さい値が 2 番目(添え字 1) に移動するまでの比較回数が 3 回になる説明をしなさい。
（Ｃ）
N= 5 のとき、全体の回数はいくつになるか。
（Ｄ）
一般に要素数 n の場合の比較回数を式で示せ。
（Ｅ）
最悪の場合などを考えよう。{9,3,1,8,2}と{1,2,3,8,9} の比較回数は、それぞれ、いくつか。
分析が終わったので、O 記法で表現しよう。n が大きくなると、計算時間はどのように増加していくのかを表現する。
D, E から、バブルソートの時間計算量は O (n2) と表現される。
（Ｆ）O (n2) は、O(n)と比較すると、どのような性質だろうか。
注：このほかの話題：番兵、ハッシュ法、文字列照合(kmp, bm)、ユークリッドの互除法、エラトステネスのふるい

Download Report