浙江大学2007–2008学年秋季学期 数据结构基础 课程期末考试试卷 (2).doc

浙江大学20072008学年秋季学期数据结构基础课程期末考试试卷开课学院： 软件院、计算机、竺可桢学院 ，考试形式：闭卷，允许带_ 无 入场考试时间：_2007_年_11_月_17日, 所需时间： 120 分钟考生姓名： _学号： 专业： _教师： 题序一二三四总 分得分评卷人Answer SheetPart I1. c2. a3. d4. d5. c6. b7. a8. b9. b10. cPart II1. H-Elements 1 Child != H-Size & H-Elements Child + 1 H-Elements Child H-Elements i = H-Elements Child 2. j = Increment Tmp A j - Increment 3. ThisSum + Aj ThisSum = 0 Part III1. (a) ABEDHIFCGJ(b)ABDEHFICGJ1.ABCDEFGHIJ447454412(c) 2. (a)402863387210080914028633810080912. (b)402863388010091or3. 2, 4, 2, 2, -5, 5, 6, 9, 5 4. (a)Build max heap and call DeletMax for k times.O(N+k logN)Keep a min heap of k elements. Compare a new element with the root and, DeletMin and Insert the new element if the new one is larger.O(N logk)Sort and take the kth largest.O(N logN)Take a pivot and partition the set as in Quicksort.If k|S2|, then its in S1 and its the (|S1|-N+k)-th largest element. Recursively find it from S1.Average = O(N). Worst=O(N2).4. (b)Part IVvoid Dijkstra( Table T )/* T .Count is initialized to be 0. Tstart.Count = Tstart.balloon */vertex v, w;for ( ; ; ) v = smallest unknown distance vertex; if ( v = NotAVertex ) break; Tv.Known = True; for ( each w adjacent to v ) if( !Tw.Known ) if( Tv.Dist + Cvw Tw.Count ) ) Tw.Count = Tv.Count + Tw.balloon; Tw.Path = v; /* DO NOT forget this */NOTE: Please write your answers on the answer sheet.注意：请将答案填写在答题纸上。I. Please select the answer for the following problems. (20 points) (1) The time complexity of the following piece of code is (2 points)for(i=0; i0; j/=2) printf(“%dn”, j);a. O(n)b. O(n*n)c. O(nlogn)d. O(n*i)(2) Suppose that the time complexities of two programs are given by T1(N)=O(f(N) and T2(N)=O(f(N). Which of the following equations is true? (2 points) a. T1(N)+T2(N)=O(f(N)b. T1(N)-T2(N)=o(f(N) c. T1(N)/T2(N)=O(1)d. T1(N)=O(T2(N)(3) Given an empty stack S and an empty queue Q. A list of characters are pushed into S in the order of a, b, c, d, e, f and every character that is popped from S will be inserted into Q immediately. If the output of Q is b, d, c, f, e, a, the minimum capacity of S must be . (2 points) a. 6b. 5c. 4d. 3(4) Suppose that the size of a hash table is 11, and the hash function is H(key)=key%11. The following 4 elements have been inserted into the table as Addr(14)=3, Addr(38)=5, Addr(61)=6, Addr(86)=9. When open addressing with quadratic probing is used to solve collisions, the address of the element with key=49 will be . (2 points) a. 4b. 7c. 8d. 10(5) For a binary tree, given the postorder traversal sequence FDEBGCA and the inorder traversal sequence FDBEACG, the corresponding preorder traversal sequence is . (2 points)a. ABDFEGC b. ABDEFCG c. ABDFECG d. ABCDEFG(6) Insert 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, 2 into an initially empty binary min heap one at a time, after performing three DeleteMin operations, the last element of the heap is . (2 points)a. 10b. 11c. 8d. 5(7) Let T be a tree created by union-by-size with N nodes, then the height of T can be . (2 points)a. at most log2(N)+1b. at least log2(N)+1c. as large as Nd. anything that is greater than 1(8) Given a weighted and connected undirected graph G, there is/are minimum spanning tree(s) of G. (2 points)a. only oneb. one or morec. more than oned. zero or more(9) To find the shortest path between a pair of given vertices, method can be used. (2 points)a. Kruskalb. Dijkstrac. Hashingd. Critical Path(10) Among the following sorting algorithms, has the average run time O(NlogN) with O(N) extra spaces. (2 points)a. Quick sortb. Heap sortc. Merge sortd. Insertion sortII. Given the function descriptions of the following three (pseudo-code) programs, please fill in the blank lines. (24 points)(1) The function is to delete the maximum element in a max heap. (12 points)ElementType DeleteMax( PriorityQueue H ) int i, Child; ElementType MaxElement, LastElement; MaxElement = ; LastElement = H-Elements H-Size- ; for( i = 1; i * 2 Size; i = Child ) Child = i * 2; if( ) Child+; if( LastElement Elements Child ) ; else break; H-Elements i = LastElement; return MaxElement; (2) The function is to sort a list of N elements A in non-decreasing order by Shellsort with Shells increments. (6 points)void Shellsort( ElementType A , int N ) int i, j, Increment; ElementType Tmp; for ( Increment = N / 2; Increment 0; Increment /= 2 ) for ( i = Increment; i N; i+ ) Tmp = A i ; for ( j = i; ; j - = Increment ) if( ) A j = A j - Increment ; else break; A j = Tmp; (3) The function is to find maximum sum value of the subsequence in A0, A1, A2, AN-1. (6 points)int MaxSubsequenceSum(int A, int N) int ThisSum, MaxSum, j;ThisSum=MaxSum=0;for(j=0; jMaxSum)MaxSum= ThisSum;else if (ThisSum 0) ;return MaxSum;III. Please write or draw your answers for the following problems on the answer sheet. (41 points)7ABCDEFGHIJ4645117485646541325(1) In the given graph, start from vertex A,Please list:(a) the depth-first search sequence;(b) the breath-first search sequence; and(c) the minimum spanning tree.Note: All the adjacent vertices are to be visited by alphabetical order.(15 points)(2) Insert the numbers 40, 28, 6, 72, 100, 3, 80, 91, 38 into an initially empty binary search tree. Please show(a)the resulting binary search tree; (10 points) and(b)the resulting binary search tree after 72 is deleted. (3 points)(3) The array representation of the disjoint sets is given by 2, 4, 2, 2, -3, 5, 6, 9, -2 . Please list the resulting array elements after invoking Uni