17-18年期中考试试卷

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

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

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

答题时长45分钟

考生

得分27

总分100

---

判断题得分：9总分：15

R1-1

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

R1-2

For a sequentially stored linear list of length $N$, the time complexities for deleting the first element and inserting the last element are $O(1)$ and $O(N)$, respectively.

(3分)

T

F

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

R1-3

The sum of the degrees of all the vertices in a connected graph must be an even number.

(3分)

T

F

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

R1-4

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

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

(3分)

T

F

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

单选题得分：18总分：65

R2-1

How many leaf node does a complete binary tree with 2435 nodes have?

(6分)

A.

1218

B.

1217

C.

cannot be determined

D.

812

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

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

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, -7, 5, 3 }

B.

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

C.

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

D.

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

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

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

A.

3, 4, 6, 8, 12, 9

B.

3, 4, 9, 8, 12, 6

C.

4, 3, 8, 12, 9, 6

D.

4, 3, 6, 8, 12, 9

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

R2-5

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

A.

2 and 6 are siblings

B.

6 is the root

C.

2 is the parent of 4

D.

None of the above

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

R2-6

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

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

Then the best conclusion about their time complexities is:

(5分)

A.

they are both $O(logN)$

B.

$O(logN)$ for P1, and $O(N)$ for P2

C.

$O(logN)$ for P1, and $O(NlogN)$ for P2

D.

they are both $O(N)$

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

R2-7

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

(5分)

A.

4

B.

3

C.

1

D.

2

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

R2-8

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.

15

C.

16

D.

21

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

R2-9

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

(6分)

A.

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

B.

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

C.

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

D.

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

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

R2-10

Which of the following statements is TRUE about topological sorting?

(5分)

A.

In a DAG, if for any pair of distinct vertices $V_i$ and $V_j$, there is a path either from $V_i$ to $V_j$ or from $V_j$ to $V_i$, then the DAG must have a unique topological sequence.

B.

If the adjacency matrix is triangular, then the corresponding directed graph must have a unique topological sequence.

C.

If $V_i$ precedes $V_j$ in a topological sequence, then there must be a path from $V_i$ to $V_j$.

D.

If a graph has a topological sequence, then its adjacency matrix must be triangular.

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

R2-11

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

A.

21

B.

20

C.

12

D.

22

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

R2-12

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

B.

(front+size)%m

C.

front+size-1

D.

(front+size-1)%m

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

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

R5-1

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];
}

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

评测结果多种错误(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	编译错误	0
1	未作答	0

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