浙江大学2019-20秋冬《数据结构基础》期末模拟练习
开始时间2016/01/01 08:00:00
结束时间2038/01/18 08:00:00
答题时长120分钟
考生Reticence
得分70
总分100

判断题得分:14总分:20
1-1

It is always possible to represent a tree by a one-dimensional integer array.

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

1-2

During the sorting, processing every element which is not yet at its final position is called a "run". To sort a list of integers using quick sort, it may reduce the total number of recursions by processing the small partion first in each run.

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

1-3

There must be a collision if we insert a new element into a hash table with the loading density being 1.

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

1-4

In a binary tree, if node A is an ancestor of node B, then A must precede B in the inorder traversal sequence.

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

1-5

For binary heaps with NN elements, the BuildHeap function (which adjust an array of elements into a heap in linear time) does at most Nlog(N+1)N-log(N+1) comparisons between elements.

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

1-6

Let P be the shortest path from S to T. If the weight of every edge in the graph is multiplied by 2, P will still be the shortest path from S to T.

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

1-7

To judge an odd integer N(>10)N(>10) is prime or not, we need to check if it is divisible by any odd number from 3 to N\sqrt N . The time complexity of this algorithm is O(N)O(\sqrt N).

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

1-8

Given that the pushing sequence of a stack is { 1, 2, \cdots, nn } and popping sequence is { x1,x2,,xnx_1, x_2, \cdots, x_n }. If x2=nx_2 = n, we can obtain 2 different possible popping sequences.

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

1-9

During finding all articulation points in a connected graph, if v1 is the parent of v2 in the depth-first tree, Num(v1) must be less than Num(v2).

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

1-10

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

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

单选题得分:51总分:60
2-1

Given the AOE network of a project with 8 activities shown below, the earliest/latest completion time for node 4 is __.

Untitled.png

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

2-2

The array representation of the disjoint sets is given by { 3, 1, -5, 2, 1, -3, -1, 6, 6 }. Keep in mind that the elements are numbered from 1 to 9. After invoking Union(Find(4), Find(8)) with union-by-size, which elements will be changed in the resulting array?

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

2-3

Suppose that the level-order traversal sequence of a max-heap is {64, 53, 45, 36, 48, 27}. Use the linear algorithm to adjust this max-heap into a min-heap, and then insert 32. The postorder traversal sequence of the resulting tree is:

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

2-4

Given an integer sequence 25、84、21、47、15、27、68、35、20, after the first run of the shell sorting by an increment 3, the integer sequence is __.

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

2-5

For a complete binary tree with even number of nodes, among the following statements, how many statement(s) is/are true?

a) the height of the left subtree must be greater than that of the right subtree

b) the number of nodes in the left subtree must be greater than that in the right subtree

c) the number of leaf-nodes in the left subtree must be twice over that in the right subtree

d) the number of leaf-nodes and that of non-leaf-nodes are exactly the same

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

2-6

When solving the maximum flow problem for graph GG, if partial states of the GfG_f ( will be the maximum flow when the algorithm terminates) and GrG_r (residual graph) are shown as the following, what must be the capacity of (v1, v2) or of (v2,v1) in the original graph GG?

图2.jpg

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

2-7

The space complexity of iteratively traversing a binary tree with NN nodes and height HH in inorder (with the help of an auxiliary stack) is __.

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

2-8

Graph G is an undirected completed graph of 20 nodes. Is there an Euler circuit in G? If not, in order to have an Euler circuit, what is the minimum number of edges which should be removed from G?

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

2-9

For an in-order threaded binary tree, if the post-order and in-order traversal sequences are CBFGEDA and BCADFEG respectively, the number of left threaded links and that of right threaded links are _.

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

2-10

A graph with 90 vertices and 20 edges must have at least __ connected component(s).

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

2-11

To find the minimum spanning tree with Prim's algorithm from v1 for the following graph. Which edge will be added in the final step?

图1.jpg

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

2-12

If keys are pushed onto a stack in the order { 1, 2, 3, 4, 5} , then in the following sequence, the legal output sequence of the stack is ()

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

2-13

Given a tree of degree 5. Suppose that the numbers of nodes of degrees 1, 2, 3, 4, 5 are 3, 1, 2, 4, 3, respectively. Then the number of leaf nodes must be _.

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

2-14

Suppose that the range of a hash table is [0, 18], and the hash function is H(Key)=Key%17. If linear probing is used to resolve collisions, then after inserting { 16, 32, 14, 34, 48 } one by one into the hash table, the index of 48 is:

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

2-15

Given a binary search tree with its preorder traversal sequence { 10, 8, 21, 12, 15, 32 }. If 10 is deleted from the tree, which one of the following statements is FALSE?

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

2-16

To list the directory in a hierarchical file system with the format of files that are of depth di will have their names indented by di tabs, which of the following traversals is the most suitable one.

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

2-17

Insert {20, 25, 13, 22, 4, 9, 29, 35, 14, 17} one by one into an initially empty hash table of size 13 with the hash function H(Key)=Key%13, and quadratic probing is used to resolve collisions. How many numbers can be inserted without collisions?

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

