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

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

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

       

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

1-2

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-3

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

       

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

1-4

2N2^N and NNN^N have the same speed of growth. (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 分)

单选题得分:48总分:65
2-1

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

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

2-2

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

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

2-3

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

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

2-4

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

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

2-5

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-6

Which of the following statements is TRUE about topological sorting? (5分)

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

2-7

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

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

2-8

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

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

2-9

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

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

2-10

From the given graph shown by the figure, how many different topological orders can we obtain? (5分)

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

2-11

The recurrent equations for the time complexities of programs P1 and P2 are:

  • P1: T(1)=1T(1)=1, T(N)=T(N/2)+1T(N)=T(N/2)+1;
  • P2: T(1)=1T(1)=1, T(N)=2T(N/2)+1T(N)=2T(N/2)+1;

Then the correct conclusion about their time complexities is: (5分)

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

2-12

In-order traversal of a binary tree can be done iteratively. Given the stack operation sequence as the following:

push(1), push(2), push(3), pop(), push(4), pop(), pop(), push(5), pop(), pop(), push(6), pop()

Which one of the following statements is TRUE? (6分)

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

程序填空题得分:20总分:20
5-1

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

5-2

The function is to find the K-th largest element in a list A of N elements. The function BuildMinHeap(H, K) is to arrange elements H[1] ... H[K] into a min-heap. Please complete the following program.

ElementType FindKthLargest ( int A[], int N, int K )
{   /* it is assumed that K<=N */
    ElementType *H;
    int i, next, child;

    H = (ElementType *)malloc((K+1)*sizeof(ElementType));
    for ( i=1; i<=K; i++ ) H[i] = A[i-1];
    BuildMinHeap(H, K);

    for ( next=K; next<N; next++ ) {
        H[0] = A[next];
        if ( H[0] > H[1] ) {
            for ( i=1; i*2<=K; i=child ) {
                child = i*2;
                if ( child!=K && (5分) ) child++;
                if ( (5分) )
                    H[i] = H[child];
                else break;
            }
            H[i] = H[0];
        }
    }
    return H[1];
}

评测结果
答案正确(10 分)
测试点得分
序号结果得分
0答案正确5
1答案正确5