浙江大学2007–2008学年秋季学期 数据结构基础 课程期末考试试卷
- 格式：doc
- 大小：133.50 KB
- 文档页数：6
浙江大学2007–2008学年秋季学期
《数据结构基础》课程期末考试试卷
开课学院： 软件院、计算机、竺可桢学院 ，考试形式：闭卷，允许带_ 无 入场
考试时间：_2007_年_11_月_17日, 所需时间： 120 分钟
考生姓名： ___学号： 专业： ____教师：
题序 一 二 三 四 总 分
得分
评卷人
Answer Sheet
Part I
1. c 2. a 3. d 4. d 5. c
6. b 7. a 8. b 9. b 10. c
Part II
1.
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 + A[j]
ThisSum = 0
Part III
1.
(a) ABEDHIFCGJ
(b)ABDEHFICGJ
1.
(c)
A B C
D E F G
H I J 4 4 7 4
5 4
4 1 2 2. (a)
2. (b)
or
3.
{ 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 the element must be in S2,
recursively find it from S2.
If k=|S2|+1, then return the pivot.
If k>|S2|, then it’s in S1 and it’s the
(|S1|-N+k)-th largest element.
Recursively find it from S1.
Average = O(N). Worst=O(N2).
4. (b)
40
28
6
3 38 72
100
80
91 40
28
6
3 38 100
80
91
40
28
6
3 38 80
100
91 Part IV
void Dijkstra( Table T )
{/* T[ ].Count is initialized to be 0. T[start].Count = T[start].balloon */
vertex v, w;
for ( ; ; ) {
v = smallest unknown distance vertex;
if ( v == NotAVertex )
break;
T[v].Known = True;
for ( each w adjacent to v )
if( !T[w].Known )
if( T[v].Dist + Cvw < T[w].Dist ) {
Decrease( T[w].Dist to T[v]+Cvw )
T[w].Path = v;
T[w].Count = T[v].Count + T[w].balloon;
}
else if( ( T[v].Dist + Cvw == T[w].Dist )
&& ( T[v].Count + T[w].balloon > T[w].Count ) ) {
T[w].Count = T[v].Count + T[w].balloon;
T[w].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; 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 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. 6 b. 5 c. 4 d. 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. 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
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. 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
T can be . (2 points)
a. at most log2(N)+1 b. at least log2(N)+1
c. as large as N d. 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 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, 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)
a. Quick sort b. Heap sort c. Merge sort d. Insertion sort
