复旦大学:《数据结构与算法设计》考试样卷_2009-2010年度A卷(答案)

Example Answers of Data Structures and algorithms (Software School, Fundan University, winter, 2009-2010) Questions(100 points) 1. Amortized cost PUSH 2 POP O BUCKUPO 2. Topological sort Step 1: Call depth first search algorithm Step 2: Sort by finishing time Run time: O(n/gn) Yes, it can be used to solve the single-source shortest path problem for a DAG with negative edge path costs because DAG is a directed acyclic graph 3. Find the minimum spanning tree for every connected, undirected graph Count the number of edges that appear in the minimum spanning trees, denoted by x. The minimum number of edges that need to be removed from an undirected graph that the resulting graph is acyclic is E-x 4. Two key ingredients Optimal substructure: Dynamic programming builds an optimal solution to the problem from optimal solutions to subproblems. The solutions to the subproblems used within the optimal solution to the problem must themselves be optima using a"cut-and-paste"technique Subproblems should be independent Overlapping subproblems: Recursive algorithm revisits the same problem over and over again. In contrast, a problem for which a divide-and-conquer approach is suitable usually generates brand-new problems at each step of the recursion For greedy algorithm, we should prove that at any stage of the recursion, one of the optimal choices is the greedy choice. Thus, it is always safe to make the greedy choice Greedy-choice property: A globally optimal solution can be arrived at by making a locally optimal choice(a greedy choice at each step yields a globally optimal solution) 5. Write pseudocode for Prim's algorithm MST-PRIM(G, w, r) for each t∈v[G 2. do keyu 6. while O≠0
Example Answers of Data Structures and Algorithms (Software School, Fundan University, winter, 2009 - 2010) Questions (100 points) 1. Amortized cost PUSH 2 POP 0 BUCKUP 0 2. Topological sort Step 1: Call depth first search algorithm. Step 2: Sort by finishing time. Run time: O(nlgn) Yes, it can be used to solve the single-source shortest path problem for a DAG with negative edge path costs because DAG is a directed acyclic graph. 3. Find the minimum spanning tree for every connected, undirected graph Count the number of edges that appear in the minimum spanning trees, denoted by x. The minimum number of edges that need to be removed from an undirected graph that the resulting graph is acyclic is E – x. 4. Two key ingredients Optimal substructure: Dynamic programming builds an optimal solution to the problem from optimal solutions to subproblems. The solutions to the subproblems used within the optimal solution to the problem must themselves be optimal by using a "cut-and-paste" technique. Subproblems should be independent. Overlapping subproblems: Recursive algorithm revisits the same problem over and over again. In contrast, a problem for which a divide-and-conquer approach is suitable usually generates brand-new problems at each step of the recursion. For greedy algorithm, we should prove that at any stage of the recursion, one of the optimal choices is the greedy choice. Thus, it is always safe to make the greedy choice. Greedy-choice property: A globally optimal solution can be arrived at by making a locally optimal choice (a greedy choice at each step yields a globally optimal solution). 5. Write pseudocode for Prim's algorithm MST-PRIM(G, w, r) 1. for each u ∈ V [G] 2. do key[u] ← ∞ 3. π[u] ← NIL 4. key[r] ← Ø 5. Q ← V [G] 6. while Q ≠ 0

