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

アルゴリズムと
データ構造
第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分くらいで完成させ)
第1問
第2問
第3問
第4問
解説
第1問
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
(2)
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日(月) 午前 8:45 ~ 10:15 (90分)
出題範囲
1. アルゴリズムの計算量、フローチャート
2. 配列
3. 多次元配列, 構造体、 配列によるリスト
4. ポインタによるリスト、循環・重連結リスト
5. スタック、キュー
6. 探索
7. 再帰的アルゴリズム
8. ソート:単純なソートアルゴリズム、バケットソート、基数ソート、シェルソート、クイックソート
9. 文字列処理
10. 木構造
注意事項
1. 講義ノート,参考図書,講義資料,電卓,計算機などの持ち込みは一切不可。
2. 学期末試験を受験するためには、学生証を提示しなければならない。
3. 試験開始10分前までに試験室に入室し、監督者が指定した席(基本的に、学籍番号順)
に着席しなければならない。
4. 試験開始後20分を経過した遅刻者は、事情の如何を問わず、入室および受験できない。
5. 試験開始後30分を経過しないと退室できない。