15-16年期中考试试卷

浙江大学2015-16秋冬《数据结构基础》期中模拟练习

开始时间01/01/2016 8:00:00 AM

结束时间01/18/2038 8:00:00 AM

答题时长90分钟

考生

得分43

总分104

---

判断题得分：8总分：10

R1-1

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

(2分)

T

F

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

R1-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 right child.

(2分)

T

F

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

R1-3

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

(2分)

T

F

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

R1-4

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

T

F

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

R1-5

Given the input sequence onto a stack as {1, 2, 3, ..., $N$}. If the first output is $i$, then the $j$-th output must be $j-i-1$.

(2分)

T

F

评测结果答案错误(0 分)

单选题得分：30总分：64

R2-1

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

A.

8

B.

12

C.

18

D.

20

评测结果答案错误(0 分)

R2-2

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

A.

front+size

B.

(front+size)%m

C.

(front+size-1)%m

D.

front+size-1

评测结果答案错误(0 分)

R2-3

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

A.

1, 3, 2, 5, 4, 7, 6

B.

1, 3, 5, 4, 2, 7, 6

C.

1, 2, 5, 3, 4, 7, 6

D.

1, 2, 3, 4, 5, 7, 6

评测结果答案正确(6 分)

R2-4

Among the following methods, which one's time complexity is always $O(NlogN)$, no matter what the initial condition is?

(3分)

A.

bubble sort

B.

heap sort

C.

quick sort

D.

simple selection sort

评测结果答案错误(0 分)

R2-5

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

A.

$2^{h-1}+1$, $2^h-1$

B.

$2h-1$, $2^h-1$

C.

$2h$, $2^h-1$

D.

$2h-1$, $2^{h-1}-1$

评测结果答案错误(0 分)

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

A.

4, 1, 3, 7, 6, 2, 5

B.

3, 5, 4, 2, 6, 1, 7

C.

3, 5, 4, 7, 2, 6, 1

D.

1, 4, 3, 7, 2, 6, 5

评测结果答案正确(6 分)

R2-7

To delete p from a doubly linked list, we must do:

(6分)

A.

p->prior->next=p->next; p->next->prior=p->prior;

B.

p->next=p->prior->prior; p->prior=p->next->next;

C.

p->next->prior=p; p->next=p->next->next;

D.

p->prior=p->prior->prior; p->prior->next=p;

评测结果答案正确(6 分)

R2-8

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

A.

1847

B.

823

C.

cannot be determined

D.

311

评测结果答案正确(6 分)

R2-9

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

A.

4 and -5

B.

8 and -6

C.

1 and -6

D.

8 and -5

评测结果答案错误(0 分)

R2-10

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

(3分)

A.

level-order traversal

B.

preorder traversal

C.

postorder traversal

D.

inorder traversal

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

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

A.

→321→331→33→63→34→156→46→57→7→28

B.

→331→321→33→63→34→156→46→57→7→28

C.

→156→28→321→331→33→34→46→57→63→7

D.

→57→46→28→7→33→34→63→156→321→331

评测结果答案错误(0 分)

R2-12

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

(3分)

A.

heap sort $>$ quick sort $>$ merge sort

B.

heap sort $<$ quick sort $<$ merge sort

C.

heap sort $>$ merge sort $>$ quick sort

D.

heap sort $<$ merge sort $<$ quick sort

评测结果答案错误(0 分)

R2-13

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

A.

1

B.

3

C.

5

D.

1 or 5

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

程序填空题得分：0总分：10

R5-1

The function is to increase the value of the integer key at position P by a positive amount D in a max-heap H.

void IncreaseKey( 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;
}

序号	结果	测试点得分
0	编译错误	0
1	未作答	0

评测结果多种错误(0 分)

函数题得分：5总分：20

R6-1

No Greater Than X in BST

(20分)

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

Format of function:

void Print_NGT( 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_NGT( Tree T,  int X );

int main()
{
    Tree T;
    int X;

    T = BuildTree();
    scanf("%d", &X);
    Print_NGT( T, X );
    printf("End\n");

    return 0;
}

/* Your function will be put here */

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

91 90 85 81 80 55 End

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

End

编译器

GCC

代码

void Print_NGT( Tree T,  int X ) {
    return;
}

编译器输出

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);
     ^~~~~~~~~~~~~~~

测试点	结果	测试点得分	耗时	内存
0	答案错误	0	4.00 ms	312 KB
1	答案正确	3	4.00 ms	432 KB
2	答案错误	0	4.00 ms	336 KB
3	答案正确	2	4.00 ms	352 KB
4	答案错误	0	4.00 ms	384 KB

评测结果部分正确(5 分)