If the most commonly used operations are to visit a random position and to insert and delete the last element in a linear list, then sequential storage works the fastest. (2分)
If the postorder and inorder traversal sequences of a binary tree are the same, then none of the nodes in the tree has a left child. (2分)
Given the input sequence onto a stack as {1, 2, 3, ..., }. If the first output is , then the -th output must be . (2分)
is . (2分)
The best "worst-case time complexity" for any algorithm that sorts by comparisons only must be . (2分)
If on the 9th level of a complete binary tree (assume that the root is on the 1st level) there are 100 leaf nodes, then the maximum number of nodes of this tree must be: (6分)
Which one of the following relations is correct about the extra space taken by heap sort, quick sort and merge sort? (3分)
Given the pushing sequence of a stack as {1, 2, 3, 4, 5}. If the first number being popped out is 4, then the last one out must be: (3分)
The array representation of a disjoint set containing numbers 0 to 8 is given by { 1, -4, 1, 1, -3, 4, 4, 8, -2 }. Then to union the two sets which contain 6 and 8 (with union-by-size), the index of the resulting root and the value stored at the root are: (6分)
Given a tree of degree 3. Suppose that the numbers of nodes of degrees 1, 2 and 3 are 5, 3 and 2, respectively. Then the number of leaf nodes must be: (6分)
Suppose that the level-order traversal sequence of a min-heap is {1, 3, 2, 5, 4, 7, 6}. Use the linear algorithm to adjust this min-heap into a max-heap. The inorder traversal sequence of the resulting tree is: (6分)
Among the following sorting methods, which one may cause that none of the elements are at their final positions before the last run begins? Assume that there are more than 2 elements to be sorted. (3分)
Suppose that the height of a binary tree is (the height of a leaf node is defined to be 1), and it has only the nodes of degrees 0 and 2. Then the minimum and maximum possible total numbers of nodes are: (6分)
Insert {5, 2, 7, 3, 4, 1, 6} one by one into an initially empty min-heap. The preorder traversal sequence of the resulting tree is: (6分)
To delete p
from a doubly linked list, we must do: (6分)
Given input { 321, 156, 57, 46, 28, 7, 331, 33, 34, 63 }. Which one of the following is the result after the 1st run of the Least Signification Digit (LSD) radix sort? (4分)
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: (6分)
For a binary search tree, in which order of traversal that we can obtain a non-decreasing sequence? (3分)
The function is to lower the value of the integer key at position P
by a positive amount D
in a min-heap H
.
void DecreaseKey( int P, int D, PriorityQueue H )
{
int i, key;
key = H->Elements[P] - D;
for ( i = (10分); H->Elements[i/2] > key; i/=2 )
;
H->Elements[i] = key;
}
分数组成 | 结果 | 得分 |
---|---|---|
1 | 答案正确 | 3 |
2 | 答案正确 | 3 |
You are supposed to output, in decreasing order, all the elements no less than X
in a binary search tree T
.
void Print_NLT( Tree T, int X );
where Tree
is defined as the following:
typedef struct TreeNode *Tree;
struct TreeNode {
int Element;
Tree Left;
Tree Right;
};
The function is supposed to use Output(X)
to print X
.
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode *Tree;
struct TreeNode {
int Element;
Tree Left;
Tree Right;
};
Tree BuildTree(); /* details omitted */
void Output( int X ); /* details omitted */
void Print_NLT( Tree T, int X );
int main()
{
Tree T;
int X;
T = BuildTree();
scanf("%d", &X);
Print_NLT( T, X );
printf("End\n");
return 0;
}
/* Your function will be put here */
92 91 90 85 81 80 End
End
void Print_NLT( Tree T, int X ) { if(T == NULL) return; Print_NLT(T->Right, X); if(T->Element >= X) printf("%d ", T->Element); Print_NLT(T->Left, X); }
测试点 | 结果 | 耗时 | 内存 |
---|---|---|---|
0 | 答案正确 | 2 ms | 360KB |
1 | 答案正确 | 2 ms | 256KB |
2 | 答案正确 | 3 ms | 264KB |
3 | 答案正确 | 3 ms | 384KB |
4 | 答案正确 | 3 ms | 384KB |