For the following piece of code
if ( A > B ){
for ( i=0; i<N*4; i++ )
for ( j=N*N; j>i; j-- )
C += A;
}
else {
for ( i=0; i<N*N/20; i++ )
for ( j=3*N; j>i; j-- )
for ( k=0; k<N*3; k++)
C += B;
}
the lowest upper bound of the time complexity is . (2分)
To sort records, heap sort requires at least extra space. (2分)
The best case time complexity of sorting algorithms based only on comparisons is at least . (2分)
If A
and B
are both leaf nodes in a binary tree, then there exists a binary tree with preorder traversal sequence ...A...B...
and inorder traversal sequence ...B...A...
.
(2分)
If a complete binary tree with 136 nodes is stored in an array (root at position 1), then the node at position 12 precedes the node at position 95 in its preorder traversal sequence. (2分)
If in a directed graph, every vertex is part of some cycle, then the graph must be strongly connected. (2分)
An algorithm to check for balancing symbols in an expression uses a queue to store the partial expression. (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分)
Prim's algorithm is to maintain a forest and to merge two trees into one at each stage. (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
.
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分)
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分)
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分)
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, 16, 6, 25, 20, 7}, which number is placed in the position of index 7? (3分)
Which of the following statements is FALSE about the shortest path algorithms? (3分)
The maximum flow in the network of the given Figure is: (4分)
How many distinct topological sequences are there in the following DAG?(2分)
Which of the following statements is TRUE about topological sorting? (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分)
Given the adjacency list of a directed graph as shown by the figure. There is(are) __ strongly connected component(s). (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分)
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分)
To sort records iteratively by merge sort, the number of runs is: (2分)
If a DFS sequence of a graph is {V1, V4, V0, V3, V2}, then which one of the following can NOT possibly be the corresponding graph? (3分)
Insert {10, 1, 14, 5, 8, 15, 3, 9, 7, 4, 11, 13} into an initially empty binary min-heap one at a time. After performing three DeleteMin operations, and then inserting 6 and 12 into the heap, the top element of the heap must be __ . (2分)
Given a weighted graph as shown by the figure. Which one of the following statements is TRUE about its minimum spanning tree? (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 | 20 | |
D | 15 |
Which algorithm is the fastest for problem size 200? (3分)
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分)
Given a binary tree with 100 leaves and without 1-degree nodes, the number of nodes in the tree is __ . (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 | 答案正确 | 3 |
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
#ifdef PINTIA #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; } #endif /////// int LCA( Tree T, int u, int v ) { int a, b; if (u>v) { a = v; b = u; } else { // u < v a = u; b = v; } // a < b int fa = 0; Tree Ta = T; while (Ta) { if (a > Ta->Key) Ta = Ta->Right; else if (a < Ta->Key) Ta = Ta->Left; else { fa = 1; break; } } int fb = 0; Tree Tb = T; while (Tb) { if (b > Tb->Key) Tb = Tb->Right; else if (b < Tb->Key) Tb = Tb->Left; else { fb = 1; break; } } if (!(fa&&fb)) return ERROR; while (1) { if (T->Key > a && T->Key > b) T = T->Left; else if (T->Key < a && T->Key < b) T = T->Right; else return T->Key; } }
测试点 | 结果 | 得分 | 耗时 | 内存 |
---|---|---|---|---|
0 | 答案正确 | 1 | 4 ms | 356 KB |
1 | 答案正确 | 1 | 3 ms | 256 KB |
2 | 答案正确 | 1 | 3 ms | 256 KB |
3 | 答案正确 | 1 | 2 ms | 256 KB |
4 | 答案正确 | 1 | 2 ms | 256 KB |
5 | 答案正确 | 1 | 4 ms | 256 KB |
6 | 答案正确 | 1 | 3 ms | 368 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); ^~~~~~~~~~~~~~~~~~~~~~