7.dol← EXTRACT-MIN(Q) 8 for each∈Ad/al 9 do ifv E O and w(u, v) rankly 2. then ply 3. else p{x]←y then rankb]← rankly]+1 6. Answer quest a. This algorithm will not work for cyclic graph b. The algorithm is equal to DFS .O(+E) 7. Find all-pairs shortest paths 03729 1122 030-45x=5134 471109 -5 5152 8. Fill the blanks (b)q←x{q (c)q←q+1
7. do u ← EXTRACT-MIN(Q) 8. for each v ∈ Adj[u] 9. do if v ∈ Q and w(u, v) rank[y] 2. then p[y] ← x 3. else p[x] ← y 4. if rank[x] = rank[y] 5. then rank[y] ← rank[y] + 1 6. Answer questions a. This algorithm will not work for cyclic graphs b. The algorithm is equal to DFS. c. O(V + E) 7. Find all-pairs shortest paths 0 3 7 29 1 0 8 16 0 3 0 45 4 7 11 0 9 5 2 2 30 D ⎡ ⎤ ⎢ ⎥ − = − ⎣ ⎦ −− − 1122 5 522 51 34 515 4 5152 π ⎡∅ ⎤ ⎢ ⎥ ∅ ⎢ ⎥ = ⎢ ∅ ⎥ ⎢ ⎥ ⎢ ∅ ⎥ ⎢ ∅⎥ ⎣ ⎦ 8. Fill the blanks (a) q > 0 (b) q ← π [q] (c) q ← q + 1 (d) q = m (e) q ← π [q]

9. Minimum cost flow Path:s→2→1→t,fow:5,cost:4, total:20. Path:s→l→t,flow:2,cost:5, total:10 Path:s→2→3→t,flow:3,cost:6, total:18 Total cost 48
9. Minimum cost flow Path: s → 2 → 1 → t, flow: 5, cost: 4, total: 20. Path: s → 1 → t, flow: 2, cost: 5, total: 10. Path: s → 2 → 3 → t, flow: 3, cost: 6, total: 18. Total cost: 48
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 复旦大学:《数据结构与算法设计》考试样卷_2009-2010年度A卷(试卷).pdf
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)移动商务介绍(概念及其特点、移动商务与电子商务、价值链及商业模式).ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)无线局域网补充删节版本.ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)移动电话通信原理(补充资料).ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Wide Area Networks(WANs).ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Ethernet LANs.ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Topics Covered(胥正川).ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Networked Applications.ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Network Management.ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Security.ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)TCP/IP Internetworking.ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)TCP/IP Internetworking.ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)TCP/IP Internetworking.ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Wide Area Networks(WANs).ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Wide Area Networks(WANs).ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Wide Area Networks(WANs).ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Telecommunications.ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Telecommunications.ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Telecommunications.ppt
- 复旦大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Wireless LANs(WLANs).ppt
- 复旦大学:《数据结构与算法设计》实验设计_Lab 1. Stack.pdf
- 复旦大学:《数据结构与算法设计》实验设计_Lab 2. Divide and Conquer.pdf
- 复旦大学:《数据结构与算法设计》实验设计_Lab 3. Hash Tables.pdf
- 复旦大学:《数据结构与算法设计》实验设计_Lab 4. Binary Search Trees.pdf
- 复旦大学:《数据结构与算法设计》实验设计_Lab 5. Red-Black Tree.pdf
- 复旦大学:《数据结构与算法设计》实验设计_Lab 6. Greedy Algorithms.pdf
- 复旦大学:《数据结构与算法设计》实验设计_Lab 7. Single-Source Shortest Paths.pdf
- 复旦大学:《数据结构与算法设计》实验设计_Lab 8. String Matching.pdf
- 复旦大学:《数据结构与算法设计》综合项目_Project1. Combining quicksort with insertion sort.pdf
- 复旦大学:《数据结构与算法设计》综合项目_Project2. English-Chinese dictionary based on binary search tree.pdf
- 复旦大学:《数据结构与算法设计》综合项目_Project3. All-pairs shortest path.pdf
- 复旦大学:《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 01 Algorithm analysis and recurrences.pdf
- 复旦大学:《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 02 Divide-and-conquer design paradigm.pdf
- 复旦大学:《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 03 Basic data structure - Elementary data structures.pdf
- 复旦大学:《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 04 Soring.pdf
- 复旦大学:《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 05 Hash tables.pdf
- 复旦大学:《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 06 Binary search trees.pdf
- 复旦大学:《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 07 Amortized analysis.pdf
- 复旦大学:《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 08 Dynamic programming.pdf
- 复旦大学:《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 09 Greedy algorithms.pdf