加載中. ..
PDF
學號： 姓名：
國立中山大學 101 學年度第 2學期資訊工程學系資工數學期末考
2012/06/20
1. Define the Bellman’s Minimality Principle (Optimality Principle), and take
an example (5%)
2. (a) Use adjacency matrix to express Fig. 1. (10%)
(b) What is the edge incidence list? (5%)
(c) What is the vertex incidence list? (5%)
3. What are the “Graph”? “Digraph”? Define them and take an example for
each term. (5%)
4. What are the “walk”, “trail”, “path” and “cycle”? Define them and take an
example for each term. (5%)
Note: From Question. 5 to Question. 8, you get “zero” if you only write
the answer. You have to show all the steps as examples in textbook.
b a
d
Fig. 1
c
e
學號： 姓名：
5. Use Moore’s BFS Algorithm to find the shortest path from vertex s to
vertex t, and the shortest path’s length in Fig.2. Show all the steps, step by
step. (10 %)
6. Use Dijkstra’s algorithm to solve the Fig. 3 single-source shortest path
problem (Show: (I) PL and TL in every step. (II) Show every subgraph in
each step.)
(a). from vertex “a” to vertex “b”, ”c”, ”d”, ”e” and “f”.(10%)
(b). from vertex “f” to vertex “a”, ”b”, ”c”, ”d” and “e”.(10%)
a b
e
d f
c
3
2
2 3
3
5
1
2
1
Fig. 3
Fig. 2
s
t
學號： 姓名：
7. Use Greedy algorithm (Kruskal’s algorithm) to construct the shortest
spanning tree for Fig. 3. (20%) (Show: (I) Length sorting table. (II) Show
every subgraph in each step. (III) Show Double Labels as shown in
Example, for example, every root in separate trees, and update the root
whenever connecting two separate trees into a tree.)
8. Use Prim’s algorithm to construct the shortest spanning tree for Fig. 4,
suppose the initial vertex is “a” (20%) (Show: (I) the label of verities and
(II) every subgraph in each step.)
9. What are the differences between shortest path problem and shortest
spanning tree problem? Show those differences by an example. (5%)
10. What are the differences between Greedy algorithm (Kruskal’s algorithm)
and Prim’s Algorithm. (10%)
b
c
e
f
d
Fig. 4
a
10
5
19
18
11
16
21
1433
6
b c
g
d
f e
6 2
2 8
Fig. 3
a
5
10
4
7 5