The best case time complexity of sorting algorithms based only on comparisons is at least . (2分)
To sort records, heap sort requires at least extra space. (2分)
If a complete binary tree with 137 nodes is stored in an array (root at position 1), then the nodes at positions 127 and 128 are at the same level. (2分)
If in a directed graph, every vertex is part of some cycle, then the graph must be strongly connected. (2分)
For the following piece of code
if ( A > B ){
for ( i=0; i<N*2; i++ )
for ( j=N*N; j>i; j-- )
C += A;
}
else {
for ( i=0; i<N*N/2; i++ )
for ( j=N; j>i; j-- )
for ( k=0; k<N*100; k++)
C += B;
}
the lowest upper bound of the time complexity is . (2分)
Prim's algorithm is to grow the minimum spanning tree by adding one edge, and thus an associated vertex, to the tree in each stage. (2分)
An algorithm to check for balancing symbols in an expression uses a queue to store the partial expression. (2分)
If X
and Y
are both leaf nodes in a binary tree, then there exists a binary tree with preorder traversal sequence ...X
...Y
... and postorder traversal sequence ...Y
...X
.... (2分)
Given a hash table with size 13. If only the positions with odd (奇数) indices are occupied (the index starts from 0), then when the quadratic probing is used, insertion of a new key into this hash table can be successful. (2分)
Given two sorted lists and , the fastest algorithm for computing has time complexity . (2分)
To sort records iteratively by merge sort, the number of runs is: (2分)
Insert 6 keys {23, 80, 95, 90, 82, 76} into an initially empty binary search tree. Suppose that the structure of the resulting tree is given in the figure. Which one of the followings is the possible sequence of insertions? (4分)
Insert {6, 15, 3, 9, 7, 4, 12, 10, 15, 14, 5, 13} into an initially empty binary min-heap one at a time. After performing three DeleteMin operations, and then inserting 8 and 11 into the heap, the top element of the heap must be __ . (2分)
Given a binary tree with 100 leaves and without 1-degree nodes, the number of nodes in the tree is __ . (3分)
Given input { 4321, 56, 57, 46, 289, 17, 331, 33, 234, 63 }. Which one of the following is the result after the 1st run of the Least Signification Digit (LSD) radix sort? (3分)
The array representation of the disjoint sets is given by {2, –4, 2, 3, -3, 5, 6, 9, -2}. Keep in mind that the elements are numbered from 1 to 9. After invoking Union(Find(4), Find(6)) with union-by-size, which elements will be changed in the resulting array? (3分)
If a DFS sequence of a graph is {V2, V0, V4, V3, V1}, then which one of the following can NOT possibly be the corresponding graph? (3分)
Which of the following statements is TRUE about topological sorting? (3分)
How many distinct topological sequences are there in the following DAG?(2分)
Let A
and B
be the two distinct nodes in a binary tree. A
will be visited before B
in the inorder traversal if __。 (3分)
Note: Let R
be the nearest common ancestor of A
and B
. "A
is on the right (or left) of B
" means that A
is in the right (or left) subtree of R
and B
in the left (or right) subtree of R
.
Given a hash table of size 13 and the hash function h(x)=x mod 13. Assume that quadratic probing is used to solve collisions. After filling in the hash table one by one with input sequence {2, 15, 3, 29, 6, 25, 33, 7}, which number is placed in the position of index 7? (3分)
Insert {5, 6, 7, 2, 4, 3} one by one into an initially empty binary search tree. The postorder traversal sequence of the resulting tree is _ (3分)
Given the adjacency list of a directed graph as shown by the figure. There is(are) __ strongly connected component(s). (3分)
Given an empty stack S and an empty queue Q. Push elements {1, 2, 3, 4, 5, 6, 7} one by one onto S. If each element that is popped from S is enqueued onto Q immediately, and if the dequeue sequence is {3, 2, 6, 5, 7, 4, 1}, then the minimum size of S must be: (3分)
The maximum flow in the network of the given Figure is: (4分)
Use Dijkstra's algorithm to find the shortest paths from vertex a
to other vertices. In which order that the results must be obtained?(4分)
If the preorder and the postorder traversal sequences of a binary tree have exactly the opposite order, which of the followings is TRUE about the tree? (3分)
Which of the following statements is FALSE about the shortest path algorithms? (3分)
Given the following four algorithms with their runtimes for problem size 100 and their time complexities:
Algorithm | Runtime | Time Complexity |
---|---|---|
A | 100 | |
B | 50 | |
C | 25 | |
D | 10 |
Which algorithm is the fastest for problem size 200? (3分)
Given a weighted graph as shown by the figure. Which one of the following statements is TRUE about its minimum spanning tree? (3分)
The function is to find the K
-th largest element in a list A
of N
elements. The initial function call is Qselect(A, K, 0, N-1)
. Please complete the following program.
ElementType Qselect( ElementType A[], int K, int Left, int Right )
{
ElementType Pivot = A[Left];
int L = Left, R = Right+1;
while (1) {
while ( A[++L] > Pivot ) ;
(3分);
if ( L < R ) Swap( &A[L], &A[R] );
else break;
}
Swap( &A[Left], &A[R] );
if ( K < (L-Left) )
return Qselect(A, K, Left, R-1);
else if ( K > (L-Left) )
(3分);
else
return Pivot;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 3 |
1 | 答案错误 | 0 |
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 && (3分) ) child++;
if ( (3分) )
H[i] = H[child];
else break;
}
H[i] = H[0];
}
}
return H[1];
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案错误 | 0 |
1 | 答案正确 | 3 |
The lowest common ancestor (LCA) of two nodes u
and v
in a tree T
is the deepest node that has both u
and v
as descendants. Given any two nodes in a binary search tree (BST), you are supposed to find their LCA.
int LCA( Tree T, int u, int v );
where Tree
is defined as the following:
typedef struct TreeNode *Tree;
struct TreeNode {
int Key;
Tree Left;
Tree Right;
};
The function LCA
is supposed to return the key value of the LCA of u
and v
in T
. In case that either u
or v
is not found in T
, return ERROR
instead.
#include <stdio.h>
#include <stdlib.h>
#define ERROR -1
typedef struct TreeNode *Tree;
struct TreeNode {
int Key;
Tree Left;
Tree Right;
};
Tree BuildTree(); /* details omitted */
int LCA( Tree T, int u, int v );
int main()
{
Tree T;
int u, v, ans;
T = BuildTree();
scanf("%d %d", &u, &v);
ans = LCA(T, u, v);
if ( ans == ERROR ) printf("Wrong input\n");
else printf("LCA = %d\n", ans);
return 0;
}
/* Your function will be put here */
2 7
LCA = 6
1 9
Wrong input
int a[1000],now=0; void make(Tree T){ if(T==NULL)return; make(T->Left); a[now++]=T->Key; make(T->Right); } int LCA( Tree T, int u, int v ){ make(T); int i,flag1=0,flag2=0; for(i=0;i<now;i++){ if(a[i]==u)flag1=1; if(a[i]==v)flag2=1; } if(flag1==0||flag2==0)return ERROR; if(T==NULL)return ERROR; if(u<=T->Key&&v>=T->Key)return T->Key; if(u>=T->Key&&v<=T->Key)return T->Key; if(u<T->Key&&v<T->Key)return LCA(T->Left,u,v); if(u>T->Key&&v>T->Key)return LCA(T->Right,u,v); else return ERROR; }
测试点 | 结果 | 得分 | 耗时 | 内存 |
---|---|---|---|---|
0 | 答案正确 | 1 | 2 ms | 256 KB |
1 | 答案正确 | 1 | 3 ms | 384 KB |
2 | 答案正确 | 1 | 2 ms | 256 KB |
3 | 答案正确 | 1 | 2 ms | 256 KB |
4 | 答案正确 | 1 | 3 ms | 256 KB |
5 | 答案正确 | 1 | 3 ms | 256 KB |
6 | 答案正确 | 1 | 2 ms | 256 KB |
7 | 答案正确 | 1 | 2 ms | 256 KB |
a.c: In function ‘BuildTree’: a.c:35:6: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &n); ^~~~~~~~~~~~~~~ a.c:37:10: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &x); ^~~~~~~~~~~~~~~ a.c: In function ‘main’: a.c:51:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d %d", &u, &v); ^~~~~~~~~~~~~~~~~~~~~~