アルゴリズムとデータ構造

アルゴリズムと
データ構造
第15回
総合演習
木の復習
木の再帰的定義
 親子関係兄弟経路と経路の長さ先祖と子孫先祖と子孫
 順序木と無順序木
 木の探索（走査）
 行きがけ順
 通りがけ順
 帰りがけ順
 木のデータ構造
 親へのポインタによる木の表現
 子のリストによる木の表現
 木の操作
 ノードの探索
 ノードの挿入
前回の演習問題
解説
行きがけ順
24
12
5
39
16
7
24
12
5
30
20
7
16
20
28
39
50
33
30
44
28
33
50
44
解説
通りがけ順
24
12
5
39
16
7
5
7
12
30
20
16
20
24
28
28
50
33
30
44
33
39
44
50
解説
帰りがけ順
24
12
5
39
16
7
7
5
20
30
20
16
12
28
28
33
50
33
30
44
44
50
39
24
解説
挿入：44
挿入：31
挿入：40
挿入：39
挿入：16
挿入：9
挿入：6
挿入：20
挿入：13
挿入：28
28
13
44
6
20
9
16
39
31
40
｛28, 44, 13, 20, 6, 9, 16, 39, 40, 31｝を順に挿入
解説
挿入：40
挿入：28
挿入：44
挿入：13
挿入：20
挿入：6
挿入：9
挿入：16
挿入：39
挿入：31
31
16
9
6
40
20
13
39
44
28
｛28, 44, 13, 20, 6, 9, 16, 39, 40, 31｝を逆順に挿入
先週の演習問題の答え
総合演習
（40分くらいで完成させ）
第１問
第２問
第３問
第4問
解説
第１問
enqueue
dequeue
0
1
2
3
4
5
87
14
34
40
26
59
rear rear rear
front front front
3
答え：
61
6
87
14
7
8
9
10
11
3
61
front front
第2問の解説
（1）
15を挿入
61を挿入
70を挿入
58を挿入
21を挿入
ハッシュ値1
ハッシュ値5
再ハッシュ値7
ハッシュ値0
ハッシュ値2
ハッシュ値7
再ハッシュ値9
再ハッシュ値11
（２）
0
1
2
70
15
58
70
15
58
3
4
5
46
33
6
7
8
9
10
11
12
91
61
66
21
12
61
61
21
61
21
衝突
衝突
衝突
13
21
15を挿入
61を挿入
70を挿入
58を挿入
21を挿入
ハッシュ値1
ハッシュ値5
再ハッシュ値8
ハッシュ値0
ハッシュ値2
ハッシュ値7
再ハッシュ値10
再ハッシュ値13
答え：
0
1
2
70
15
58
70
15
58
3
4
5
46
6
7
8
9
10
33
91
61
66
61
21
61
21
衝突
衝突
衝突
11
12
13
12
21
21
第3問の解説
recur(-1) : （何も実行されない）
recur(0) : （何も実行されない）
recur(1) : 1 recur(0) recur(-1)
→
1
recur(2) : 2 recur(1) recur(0)
→
2 1
21
recur(3) : 3 recur(2) recur(1)
→
3 21
3211
recur(4) : 4 recur(3) recur(2)
→
4 3211
4321121
recur(5) : 5 recur(4) recur(3)
→
5 4321121 3211
543211213211
recur(6) : 6 recur(5) recur(4)
→
665432112132114321121
543211213211 4321121
答え：
1
21
第4問の解説
int fibonacci(int n) {
if ( n == 1 || n == 2 ) /* n が 1 または 2 の場合 */
return ( 1 );
else if (n >= 3) /* n が 3 以上の場合（再帰） */
return (fibonacci(n - 2) + fibonacci(n - 1) );
else
/* 無効な n の場合の処理 */
return (-1);
}
答え：
学期末試験に関する説明
2014年8月4日（月）午前８：４５～１０：１５（90分）
出題範囲
1. アルゴリズムの計算量、フローチャート
2. 配列
3. 多次元配列, 構造体、配列によるリスト
4. ポインタによるリスト、循環・重連結リスト
5. スタック、キュー
6. 探索
7. 再帰的アルゴリズム
8. ソート：単純なソートアルゴリズム、バケットソート、基数ソート、シェルソート、クイックソート
9. 文字列処理
10. 木構造
注意事項
1. 講義ノート，参考図書，講義資料，電卓，計算機などの持ち込みは一切不可。
2. 学期末試験を受験するためには、学生証を提示しなければならない。
3．試験開始10分前までに試験室に入室し、監督者が指定した席（基本的に、学籍番号順）
に着席しなければならない。
4. 試験開始後20分を経過した遅刻者は、事情の如何を問わず、入室および受験できない。
5. 試験開始後30分を経過しないと退室できない。

Download Report