浙江大学2007–2008学年秋季学期《数据结构基础》课程期末考试试卷开课学院：软件学院、计算机、竺可桢学院，考试形式：闭卷，允许带_ 无入场考试时间：_2007_年_11_月_17日, 所需时间： 120 分钟考生姓名： ___学号：专业： ____教师：Answer SheetNOTE: 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; i<n; i++)for(j=i; j>0; j/=2)printf(“%d\n”, 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 pushedinto 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 isH(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 theinorder traversal sequence FDBEACG, the corresponding preorder traversal sequence is . (2 points)a. ABDFEGCb. ABDEFCGc. ABDFECGd. ABCDEFG(6)Insert 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, 2 into an initiallyempty 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 ofT 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 minimumspanning 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, methodcan be used. (2 points)a. Kruskalb. Dijkstrac. Hashingd. Critical Path(10)Among the following sorting algorithms, has the average run timeO(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 <= H->Size; i = Child ){ Child = i * 2;if( ② )Child++;if( LastElement < H->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 orderby Shellsort with Shell’s 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 A[0], A[1],A[2], … A[N-1]. (6 points)int MaxSubsequenceSum(int A[], int N){int ThisSum, MaxSum, j;ThisSum=MaxSum=0;for(j=0; j<N; j++) {ThisSum = ① ;if (ThisSum >MaxSum)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)(1)Please list:(a)the depth-first search sequence;(b)(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 emptybinary 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 invokingUnion(7, 9) with union-by-size. Keep in mind that the elements are numberedfrom 1 to 9. (5 points)(4)Given a list of N elements and an integer k. Please describe two differentalgorithms for finding the kth largest element and give the time complexities.(8 points)IV. If each vertex in an undirected weighted graph has a number of balloons assigned.Explain how to modify Dijkstra's algorithm so that if there is more than one minimum path from v to w, a path with the maximum number of balloons is chosen.(15 points)Note : T[ V ].balloon contains the number of balloons at vertex V.void Dijkstra( Table T )。