In a directed graph, the sum of the in-degrees must be equal to the sum of the out-degrees of all the vertices. (1分)
For a sequentially stored linear list of length , the time complexities for deleting the first element and inserting the last element are and , respectively. (1分)
The Fibonacci number sequence {} is defined as: , , , =2, 3, .... The time complexity of the function which calculates iteratively is . (1分)
Shell sort is stable. (1分)
To sort records by merge sort, the number of merge runs is . (1分)
In hashing, functions "insert" and "find" have the same time complexity. (1分)
If a graph is represented by adjacency lists, then the space taken depends only on the number of vertices, not the number of edges. (1分)
In a graph G, if we have to do BFS twice to visit every one of its vertices, then there must be a cycle in G. (1分)
There exists a binary tree with 2016 nodes in total, and with 16 nodes having only one child. (1分)
Store a complete binary tree in an array (root at position 1). Then the nodes at positions 23 and 24 are siblings. (1分)
What is a collision in hashing? (2分)
If besides finding the shortest path from S
to every other vertices, we also need to count the number of different shortest paths, we can modify the Dijkstra algorithm in the following way: add an array count[]
so that count[V]
records the number of different shortest paths from S
to V
. Then count[V]
shall be initialized as: (3分)
If graph G is NOT connected and has 21 edges, then it must have at least _ vertices. (3分)
Given the adjacency matrix of a weighted graph as shown by the figure. The total weight of its minimum spanning tree is: (2分)
The maximum flow in the network of the given Figure is: (3分)
If the input is a set of 1-digit numbers, which one of the following methods can sort them in time? (2分)
Use the linear algorithm to adjust the given sequence of numbers { 28, 12, 7, 8, 19, 20, 15, 22 } into a max-heap, and then insert 29. The resulting sequence is __. (2分)
Given a quadtree(四叉树) with 3 nodes of degree 2, 2 nodes of degree 3, 4 nodes of degree 4. The number of leaf nodes in this tree is __. (2分)
To check if there is a cycle in a directed graph, which one of the following algorithms can be used, besides the topological sort? (2分)
BFS is similar to the __ traversal of a binary tree. (2分)
For a binary tree, if its pre-order travel sequence is { 4, 2, 1, 3, 6, 5, 7 }, and its in-order travel sequence is { 1, 2, 3, 4, 5, 6, 7 }, then which of the following statement is FALSE? (3分)
To sort the sequence { 2, 12, 16, 88, 5, 10, 34 }, if the results of the first 2 runs are given as the following:
Then the possible sorting method is: (2分)
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? (3分)
In a max-heap with () elements, the array index of the minimum key may be __. (2分)
Given input { 4321, 56, 57, 46, 28, 7, 331, 33, 234, 63 }. Which one of the following is the result after the 1st run of the Least Signification Digit (LSD) radix sort? (2分)
The articulation points of the given graph are: (2分)
Given a hash table of size 17 with the hash function . Quadratic probing () is used to resolve collisions. Then after inserting { 6, 22, 7, 26, 9, 40 } one by one into the hash table, the address of 40 is__. (2分)
Insert { 3, 8, 9, 1, 2, 6 } one by one into an initially empty binary search tree. The post-order traversal sequence of the resulting tree is: (3分)
Given the result of the 1st run of a sorting method as { 19, 21, 7, 14, 5, 27, 1, 10 }. Then among the following, this method has to be: (2分)
Suppose that a polynomial is represented by a linked list storing its non-zero terms. Given two polynimials with and non-zero terms, and the highest exponents being and , respectively. Then the time complexity for multiplying them is: (2分)
If the pushing sequence of a stack is {1, 2, 3, ..., } and the first number being popped out is , then the -th number being popped must be: (2分)
Given the adjacency lists of a directed graph as shown by the figure. Then starting from V1, a possible DFS sequence is: (2分)
To judge an integer () is prime or not, we need to check if it is divisible by any odd number from 3 to . The time complexity of this algorithm is __. (2分)
How many of the following statements is/are TRUE? (3分)
e
is the only shortest edge in the weighted graph G, then e
must be in the minimum spanning tree of G.1 2 3 4 ...
, and if there is an edge between vertices 1 and 4, then there must be an edge between the vertices 1 and 3.The function is to sort the list { r[1] … r[n]
} in non-decreasing order. Unlike selection sort which places only the minimum unsorted element in its correct position, this algorithm finds both the minimum and the maximum unsorted elements and places them into their final positions.
void sort( list r[], int n )
{
int i, j, mini, maxi;
for (i=1; i<n-i+1; i++) {
mini = maxi = i;
for( j=i+1; (3分); ++j ){
if( (3分) ) mini = j;
else if(r[j]->key > r[maxi]->key) maxi = j;
}
if( mini != i ) swap(&r[mini], &r[i]);
if( maxi != n-i+1 ){
if( (3分) ) swap(&r[mini], &r[n-i+1]);
else swap(&r[maxi], &r[n-i+1]);
}
}
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 3 |
1 | 答案正确 | 3 |
2 | 答案错误 | 0 |
Please fill the array with the results after the following union/find operations.
union( find(1), find(5) )
union( find(3), find(6) )
union( find(0), find(1) )
union( find(6), find(5) )
union( find(6), find(4) )
Note: Assume union-by-size
(if two sets are equal-sized, the first root will be the root of the result) and find-with-path-compression
. S[i]
is initialized to be for all .
i |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
S[i] |
(1分) | (1分) | (1分) | (1分) |
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 1 |
1 | 答案正确 | 1 |
2 | 答案正确 | 1 |
3 | 答案正确 | 1 |
A binary tree is said to be "height balanced" if both its left and right subtrees are height balanced, and the heights of its left and right subtrees can differ by at most 1. That is, where and are the heights of the left and right subtrees, respectively. An empty binary tree is defined to be height balanced.
The function IsBalanced
is to judge if a given binary tree T
is height balanced. If the answer is yes then return true
and store the tree height in the parameter pHeight
, else simply return false
. The height of an empty tree is defined to be 0.
typedef struct TNode *BinTree;
struct TNode{
int Key;
BinTree Left;
BinTree Right;
};
bool IsBalanced ( BinTree T, int *pHeight )
{
int LHeight, RHeight, diff;
if( T == NULL) {
*pHeight = 0;
return true;
}
else if ( IsBalanced(T->Left, &LHeight) && IsBalanced(T->Right, &RHeight) ) {
diff = LHeight - RHeight;
if ( (6分) ) {
*pHeight = 1 + ( diff>0 ? (6分) );
return true;
}
else return false;
}
return false;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案错误 | 0 |
1 | 答案正确 | 6 |
Given a binary tree, you are supposed to tell if it is a binary search tree. If the answer is yes, try to find the -th smallest key, else try to find the height of the tree.
int CheckBST ( BinTree T, int K );
where BinTree
is defined as the following:
typedef struct TNode *BinTree;
struct TNode{
int Key;
BinTree Left;
BinTree Right;
};
The function CheckBST
is supposed to return the K
-th smallest key if T
is a binary search tree; or if not, return the negative height of T
(for example, if the height is , you must return ).
Here the height of a leaf node is defined to be 1. T
is not empty and all its keys are positive integers. K
is positive and is never more than the total number of nodes in the tree.
#include <stdio.h>
#include <stdlib.h>
typedef struct TNode *BinTree;
struct TNode{
int Key;
BinTree Left;
BinTree Right;
};
BinTree BuildTree(); /* details omitted */
int CheckBST ( BinTree T, int K );
int main()
{
BinTree T;
int K, out;
T = BuildTree();
scanf("%d", &K);
out = CheckBST(T, K);
if ( out < 0 )
printf("No. Height = %d\n", -out);
else
printf("Yes. Key = %d\n", out);
return 0;
}
/* 你的代码将被嵌在这里 */
3
Yes. Key = 3
2
No. Height = 3
int max(int a, int b){return a > b ? a : b;} int GetHeight( BinTree T) { if(T == NULL) return 0; return max(GetHeight(T->Left), GetHeight(T->Right)) + 1; } int num[100000], cnt; void GetInOrder( BinTree T) { if(T == NULL) return; GetInOrder(T->Left); num[cnt++] = T->Key; GetInOrder(T->Right); } int CheckBST ( BinTree T, int K ) { cnt = 0;GetInOrder(T); for(int i = 0;i < cnt-1;i++) if(num[i] > num[i+1]) return -GetHeight(T); return num[K-1]; }
测试点 | 结果 | 得分 | 耗时 | 内存 |
---|---|---|---|---|
0 | 答案正确 | 3 | 3 ms | 256 KB |
1 | 答案正确 | 3 | 3 ms | 256 KB |
2 | 答案正确 | 1 | 2 ms | 256 KB |
3 | 答案正确 | 2 | 2 ms | 256 KB |
4 | 答案正确 | 1 | 2 ms | 256 KB |
a.c: In function ‘BuildTree’: a.c:35:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &N); ^~~~~~~~~~~~~~~ a.c:36:25: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] for (i=0; i<N; i++) scanf("%d", &postorder[i]); ^~~~~~~~~~~~~~~~~~~~~~~~~~ a.c:37:25: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] for (i=0; i<N; i++) scanf("%d", &inorder[i]); ^~~~~~~~~~~~~~~~~~~~~~~~ a.c: In function ‘main’: a.c:50:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &K); ^~~~~~~~~~~~~~~