3180103845@zju.edu.cn NQ-0002

总分: 90 / 104

判断题 总分: 10 / 10


1-1 答案正确 得分: 2 / 2

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分)

       


1-2 答案正确 得分: 2 / 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分)

       


1-3 答案正确 得分: 2 / 2

Given the input sequence onto a stack as {1, 2, 3, ..., NN}. If the first output is ii, then the jj-th output must be ji1j-i-1. (2分)

       


1-4 答案正确 得分: 2 / 2

(logN)2(logN)^2 is O(N)O(N). (2分)

       


1-5 答案正确 得分: 2 / 2

The best "worst-case time complexity" for any algorithm that sorts by comparisons only must be O(NlogN)O(NlogN). (2分)

       


选择题 总分: 54 / 64


2-1 答案正确 得分: 6 / 6

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分)


2-2 答案错误 得分: 0 / 3

Which one of the following relations is correct about the extra space taken by heap sort, quick sort and merge sort? (3分)


2-3 答案正确 得分: 3 / 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分)


2-4 答案正确 得分: 6 / 6

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分)


2-5 答案正确 得分: 6 / 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分)


2-6 答案正确 得分: 6 / 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分)


2-7 答案错误 得分: 0 / 3

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分)


2-8 答案正确 得分: 6 / 6

Suppose that the height of a binary tree is hh (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分)


2-9 答案正确 得分: 6 / 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分)


2-10 答案正确 得分: 6 / 6

To delete p from a doubly linked list, we must do: (6分)


2-11 答案错误 得分: 0 / 4

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分)


2-12 答案正确 得分: 6 / 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: (6分)


2-13 答案正确 得分: 3 / 3

For a binary search tree, in which order of traversal that we can obtain a non-decreasing sequence? (3分)


程序填空题 总分: 6 / 10


5-1 DecreaseKey 答案正确 得分: 6 / 10

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

函数题 总分: 20 / 20


6-1 No Less Than X in BST 答案正确 得分: 20 / 20

You are supposed to output, in decreasing order, all the elements no less than X in a binary search tree T.

Format of function:

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.

Sample program of judge:

#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 */

Sample Output 1 (for the tree shown in Figure 1):

92 91 90 85 81 80 End

Figure 1

Sample Output 2 (for the tree shown in Figure 2):

End

Figure 2
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