For a sequentially stored linear list of length , the time complexities for query and insertion are and , respectively. (3分)
In a binary search tree, the keys on the same level from left to right must be in sorted (non-decreasing) order. (3分)
If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}. (3分)
and have the same speed of growth. (3分)
In a directed graph, the sum of the in-degrees and out-degrees of all the vertices is twice the total number of edges. (3分)
If an undirected graph G = (V, E) contains 10 vertices. Then to guarantee that G is connected in any cases, there has to be at least __ edges. (6分)
The array representation of a disjoint set is given by { 4, 6, 5, 2, -3, -4, 3 }. If the elements are numbered from 1 to 7, the resulting array after invoking Union(Find(7),Find(1))
with union-by-size and path-compression is: (5分)
Given a quadtree(四叉树) with 2 nodes of degree 2, 3 nodes of degree 3, 4 nodes of degree 4. The number of leaf nodes in this tree is __. (5分)
Insert { 6, 9, 12, 3, 4, 8 } one by one into an initially empty binary search tree. The post-order traversal sequence of the resulting tree is: (6分)
The result of performing three DeleteMin operations in the min-heap {1,3,2,6,7,5,4,15,14,12,9,10,11,13,8} is: (5分)
Which of the following statements is TRUE about topological sorting? (5分)
To insert s
after p
in a doubly linked circular list, we must do: (6分)
In a complete binary tree with 1102 nodes, there must be __ leaf nodes. (6分)
Suppose that an array of size m
is used to store a circular queue. If the head pointer front
and the current size variable size
are used to represent the range of the queue instead of front
and rear
, then the maximum capacity of this queue can be: (5分)
From the given graph shown by the figure, how many different topological orders can we obtain? (5分)
The recurrent equations for the time complexities of programs P1 and P2 are:
Then the correct conclusion about their time complexities is: (5分)
In-order traversal of a binary tree can be done iteratively. Given the stack operation sequence as the following:
push(1), push(2), push(3), pop(), push(4), pop(), pop(), push(5), pop(), pop(), push(6), pop()
Which one of the following statements is TRUE? (6分)
Please fill in the blanks in the program which performs Find
as a Union/Find operation with path compression.
SetType Find ( ElementType X, DisjSet S )
{
ElementType root, trail, lead;
for ( root = X; S[root] > 0; (5分) ) ;
for ( trail = X; trail != root; trail = lead ) {
lead = S[trail] ;
(5分);
}
return root;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 5 |
1 | 答案正确 | 5 |
The function is to find the K
-th largest element in a list A
of N
elements. The function BuildMinHeap(H, K)
is to arrange elements H[1]
... H[K]
into a min-heap. Please complete the following program.
ElementType FindKthLargest ( int A[], int N, int K )
{ /* it is assumed that K<=N */
ElementType *H;
int i, next, child;
H = (ElementType *)malloc((K+1)*sizeof(ElementType));
for ( i=1; i<=K; i++ ) H[i] = A[i-1];
BuildMinHeap(H, K);
for ( next=K; next<N; next++ ) {
H[0] = A[next];
if ( H[0] > H[1] ) {
for ( i=1; i*2<=K; i=child ) {
child = i*2;
if ( child!=K && (5分) ) child++;
if ( (5分) )
H[i] = H[child];
else break;
}
H[i] = H[0];
}
}
return H[1];
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 5 |
1 | 答案正确 | 5 |