浙江大学2019-20秋冬《数据结构基础》期末模拟练习
开始时间2016/01/01 08:00:00
结束时间2038/01/18 08:00:00
答题时长120分钟
考生这个人由于考得太差不愿透露姓名
得分69
总分100

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

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分)
评测结果
答案错误(0 分)

1-2

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

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

1-3

In a binary tree, if node A is a descendant of node B, A may precede B in the inorder traversal sequence.

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

1-4

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

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

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

1-6

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分)
评测结果
答案正确(2 分)

1-7

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

The number of leaf nodes in a binary tree is only related to the number of 2-degree nodes , i.e it has nothing to do with the number of 1-degree nodes.

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

1-9

The best case time complexity of sorting algorithms based only on comparisons is at least O(NlogN)O(NlogN).

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

1-10

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(0.5logN)O(0.5logN).

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

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

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分)
评测结果
答案错误(0 分)

2-2

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

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

2-3

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

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

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

2-5

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

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

2-6

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

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

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

图1.jpg

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

2-9

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

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

2-10

The time complexity of recursively traversing a binary tree with NN nodes and height HH in preorder is __.

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

2-11

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

Suppose that the range of a hash table is [0, 16], and the hash function is H(Key)=Key%13. If linear probing is used to resolve collisions, then after inserting { 24, 12, 13, 49, 23 } one by one into the hash table, the index of 23 is:

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

2-13

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

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

Untitled.png

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

2-15

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

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

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

2-18

Given input { 321, 156, 57, 46, 28, 7, 331, 33, 34, 63 }. Which one of the following is the result after the 2nd run of the Least Signification Digit (LSD) radix sort?

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

2-19

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

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

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

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

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分);
      }
    }
  }
}
评测结果
答案正确(6 分)
测试点得分
序号结果得分
0答案正确3
1答案正确3

5-2

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;
    }
}
评测结果
部分正确(3 分)
测试点得分
序号结果得分
0答案正确3
1段错误0

函数题得分:8总分: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
代码
void Insert(int *ret, int num,int index){//数值插入函数但是由于题目数组为0-n-1的,所以要思考左右下标
    int left = (index+1)*2-1,right = (index+1)*2;
    if(!ret[index])ret[index] = num;
    else {
        if(num>ret[index]) Insert(ret,num,left);
        else Insert(ret,num,right);
    }
    return;
}
int cnt=0;
void PostOrder(int *ret, int *a, int index){//后序遍历途中按顺序赋值题目要求的输出的A[],这个写过,但是要注意的是cnt是全局变量,这点我搞了半天。
    if(ret[index]){
        a[cnt++] = ret[index];
        PostOrder(ret,a,(index+1)*2-1);
        PostOrder(ret,a,(index+1)*2);
        
    }
}
int IsCBST( int A[], int N ){
    int ret[111]={0};
    int index=0;
    for(int i=0; i<N; i++) Insert(ret,A[i],0);
//    for(int i=0; i<N; i++) printf("%d\n",ret[i]);
    PostOrder(ret,A,0);
    int flag =1;
    for(int i =0; i<N; i++)if(!ret[i])flag = 0;//如果是完全二叉树,则所有的点都在要求的N中,而不是则不然:在ret[x](x>N)的条件下会有节点存在
    return flag;
}
评测结果
答案正确(8 分)
编译器输出
a.c: In function ‘IsCBST’:
a.c:41:9: warning: unused variable ‘index’ [-Wunused-variable]
     int index=0;
         ^~~~~
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答案正确19.00 ms192 KB
1答案正确118.00 ms300 KB
2答案正确16.00 ms184 KB
3答案正确114.00 ms192 KB
4答案正确16.00 ms188 KB
5答案正确115.00 ms312 KB
6答案正确120.00 ms188 KB
7答案正确17.00 ms188 KB