哈工大深圳算法设计与分析08年试卷答案-何震宇.docVIP

08算法答案 B D A B C 6、 Linear probing Quadratic probing 7、 8、Two stacks can be implemented in a single array without overflows occurring if they grow from each end and towards the middle. 9、The elements of dynamic programming: optimal substructure, overlapping sub-problems The elements of greedy programming: optimal substructure, greedy choice property They share the optimal substructure property, but we may not use dynamic programming when a greedy solution suffices, or reverse. The greedy choice property is that a globally optimal solution can be arrived at by making a locally optimal (greedy) choice. We must prove that a greedy choice at each step yields a globally optimal solution. First consider a globally optimal solution, and then modify the optimal solution, to make it to begin as a greedy choice. 10、Any minimum spanning tree algorithm is OK. 11、Searching(A) for i1 to length(A) do if A[i] = v return i return NIL Loop invariant proof: Initialization: Loop invariant holds before the first loop iteration. Now i=1, if A[i] = v, then we return the index 1, if A[i]! = v, then until now we are sure that there is no v in the array! Maintenance: Each iteration maintains the loop invariant. The for loop compare v to the current array element A[i], to make sure there is no v in A[1…i-1], if A[i] = v, then we return the index i. Termination: If there is an element matched, the index is returned from early detect, or the program will return a NIL if we come to the end. So the loop invariant holds. 12、Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(αn) + T((1 - α)n) + cn, where α is a constant in the range 0 α 1 and c 0 is also a constant Because α is uncertain ,there is three situations: a. 0 α 1/2 b. α = 1/2 c. 1 α 1/2 The value of α will influence the height of the recursion tree ,but the final answer is the same, so we just consider α = 1/2 here. From the recursion tr