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))
MaxElement = c
;
LastElement = H->Elements[ H->Size-- ];
for( i = 1; i * 2 <= H->Size; i = Child )
{ Child = i * 2;
if( d
)
Child++;
if( LastElement < H->Elements[ Child ] )
minimum
spanning tree(s) of G. (2 points)
a. only one
b. one or more
c. more than one d. zero or more
(9) To find the shortest path between a pair of given vertices,
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++ ) {
d
;
}
return MaxSum;
}
III. Please write or draw your answers for the following problems on the answer sheet. (41 points)
(1) In the given graph, start from vertex A,
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. 6
b. 5
c. 4
d. 3
(4) Suppose that the size of a hash table is 11, and the hash function is
(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;
(4) Given a list of N elements and an integer k. Please describe two different algorithms for finding the kth largest element and give the time complexities. (8 points)
(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
int MaxSubsequenceSum(int A[], int N) {
int ThisSum, MaxSum, j; ThisSum=MaxSum=0;
for(j=0; j<N; j++) {
ThisSum = c
;
if (ThisSum >MaxSum)
MaxSum= ThisSum;
else if (ThisSum <0)
浙江大学 2007–2008 学年秋季学期
《数据结构基础》课程期末考试试卷
开课学院： 软件学院、计算机、竺可桢学院 ，考试形式：闭卷，允许带_ 无 入场
考试时间：_2007_年_11_月_17 日, 所需时间： 120 分钟
考生姓名：
___学号：
专业：
____教师：
题序
一
二
三
四
总分
得分
评卷人
Answer Sheet
operations, the last element of the heap is
. (2 points)
a. 10
b. 11
c. 8
d. 5
(7) Let T be a tree created by union-by-size with N nodes, then the height of
with key=49 will be
. (2 points)
a. 4
b. 7
c. 8
d. 10
(5) For a binary tree, given the postorder traversal sequence FDEBGCA and the
inorder traversal sequence FDBEACG, the corresponding preorder traversal
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.
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++)
Tmp = A[ i ]; for ( j = i; c
if(d
; j - = Increment ) )
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)
(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 Union(7, 9) with union-by-size. Keep in mind that the elements are numbered from 1 to 9. (5 points)
method
can be used. (2 points)
a. Kruskal
b. Dijkstra
c. Hashing
d. Critical Path
(10) Among the following sorting algorithms,
has the average run time
O(NlogN) with O(N) extra spaces. (2 points)
4
Please list:
D
(a) the depth-first search sequence;
2
(b) the breath-first search sequence; and
(c) the minimum spanning tree.
A 5
7
B
C
64
11 5
7
E4
F
31
6
6 5
H
4
I
J
4 8G
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