16-17年期中考试试卷

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

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

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

答题时长45分钟

考生

得分17

总分100

---

判断题得分：12总分：15

R1-1

In a binary search tree, the keys on the same level from left to right must be in sorted (non-decreasing) order.

(3分)

T

F

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

R1-2

For a sequentially stored linear list of length $N$, the time complexities for query and insertion are $O(1)$ and $O(N)$, respectively.

(3分)

T

F

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

R1-3

$2^N$ and $N^N$ have the same speed of growth.

(3分)

T

F

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

R1-4

In a directed graph, the sum of the in-degrees must be equal to the sum of the out-degrees of all the vertices.

(3分)

T

F

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

R1-5

If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}.

(3分)

T

F

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

单选题得分：0总分：65

R2-1

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:

(5分)

A.

front+size-1

B.

front+size

C.

(front+size-1)%m

D.

(front+size)%m

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

R2-2

The result of performing three DeleteMin operations in the min-heap {1,3,2,6,7,5,4,15,14,12,9,10,11,13,8} is:

(5分)

A.

4,5,6,12,7,10,8,15,14,13,9,11

B.

4,5,6,7,8,9,10,11,12,13,14,15

C.

4,6,5,13,7,10,8,15,14,12,9,11

D.

4,6,5,12,7,10,8,15,14,9,13,11

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

R2-3

In a complete binary tree with 1102 nodes, there must be __ leaf nodes.

(6分)

A.

1063

B.

551

C.

79

D.

cannot be determined

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

R2-4

Use Dijkstra algorithm to find the shortest paths from 1 to every other vertices. In which order that the destinations must be obtained?

(5分)

A.

5, 2, 3, 4, 6

B.

5, 2, 3, 6, 4

C.

5, 2, 6, 3, 4

D.

5, 2, 4, 3, 6

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

R2-5

Given a directed graph G=(V, E) where V = {v1, v2, v3, v4, v5, v6} and E = {<v1,v2>, <v1,v4>, <v2,v6>, <v3,v1>, <v3,v4>, <v4,v5>, <v5,v2>, <v5,v6>}. Then the topological order of G is:

(5分)

A.

v3, v4, v1, v5, v2, v6

B.

v3, v1, v4, v5, v2, v6

C.

v1, v3, v4, v5, v2, v6

D.

v1, v4, v3, v5, v2, v6

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

R2-6

In a weighted graph, if the length of the shortest path from b to a is 10, and there exists an edge of weight 3 between c and b, then how many of the following statements is/are TRUE?

1. The length of the shortest path from c to a must be 13.
2. The length of the shortest path from c to a must be 7.
3. The length of the shortest path from c to a must be no greater than 13.
4. The length of the shortest path from c to a must be no less than 7.

(6分)

A.

4

B.

3

C.

2

D.

1

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

R2-7

The array representation of a disjoint set is given by { 4, 6, 5, 2, -3, -4, 3 }. If the elements are numbered from 1 to 7, the resulting array after invoking Union(Find(7),Find(1)) with union-by-size and path-compression is:

(5分)

A.

{ 4, 6, 5, 2, 6, -7, 3 }

B.

{ 6, 6, 5, 6, 6, -7, 5 }

C.

{ 4, 6, 5, 2, -7, 5, 3 }

D.

{ 6, 6, 5, 6, -7, 5, 5 }

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

R2-8

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 __.

(5分)

A.

21

B.

10

C.

12

D.

20

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

R2-9

What is a critical path in an AOE network?

(5分)

A.

the shortest path from the first to the last event

B.

the longest path from the first to the last event

C.

the shortest circuit

D.

the longest circuit

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

R2-10

Insert { 6, 9, 12, 3, 4, 8 } one by one into an initially empty binary search tree. The post-order traversal sequence of the resulting tree is:

(6分)

A.

3, 4, 6, 8, 12, 9

B.

4, 3, 6, 8, 12, 9

C.

4, 3, 8, 12, 9, 6

D.

3, 4, 9, 8, 12, 6

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

R2-11

To insert s after p in a doubly linked circular list, we must do:

(6分)

A.

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

B.

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

C.

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

D.

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

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

R2-12

If an undirected graph G = (V, E) contains 7 vertices. Then to guarantee that G is connected in any cases, there has to be at least ____ edges.

(6分)

A.

6

B.

16

C.

21

D.

15

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

程序填空题得分：5总分：20

R5-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 = (5分); H->Elements[i/2] > key; i/=2 )
      (5分);
   H->Elements[i] = key;
}

评测结果未作答(0 分)

R5-2

Please fill in the blanks in the program which performs Find as a Union/Find operation with path compression.

SetType Find ( ElementType X, DisjSet S )
{   
   ElementType root, trail, lead;

   for ( root = X; S[root] > 0; (5分) ) ;  
   for ( trail = X; trail != root; trail = lead ) {
      lead = S[trail] ;   
      (5分);   
   } 
   return root;
}

序号	结果	测试点得分
0	答案正确	5
1	未作答	0

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