浙江大学2015-16秋冬《数据结构基础》期中模拟练习
开始时间1/1/2016, 12:00:00 AM
结束时间1/18/2038, 12:00:00 AM
答题时长90分钟
考生-
得分95
总分100

判断题总分:10得分:8
1-1

If the postorder and inorder traversal sequences of a binary tree are the same, then none of the nodes in the tree has a right child. (2分)

       

评测结果:答案正确(2 分)
1-2

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

       

评测结果:答案错误(0 分)
1-3

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

       

评测结果:答案正确(2 分)
1-4

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

       

评测结果:答案正确(2 分)
1-5

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

       

评测结果:答案正确(2 分)
单选题总分:64得分:61
2-1

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

评测结果:答案正确(3 分)
2-2

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

评测结果:答案正确(3 分)
2-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分)

评测结果:答案正确(3 分)
2-4

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

评测结果:答案正确(6 分)
2-5

Given a tree of degree 4. Suppose that the numbers of nodes of degrees 2, 3 and 4 are 4, 2 and 1, respectively. Then the number of leaf nodes must be: (6分)

评测结果:答案正确(6 分)
2-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分)

评测结果:答案正确(6 分)
2-7

Suppose that an array of size m is used to store a circular queue. If the front position is front and the current size is size, then the rear element must be at: (6分)

评测结果:答案正确(6 分)
2-8

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

评测结果:答案正确(6 分)
2-9

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

评测结果:答案错误(0 分)
2-10

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

评测结果:答案正确(6 分)
2-11

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

评测结果:答案正确(4 分)
2-12

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

评测结果:答案正确(6 分)
2-13

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

评测结果:答案正确(6 分)
程序填空题总分:6得分:6
5-1

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 = (3分); H->Elements[i/2] > key; i/=2 )
      (3分);
   H->Elements[i] = key;
}
评测结果:答案正确(6 分)
序号结果得分
0答案正确3
1答案正确3
函数题总分:20得分:20
6-1
No Less Than X in BST

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
代码
int a[1000] = {0}, st = -1;

int cmp(const void *l, const void *r) {
    return *(int*)r-*(int*)l;
}

void Tr(Tree T, int X) {
    if (T) {
        if (T->Element >= X) {
            a[++st] = T->Element;
        }
        Tr(T->Left, X);
        Tr(T->Right, X);
    }
}

void Print_NLT( Tree T,  int X ) {
    Tr(T, X);

    qsort(a, st+1, sizeof(int), cmp);
    for (int i = 0; i<=st; i++) {
        Output(a[i]);
    }
}
评测结果:答案正确(20 分)
测试点结果得分耗时内存
0答案正确72 ms256 KB
1答案正确32 ms256 KB
2答案正确62 ms296 KB
3答案正确22 ms256 KB
4答案正确23 ms256 KB
a.c: In function ‘BuildTree’:
a.c:33:6: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &n);
      ^~~~~~~~~~~~~~~
a.c:35: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:52:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &X);
     ^~~~~~~~~~~~~~~