复旦大学软件学院 2009~2010学年第一学期期末考试试卷 ■A卷口B卷 课程名称:数据结构与算法设计Ⅱ课程代码:S0FT130004.01 开课院系:软件学院 考试形式:闭卷 姓名 学号 专业 题号1 3 4 6 8总分 得分 ⌒装订线内不要答题 Questions(100 points) 1. A sequence of stack operations is performed on a stack whose size never exceeds k After every k operations, a copy of the entire stack is made for backup purposes. Sho that the cost of n stack operations, including copying the stack, is O(n) by assigning suitable amortized costs to the various stack operations. (5 points)
- 1 - 复旦大学软件学院 2009～2010 学年第一学期期末考试试卷 ■A 卷 □B 卷 课程名称：_数据结构与算法设计Ⅱ______ 课程代码：__ SOFT130004.01______ 开课院系：_软件学院____________ _ 考试形式：闭卷 姓 名： 学 号： 专 业： 题 号 1 2 3 4 5 6 7 8 总 分 得 分 Questions (100 points) 1. A sequence of stack operations is performed on a stack whose size never exceeds k. After every k operations, a copy of the entire stack is made for backup purposes. Show that the cost of n stack operations, including copying the stack, is O(n) by assigning suitable amortized costs to the various stack operations. (5 points) （ 装 订 线 内 不 要 答 题 ）
2. Describe in detail the topological sort algorithm, and what the running time it is when using it to sort the vertices of a DAG Can the topological sort be used to solve the single-source shortest path problem for a DAG with negative edge path costs? Why? (10 points) 3. Give an algorithm to find the minimum number of edges that need to be removed from an undirected graph so that the resulting graph is acyclic. Show that this problem IS NP-complete for directed graphs? (10 points)
- 2 - 2. Describe in detail the topological sort algorithm, and what the running time it is when using it to sort the vertices of a DAG. Can the topological sort be used to solve the single-source shortest path problem for a DAG with negative edge path costs? Why? (10 points) 3. Give an algorithm to find the minimum number of edges that need to be removed from an undirected graph so that the resulting graph is acyclic. Show that this problem is NP-complete for directed graphs? (10 points)
4. What are the two key ingredients that an optimization problem must have in order for dynamic programming to be applicable? Beneath every greedy algorithm, there almost always a more cumbersome dynamic-programming solution. If we can demonstrate what properties the problem has, then we are well on the way to developing a greedy algorithm for it?(10 points) 5. Write pseudocode for Prims algorithm(Minimum spanning tree)and for the procedure MAKE-SET(x), UNION(, y) and FIND-SET(x), which performs the corresponding manipulations on disjoint sets. (10 points)
- 3 - 4. What are the two key ingredients that an optimization problem must have in order for dynamic programming to be applicable? Beneath every greedy algorithm, there is almost always a more cumbersome dynamic-programming solution. If we can demonstrate what properties the problem has, then we are well on the way to developing a greedy algorithm for it? (10 points) 5. Write pseudocode for Prim's algorithm (Minimum spanning tree) and for the procedure MAKE-SET(x), UNION(x, y) and FIND-SET(x), which performs the corresponding manipulations on disjoint sets. (10 points)
6. Consider the following recursive algorithm for finding the shortest weighted path in an acyclic graph, from s to t(15 points) a. Why does this algorithm not work for general graphs? b. Prove that this algorithm terminates for acyclic graph c. What is the worst-case running time of the algorithm? Distance shortest(s, t)i Distance d, tmp; If(S==t) return 0 for each Vertex v adjacent to s i tmp= shortest(v, 1); if(cs, v tmp <dn) d,=Csr+ tn return d
- 4 - 6. Consider the following recursive algorithm for finding the shortest weighted path in an acyclic graph, from s to t. (15 points) a. Why does this algorithm not work for general graphs? b. Prove that this algorithm terminates for acyclic graphs. c. What is the worst-case running time of the algorithm? Distance shortest(s, t) { Distance dt, tmp; If (s = = t) return 0; dt = ∞; for each Vertex v adjacent to s { tmp = shortest(v, t); if (cs,v + tmp < dt) dt = cs,v + tmp; } return dt; }
7. Find all-pairs shortest paths for the following graph by Floyd-Warshall algorithm (15 points) 8 7
- 5 - 7. Find all-pairs shortest paths for the following graph by Floyd-Warshall algorithm (15 points) 7 6 –1 2 –4 8 9 –5 3 4 2 1 5 3
8. Fill the blanks in the following pseudocode of Knuth-Morris-Pratt matching algorithm (10 points) KMP-MATCHERT, P 1.n← length[门 2. length[P] 3.丌← COMPUTE-PREFIX-FUNCTION(P) 4.q←0∥ Number of characters matched rl← I to n do while 6789 and Pla+1]≠T[ if Pla+1=r[ then 012 if(d then print"Pattern occurs with shift"i-m 9. Find the minimum cost flow and the corresponding total cost which can ship 10 units from the source s to the sink t in the following network. Hint if y is the cost of sending one unit of flow across the edge(u, v), then the cost of sending one unit of flow across (1,7) 6,2
- 6 - 8. Fill the blanks in the following pseudocode of Knuth-Morris-Pratt matching algorithm. (10 points) 9. Find the minimum cost flow and the corresponding total cost which can ship 10 units from the source s to the sink t in the following network. Hint: if y is the cost of sending one unit of flow across the edge (u, v), then the cost of sending one unit of flow across the edge (v, u) is –y. (15 points) KMP-MATCHER(T, P) 1. n ← length[T] 2. m ← length[P] 3. π ← COMPUTE-PREFIX-FUNCTION(P) 4. q ← 0 // Number of characters matched. 5. for i ← 1 to n 6. do while (a) and P[q + 1] ≠ T[i] 7. do (b) 8. if P[q + 1] = T[i] 9. then (c) 10. if (d) 11. then print "Pattern occurs with shift" i − m 12. (e) (6, 2) (2, 4) (1, 7) (3, 10) (2, 5) (1, 8) (4, 10) 3 1 s 2 t cost capacity
