期末試験問題 (解答例)

期末試験問題 (解答例)
1.
(教科書第 2 章)
(1) 出力結果を以下に示す.
move 1 from A to C
move 2 from A to B
move 1 from C to B
move
move
move
move
3
1
2
1
from
from
from
from
A
B
B
A
to
to
to
to
C
A
C
C
(2) 出力される行数は，2n − 1 である．
2.
(教科書第 2 章)
(1) 2 分探索法を適用するためには，配列中のデータが昇順，または降順にソートされている必要がある.
(2) 配列中のデータ数が N のとき，２分探索法では O(log N ) の処理量で，指定されたデータが配列中に存在す
るか否かを決定できる．
(3) 探索するデータを x とする．2 分探索法では，x と配列中のデータとの比較を１回行う度に，配列中で探索
の対象となる範囲が半分 (以下) に減少する．この比較を繰り返すことにより最終的には配列中の探索範囲
の要素数は１となる．勿論，途中で x が見つかった場合にはそこで探索処理が打ち切られる．対象範囲の要
素数が 1 になった場合，その配列の要素が x と比較して同じか異なるかの判定を行い処理が終了する．ここ
で，m 回この比較を行ったとき配列中の探索範囲に含まれる要素数が 1 になったとすると，近似的に次式が
成り立つ，
N
=1
2m
これより，N = 2m であり，両辺の対数をとると m = log2 N となることから，O(log N ) であることが言
える．
(4) 配列中のデータが昇順にソートされている場合のプログラム例を以下に示す．
int binsearch(int *ary, int n, int x) {
int low=0, high=n-1, mid;
do {
mid=(low+high)/2;
if(x > ary[mid]) low=mid+1;
else high=mid-1;
} while(x != ary[mid] && low <= high);
if(x==ary[mid]) return 1;
else retrun 0;
}
3.
(教科書第 3 章)
(1) reverse のプログラム例を以下に示す.
struct cell* reverse(struct cell *L) {
struct cell* q=NULL;
for(; L!=NULL; L=L->next)
q=add(q,L->data);
return q;
}
(2) lcat のプログラム例を以下に示す.
struct cell* lcat(struct cell* L1, struct cell* L2) {
struct cell* p;
if(L1==NULL) return L2;
for(p=L1; p->next != NULL; p=p->next);
p->next=L2;
return L1;
}
4.
(教科書第 3 章)
(1) insert の例を以下に示す.
void insert(int d) {
struct dcell* q;
q=(struct dcell*)malloc(sizeof(struct dcell));
q->next=head.next; head.next->prev=q;
head.next=q; q->prev=&head; q->data=d;
}
(2) delete の例を以下に示す.
int delete(int d) {
struct dcell*p;
for(p=&head; p!=&tail && p->data!=d; p=p->next);
if(p==&tail) return -1;
p->next->prev=p->prev;
p->prev->next=p->next;
free(p);
return d;
}
2
5.
(教科書第 5 章)
(1) (省略）
(2)
int square_sum(struct bnode *p) {
int sum=0;
if(p!=NULL)
sum=p->data*p->data+square_sum(p->left)
+square_sum(p->right);
return sum;
}
6.
(教科書第 7 章)
(1) 最終的に出来上がるヒープの配列の内容を以下に示す。
15
12
8
10
5
1
7
3
6
(2) 最大要素を 1 つ取り出した後のヒープの配列の内容を以下に示す。
12
10
8
6
5
1
7
3
(3) N 個のデータを含むヒープ木の段数は、dlog2 (N + 1)e である。つまり、ヒープ木の根ノードから全ての葉に
至るパスの長さは blog2 N c である。データを追加する際にヒープ木の親ノードとの値比較を行うが、その
比較回数は blog2 N c を超えない。従って、この演算のオーダーは、O(log N ) である。
(4) ヒープからの最大要素の取り出しは、配列の先頭要素を取り出した後、配列の最後の要素を先頭に移動させ、
以下ヒープ木上で子ノードのデータより親ノードのデータが小さいうち最大の子ノードのデータと交換する
処理を葉ノードに向けて行う。この際の比較回数はヒープ木の段数を超えない。ヒープ木の段数は、(3) で
述べたように blog2 N c であることから、この演算のオーダーは、O(log N ) である。
7.
(教科書第 7 章)
(1) ハッシュ表の内容を以下に示す.
(2) プログラム例を以下に示す. ここでは ‘key’ のデータ型が文字列 (char*) であるため, 文字列の長さ分の領域を
htbl.key に確保することと, 文字列をコピーしなければならないことに注意.
int insert(char* key,struct rec* htbl) {
int i,cnt=0;
for(i=h1(key); i>=0 && htbl[i].st==OCC && cnt < M; i=(i+1)%M,cnt++);
if(cnt==M) return TABLE_FULL;
htbl[i].name=malloc(strlen(key)+1);
strcpy(htbl[i].name,key);
htbl[i].st=OCC;
return NORMAL;
}
3
表 1: 解答
8.
位置
flag
char*の内容
0
VAC
1
OCC
2
VAC
3
VAC
4
VAC
5
VAC
6
OCC
mandarin
7
OCC
banana
8
DEL
9
OCC
10
DEL
apple
melon
(教科書第 7 章)
(1) 線形探索法では，ハッシュ関数 h1 を用いて最初の探索位置を決定し，衝突が発生した場合には，配列中の位
置を 1 ずつずらしながら空きを探す. 一方, ダブルハッシュ法では，まずハッシュ関数 h1 で最初の探索位置を
決定した後，衝突が発生した場合には，h2 で得られた値ずつ配列中の位置を飛ばしながら空きを探索する．
(2) 一般に線形探索法では，データが連続して埋まる部分（ラン）が発生しやすい. 一方, ダブルハッシュ法では,
ランの発生が抑制される.
(3) M > M 2 であり，かつ M 2 と M の値は互いに素でなければならない．
(4) クローズドハッシュでは，削除を行う際に，配列中のその位置に以前値が存在したことを示すマークをつけ
なければならない. 単純に値を削除して，空白としてはならない.
9.
(教科書第 8 章)
(1) AVL 木は通常の２分探索木の条件に加えて、
「左右の部分木の高さの差は高々１」という条件を満たさなけれ
ばならない。
(2)
Fh = Fh−1 + Fh−2 + 1
(1)
Fh = fh+2 − 1
(2)
(3)
(4) フィボナッチ木は AVL 木の条件を満たす最もノード数が少ない木である。一方、高さ、h のフィボナッチ木
のノード数は、式 (2) で与えられる。この式は、高さ h の AVL 木の中で最もノード数が少ない木のノード
数を表しており、逆に最もノード数が多い木におけるノード数は Fh+1 である。従って、高さ h の AVL 木
のノード数を N とするとき、
4
fh+2 − 1 ≤ N < 2h − 1
(3)
の関係が成り立つ。
10.
(教科書第 9 章)
(1) データを昇順にソートするものとして説明する. ヒープソートは，配列を用いて，まず (最大のデータから順
に取り出すことができる) ヒープを作成する．次に，ヒープから最大要素の取り出し (deletemax) を実行し，
その取り出されたデータを，deletemax を実行する前の配列中でヒープを構成していた部分の最後に置く. こ
れを繰り返し，配列中でヒープを構成している部分の要素がなくなったとき，ソートが完了する.
(2) ヒープソートの処理量は，O(N log N ) である．これは，次のように証明できる. ソートするデータ数を N と
する. ヒープソートでは，(1) ヒープを作成する処理，(2) ヒープから最大要素を取り出し，配列中のヒー
プ部の最後に置く処理，を実行する. まず，(1) の処理は O(N log N ) のコストで実行できる. これは，1 個
のデータをヒープに投入する際に O(log N ) のコストを要し，それが N 回繰り返されるためである. また，
(2) の処理で，deletemin を 1 回実行する際のコストは O(log N ) である．そこで取り出されたデータをヒー
プ配列の最後の位置に置く処理は，O(1) で実行できる. これが N 回繰り返されることから，(2) の処理
全体の処理量は，O(N log N ) である．(1) と (2) の処理は直列的に実行されることから，全体の処理量は，
O(N log N ) + O(N log N ) となり，結果としてヒープソートの処理量は，O(N log N ) となる．
11.
(教科書第 10 章)
(1) 接続行列を以下に示す．
a
b
c
d
e
a
b
c
d
e
0
1
0
0
1
1
0
1
0
1
0
1
0
1
1
0
0
1
0
1
1
1
1
1
0
(2) MST を以下に示す．
5
(3) (3-1) コスト最小の要素から取り出され，取り出した要素はデータ集合から削除される機能を有していること．
(3-2) 優先順位付きキュー (プライオリティーキュー)
12.
(教科書第 11 章)
(a) 関数 sm の漸近的コストは O(mn) である．
例えば，テキストが’aaaaaaa . . . aaab’，パターンが’aaaaaab’ の場合を考える．テキストの先頭とパターン
の先頭を重ね合わせて，両者を照合する．この場合，パターンの最後の文字でテキストとの不一致が分かる．
この際に，n 回の比較を行うことになる．次に，テキストの 2 文字目とパターンの先頭を重ね合わせて同様
な処理を行う．この処理が繰り返され，テキストの m − n + 1 文字目とパターンの先頭が重ねあわされた場
合にマッチングは成功する．以上をまとめると，アルゴリズム sm での文字の比較回数は n(m − n + 1) と
なり，m À n の仮定から O(mn) となる．但し，O(n(m − n)) も正解とする．
(b) (1) BM 法では，前処理として next 表を作成する．この表は，パターンを解析することにより，テキスト中
の文字との不一致が見つかった時，テキスト上の注目文字位置をいくつ進めるかを示しているもので
ある．
(2) BM 法ではパターンの最後の文字から前に向かってテキスト上の文字との比較を行う．一方，KMP 法
では，パターンの最初の文字から後ろに向かってテキスト上の文字との比較を行う．この点が両者のパ
ターンマッチングでの最も大きな違いである．
6

Download Report