2-18

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

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

Then the correct conclusion about their time complexities is:

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

2-19

Given input { 110, 119, 7, 911, 114, 120, 122 }. Which one of the following is the result after the 2nd run of the Least Signification Digit (LSD) radix sort?

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

2-20

The time complexity of traversing a binary tree with NN nodes and height HH in levelorder (with the help of with an auxiliary queue) is __.

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

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

None-recursive Quick Selection algorithm

The function is to find the K-th smallest element in a list A of N elements. The initial function call is QSelect(A, N, K). Please complete the following program.

ElementType QSelect( ElementType A[], int N, int K )
{
    ElementType Pivot;
    int L, R, Left, Right, K1;
    Left = 0; Right = N-1; K1 = K;
    for(;;) {
        L = Left, R = Right+1;
        Pivot = A[Left];
        while (1) {
            while ( A[++L] < Pivot ) ;
            (3分);
            if ( L < R ) Swap( &A[L], &A[R] );
            else break;
        }
        Swap( &A[Left], &A[R] );
        if ( K1 < (L-Left) )
            Right = R-1;
        else if ( K1 > (L-Left) ){
            (3分); 
             Left = L;
        }else
            return Pivot;
    }
}
评测结果
答案错误(0 分)
测试点得分
序号结果得分
0运行超时0
1段错误0

5-2

The function Unweighted is to find the unweighted shortest path from Vertex S to every other vertices in a given Graph. The distances are stored in dist[], and path[] records the paths. The Graph is defined as the following:

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;          /* Number of vertices */
    int Ne;          /* Number of edges    */
    AdjList List;    /* adjacency matrix */
};
typedef PtrToGNode Graph;
void Unweighted( Graph G, Queue Q, int dist[], int path[], Vertex S )
{
  Vertex V, U;
  NodePtr ptr;

  dist[S] = 0;
  Enqueue(S, Q);
  while ( !IsEmpty(Q) ) {
    V = Dequeue( Q );
    for ( ptr=G->List[V].FirstEdge; ptr; ptr=ptr->Next) {
      U = ptr->AdjV;
      if ( dist[U] == INFINITY ) {
         (3分);
         path[U] = V;
         (3分);
      }
    }
  }
}
评测结果
部分正确(3 分)
测试点得分
序号结果得分
0答案正确3
1编译错误0

函数题得分:2总分:8
6-1
IsCBST
(8分)

Insert a sequence of integer keys into an initially empty binary search tree with larger keys in its left subtree and smaller keys in its right subtree, you are supposed to tell if the resulting tree is a complete binary search tree (CBST), and then return its preorder traversal sequence.

Format of function:

int IsCBST( int A[], int N );

where the sequence of N insertions is stored in A[].

The function IsCBST is supposed to return 1 if the resulting tree is a CBST, or 0 if not. At the mean time, A[] must store the preorder traversal sequence of the resulting tree.

Sample program of judge:

#include <stdio.h>

#define MAXN 10

int IsCBST( int A[], int N );

int main()
{
    int A[MAXN], N, i;

    scanf("%d", &N);
    for (i=0; i<N; i++) scanf("%d", &A[i]);
    if ( IsCBST(A, N) ) printf("Yes\n");
    else printf("No\n");
    for (i=0; i<N; i++) printf("%d ", A[i]);

    return 0;
}

/* Your function will be put here */

Sample Input 1:

9
38 45 42 24 58 30 67 12 51

Sample Output 1:

Yes
38 45 58 67 51 42 24 30 12 

Sample Input 2:

8
38 24 12 45 58 67 42 51

Sample Output 2:

No
38 45 58 67 51 42 24 12 
编译器
GCC
代码
int IsCBST( int A[], int N )
{
    int i,j,k,T[N];
    for (i=0;i<N;i++)
        T[i]=0;
    for (i=0;;)
    {
        if (T[i]==0) {
            T[i]=A[i];
            break;
        }
        else if (T[i]>A[i]) i=2*i+1;
        else i=2*i+2;
    }
    for (i=0;i<N;i++)
        if (T[i]) A[i]=T[i];
        else return 0;
    return 1;
}
评测结果
部分正确(2 分)
编译器输出
a.c: In function ‘IsCBST’:
a.c:23:13: warning: unused variable ‘k’ [-Wunused-variable]
     int i,j,k,T[N];
             ^
a.c:23:11: warning: unused variable ‘j’ [-Wunused-variable]
     int i,j,k,T[N];
           ^
a.c: In function ‘main’:
a.c:11:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ^~~~~~~~~~~~~~~
a.c:12:25: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     for (i=0; i<N; i++) scanf("%d", &A[i]);
                         ^~~~~~~~~~~~~~~~~~
测试点得分
测试点结果得分耗时内存
0答案错误04.00 ms328 KB
1答案错误04.00 ms328 KB
2答案错误04.00 ms324 KB
3答案错误04.00 ms324 KB
4答案错误05.00 ms192 KB
5答案错误07.00 ms312 KB
6答案正确14.00 ms196 KB
7答案正确14.00 ms320 KB