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

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

If a graph is represented by adjacency lists, then the space taken depends only on the number of vertices, not the number of edges. (1分)

       

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

Store a complete binary tree in an array (root at position 1). Then the nodes at positions 23 and 24 are siblings. (1分)

       

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

In a directed graph, the sum of the in-degrees must be equal to the sum of the out-degrees of all the vertices. (1分)

       

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

The Fibonacci number sequence {FNF_N} is defined as: F0=0F_0=0, F1=1F_1=1, FN=FN1+FN2F_N=F_{N-1}+F_{N-2}, NN=2, 3, .... The time complexity of the function which calculates FNF_N iteratively is Θ(FN)\Theta (F_N). (1分)

       

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

To sort NN records by merge sort, the number of merge runs is O(NlogN)O(NlogN). (1分)

       

评测结果:答案错误(0 分)
1-6

In hashing, functions "insert" and "find" have the same time complexity. (1分)

       

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

In a graph G, if we have to do BFS twice to visit every one of its vertices, then there must be a cycle in G. (1分)

       

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

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

       

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

There exists a binary tree with 2016 nodes in total, and with 16 nodes having only one child. (1分)

       

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

Shell sort is stable. (1分)

       

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

If the input is a set of 10410^4 1-digit numbers, which one of the following methods can sort them in O(N)O(N) time? (2分)

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

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

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

Use the linear algorithm to adjust the given sequence of numbers { 28, 12, 5, 8, 19, 20, 15, 22 } into a max-heap, and then insert 30. The resulting sequence is __. (2分)

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

Given a hash table of size 17 with the hash function H(Key)=Key%17H(Key) = Key\%17. Quadratic probing (hi(k)=(H(k)±i2)%17h_i(k) = (H(k) \pm i^2)\%17) is used to resolve collisions. Then after inserting { 23, 22, 7, 26, 9, 6 } one by one into the hash table, the address of 6 is__. (2分)

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

If besides finding the shortest path from S to every other vertices, we also need to count the number of different shortest paths, we can modify the Dijkstra algorithm in the following way: add an array count[] so that count[V] records the number of different shortest paths from S to V. Then count[V] shall be initialized as: (3分)

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

In a max-heap with nn (>1>1) elements, the array index of the minimum key may be __. (2分)

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

Given the adjacency lists of a directed graph as shown by the figure. Then starting from V1, a possible DFS sequence is: (2分)

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

Given input { 431, 56, 57, 46, 28, 7, 331, 33, 24, 63 }. Which one of the following is the result after the 1st run of the Least Signification Digit (LSD) radix sort? (2分)

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

The maximum flow in the network of the given Figure is: (3分)

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

The articulation points of the given graph are: (2分)

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

For a binary tree, if its pre-order travel sequence is { 4, 2, 1, 3, 6, 5, 7 }, and its in-order travel sequence is { 1, 2, 3, 4, 5, 6, 7 }, then which of the following statement is FALSE? (3分)

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

To sort the sequence { 2, 12, 16, 88, 5, 10, 34 }, if the results of the first 2 runs are given as the following:

  • after the 1st run: 2, 12, 16, 10, 5, 34, 88
  • after the 2nd run: 2, 5, 10, 12, 16, 34, 88

Then the possible sorting method is: (2分)

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

If the pushing sequence of a stack is {1, 2, 3, ..., NN} and the first number being popped out is ii, then the jj-th number being popped must be: (2分)

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

