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

判断题总分:15得分:15
1-1

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

       

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

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

       

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

N2logNN^2 logN and NlogN2N logN^2 have the same speed of growth. (3分)

       

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

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

       

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

In a directed graph, the sum of the in-degrees and out-degrees of all the vertices is twice the total number of edges. (3分)

       

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

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

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

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

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

What is a critical path in an AOE network? (5分)

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

Given a quadtree(四叉树) with 4 nodes of degree 2, 4 nodes of degree 3, 3 nodes of degree 4. The number of leaf nodes in this tree is __. (5分)

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

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

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

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

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

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? (6分)

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

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: (5分)

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

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

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

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

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

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

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

In a complete binary tree with 1102 nodes, there must be __ leaf nodes. (6分)

评测结果:答案正确(6 分)
程序填空题总分:20得分:20
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 = (5分); H->Elements[i/2] > key; i/=2 )
      (5分);
   H->Elements[i] = key;
}
评测结果:答案正确(10 分)
序号结果得分
0答案正确5
1答案正确5
5-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;
}
评测结果:答案正确(10 分)
序号结果得分
0答案正确5
1答案正确5