1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta name="generator" content=
"HTML Tidy for Linux/x86 (vers 1st December 2004), see www.w3.org" />
<meta http-equiv="Content-Type" content="text/html; charset=big5" />
<link rel="stylesheet" href="../../c/exam.css" type="text/css" />
<title>借助 algotutor 製作的小考範例</title>
</head>
<body>
<h1>借助 algotutor 製作的小考範例</h1>
<hr />
<p>Algotutor 對於教師出考題也很有幫助。 教師可以用 gen_at_graph
產生一個很大的亂數圖檔, 在某個演算法進行到一半的時候,
詢問學生下一步會發生什麼事。 如果要用傳統手工的方式做這件事,
成本效益顯得太低。 以下的例子就是作者用 algotutor
所製作的小考考題的一部分。</p>
<hr />
<p>圖一: <img src="q61.png" alt="圖一" /></p>
<p>圖二: <img src="q62.png" alt="圖二" /></p>
<ol>
<li>圖一是 Dijkstra's algorithm for single source shortest path
problem 進行到一半時的狀況。 接下來要將 L 從 Fringe 取出, 把它變成
visited。 請問 L 的每個鄰居 (除了它的 parent 之外) 會有何變化?
<ul>
<li>__ 的狀態不改變; ____ 成為一條 back edge;</li>
<li>__ 從 unseen 變成 fringe, value 成為 __;</li>
<li>__ 的 parent 從 __ 變成 __, value 從 __ 變成 __</li>
<li>...</li>
</ul>
</li>
<li>繼續進行, 又拍到圖二。 此時 H 剛從 fringe 變成 visited,
它的所有鄰居只剩下 I 還沒有處理, 而 heap 內容為: W 8, C 9, P 13, U
11, N 10, I 14, S 13, Q 11 共 8 個元素。 請描述處理 I 之後, graph
與 heap 各會發生什麼變化?</li>
<li>對 <a href="q63.gr">一個 graph</a> 進行 Prim's algorithm 建立
minimal spanning tree。 從 G 出發; 進行到一半時拍到圖三。 此時的
heap 內容為: S 1, J 2, W 4, E 3, O 2, L 8, A 4, R 8, M 3, B 7 共 10
個元素。 現在即將從 fringe 當中取出 S, 將它變成 visited。 請畫出
「取出 S」 前後, heap 的內容, 並請標示出元素上升/下降的路徑。</li>
<li>請列出 S 每個 neighbor (除了它的 parent 之外) 的變化:
<ul>
<li>__ 的狀態不改變; ____ 成為一條 back edge;</li>
<li>__ 從 unseen 變成 fringe, value 成為 __;</li>
<li>__ 的 parent 從 __ 變成 __, value 從 __ 變成 __</li>
<li>... 等等</li>
</ul>
</li>
</ol>
<p>圖三: <img src="q63.png" alt="圖三" /></p>
</body>
</html>
|