To judge an integer NN (>10>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 __. (2分)

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

Given the result of the 1st run of a sorting method as { 19, 21, 7, 14, 5, 27, 1, 10 }. Then among the following, this method has to be: (2分)

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

If graph G is NOT connected and has 15 edges, then it must have at least _ vertices. (3分)

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

Suppose that a polynomial is represented by a linked list storing its non-zero terms. Given two polynimials with N1N_1 and N2N_2 non-zero terms, and the highest exponents being M1M_1 and M2M_2, respectively. Then the time complexity for multiplying them is: (2分)

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

Given the adjacency matrix of a weighted graph as shown by the figure. The total weight of its minimum spanning tree is: (2分)

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

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

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

To check if there is a cycle in a directed graph, which one of the following algorithms can be used, besides the topological sort? (2分)

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

How many of the following statements is/are TRUE? (3分)

  1. If e is the only shortest edge in the weighted graph G, then e must be in the minimum spanning tree of G.
  2. If the BFS sequence of a graph is 1 2 3 4 ..., and if there is an edge between vertices 1 and 4, then there must be an edge between the vertices 1 and 3.
  3. In a directed graph G with at least two vertices, if DFS from any vertex can visit every other vertices, then the topological order must NOT exist.
  4. Suppose that a graph is represented by an adjacency matrix. If there exist non-zero entries in the matrix, yet all the entries below the diagonal are zeros, then this graph must be a directed graph.
评测结果:答案错误(0 分)
2-22

If quadratic probing is used to resolve collisions, then which one of the following statements is TRUE about inserting a new element? (2分)

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

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 __. (2分)

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

BFS is similar to the __ traversal of a binary tree. (2分)

评测结果:答案正确(2 分)
程序填空题总分:25得分:25
5-1

Please fill the array with the results after the following union/find operations.

union( find(1), find(5) )
union( find(3), find(6) )
union( find(0), find(1) )
union( find(6), find(5) )
union( find(6), find(4) )

Note: Assume union-by-size (if two sets are equal-sized, the first root will be the root of the result) and find-with-path-compression. S[i] is initialized to be 1-1 for all 0i70\le i\le 7.

i 0 1 2 3 4 5 6 7
S[i] 11 (1分) 1-1 (1分) (1分) 11 (1分) 1-1
评测结果:答案正确(4 分)
序号结果得分
0答案正确1
1答案正确1
2答案正确1
3答案正确1
5-2

The function is to sort the list { r[1] … r[n] } in non-increasing order. Unlike selection sort which places only the maximum unsorted element in its correct position, this algorithm finds both the minimum and the maximum unsorted elements and places them into their final positions.

void  sort( list r[], int n )  
{
   int i, j, mini, maxi;

   for (i=1; i<n-i+1; i++) {
      mini = maxi = i;
      for( j=i+1; (3分); ++j ){
         if( (3分) ) mini = j; 
         else if(r[j]->key > r[maxi]->key) maxi = j;
      }
      if( maxi != i ) swap(&r[maxi], &r[i]);
      if( mini != n-i+1 ){
         if( (3分) ) swap(&r[maxi], &r[n-i+1]);
         else swap(&r[mini], &r[n-i+1]);
      }
   }
} 
评测结果:答案正确(9 分)
序号结果得分
0答案正确3
1答案正确3
2答案正确3
5-3

A binary tree is said to be "height balanced" if both its left and right subtrees are height balanced, and the heights of its left and right subtrees can differ by at most 1. That is, HLHR1|H_L - H_R |\le 1 where HLH_L and HRH_R are the heights of the left and right subtrees, respectively. An empty binary tree is defined to be height balanced.

The function IsBalanced is to judge if a given binary tree T is height balanced. If the answer is yes then return true and store the tree height in the parameter pHeight, else simply return false. The height of an empty tree is defined to be 0.

typedef struct TNode *BinTree;
struct TNode{
    int Key;
    BinTree Left;
    BinTree Right;
};

bool IsBalanced ( BinTree T, int *pHeight )  
{
    int  LHeight, RHeight, diff;

    if( T == NULL) {                     
        *pHeight = 0;  
        return true;  
    }    
    else if ( IsBalanced(T->Left, &LHeight) && IsBalanced(T->Right, &RHeight) ) {    
        diff = LHeight - RHeight + 1;              
        if ( (6分) )  {  
            *pHeight = 1 + ( diff<1 ? (6分) );  
            return true;  
        }  
        else return false;           
    }        
    return false; 
}  
评测结果:答案正确(12 分)
序号结果得分
0答案正确6
1答案正确6
函数题总分:10得分:10
6-1
CheckBST[2]

Given a binary tree, you are supposed to tell if it is a binary search tree. If the answer is yes, try to find the KK-th smallest key, else try to find the height of the tree.

Format of function:

int CheckBST ( BinTree T, int K );

where BinTree is defined as the following:

typedef struct TNode *BinTree;
struct TNode{
    int Key;
    BinTree Left;
    BinTree Right;
};

The function CheckBST is supposed to return the K-th smallest key if T is a binary search tree; or if not, return the negative height of T (for example, if the height is 55, you must return 5-5).

Here the height of a leaf node is defined to be 1. T is not empty and all its keys are positive integers. K is positive and is never more than the total number of nodes in the tree.

Sample program of judge:

#include <stdio.h>
#include <stdlib.h>

typedef struct TNode *BinTree;
struct TNode{
    int Key;
    BinTree Left;
    BinTree Right;
};

BinTree BuildTree(); /* details omitted */
int CheckBST ( BinTree T, int K );

int main()
{
    BinTree T;
    int K, out;

    T = BuildTree();
    scanf("%d", &K);
    out = CheckBST(T, K);
    if ( out < 0 )
        printf("No.  Height = %d\n", -out);
    else
        printf("Yes.  Key = %d\n", out);

    return 0;
}
/* 你的代码将被嵌在这里 */

Sample Input 1: (for the following tree)

3

Sample Output 1:

Yes.  Key = 3

Sample Input 2: (for the following tree)

2

Sample Output 2:

No.  Height = 3
代码
int getheight(BinTree T){
    if(T==NULL)return 0;
    return 1+(getheight(T->Left)>getheight(T->Right)?getheight(T->Left):getheight(T->Right));
}
int check(BinTree t,int k);
void make(BinTree T);
int a[100],now=-1;
int CheckBST ( BinTree T, int K ){
    if(T==NULL)return 1;
    make(T);
    if(check(T,K)==0)return -getheight(T);
    else return check(T,K);
}
int check(BinTree t,int k){
    int i;
    for(i=0;i<now;i++){
        if(a[i]>a[i+1]) return 0;
    }
    return a[k-1];
}
void make(BinTree T){
    if(T==NULL)return;
    make(T->Left);
    a[++now]=T->Key;
    make(T->Right);
}
评测结果:答案正确(10 分)
测试点结果得分耗时内存
0答案正确33 ms256 KB
1答案正确33 ms380 KB
2答案正确13 ms256 KB
3答案正确22 ms384 KB
4答案正确12 ms296 KB
a.c: In function ‘BuildTree’:
a.c:35:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ^~~~~~~~~~~~~~~
a.c:36:25: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     for (i=0; i<N; i++) scanf("%d", &postorder[i]);
                         ^~~~~~~~~~~~~~~~~~~~~~~~~~
a.c:37:25: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     for (i=0; i<N; i++) scanf("%d", &inorder[i]);
                         ^~~~~~~~~~~~~~~~~~~~~~~~
a.c: In function ‘main’:
a.c:50:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &K);
     ^~~~~~~~~~~~~~~