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

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

Given a binary search tree with 20 integer keys which include 10, 11, and 12, if 10 and 12 are on the same level, then 11 must be their common ancestor. (2分)

       

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

In a directed graph, the sum of the in-degrees and out-degrees of all the vertices is twice the total number of edges. (2分)

       

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

The minimum spanning tree of a connected weighted graph with vertex set V={ A, B, C, D, E } and weight set W={ 1, 3, 2, 5, 1, 7, 9, 8, 4} must be unique. (2分)

       

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

If the preorder and the postorder traversal sequences of a binary tree have exactly the opposite orders, then none of the nodes in the tree has two subtrees. (2分)

       

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

If there are less than 20 inversions in an integer array, then Insertion Sort will be the best method among Quick Sort, Heap Sort and Insertion Sort. (2分)

       

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

After the first run of Bubble Sort, it is possible that no element is placed in its final position. (2分)

       

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

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

       

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

If the most commonly used operations are to visit a random position and to insert and delete the last element in a linear list, then sequential storage works the fastest. (2分)

       

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

If 7 elements have been stored in a hash table of size 13 at positions { 0, 1, 2, 4, 5, 10, 11 }, and the hash function is H(x)=x%13H(x)=x\%13. Then an empty spot can't be found when inserting the element 40 with quadratic probing. (2分)

       

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

O(N2)O(N^2) is the same as O(1+2+3++N)O(1+2+3+\cdots+N). (2分)

       

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

Rehashing is required when an insertion to a hash table fails. Which of the following is NOT necessary to rehashing? (3分)

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

Given that the pushing sequence of a stack is { 1, 2, \cdots, nn } and popping sequence is { p1p_1, p2p_2, \cdots, pnp_n }. If p2=np_2 = n, how many different possible popping sequences can we obtain? (3分)

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

Quick Sort can be implemented by a recursive function void Qsort( ElementType A[ ], int Left, int Right ). If we are to implement the function Qsort() in a non-recursive way with a stack, which of the following should be packed as the elements of the stack? (3分)

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

To sort { 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 } by Shell Sort, if we obtain ( 4, 2, 1, 8, 3, 5, 10, 6, 9, 11, 7 ) after the first run, and ( 1, 2, 3, 5, 4, 6, 7, 8, 9, 11, 10 ) after the second run, then the increments of these two runs must be __ , respectively. (3分)

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

When inserting a new key a into a binary search tree T with 1025 nodes, the worst-case number of comparisons between a and the keys already in T is in the range of: (3分)

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

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

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

Given the structure of a binary search tree (as shown in the figure), which one of the following insertion sequences is impossible? (3分)

206.jpg

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

Suppose that the level-order traversal sequence of a max-heap is {98, 72, 86, 60, 65, 12, 23, 50}. Use the linear algorithm to adjust this max-heap into a min-heap, and then run DeleteMin twice. The inorder traversal sequence of the resulting tree is: (3分)

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

The inorder and the postorder traversal sequences of a binary tree are a b c d e f g and b c a e g f d, respectively. Then the preorder traversal sequences is: (3分)

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

The maximum flow in the following network is: (3分)

89.jpg

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

Given an undirected graph, and the edge set of a DFS from V0 as: {(V0,V1) , (V0,V4) , (V1,V2) , (V1,V3) , (V4,V5) , (V5,V6)} . Which one the following cannot be the sequence of another DFS? (3分)

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

A relation RR is defined on a set SS. If for every element ee in SS, "ee RR ee" is always true, then RR is said to be __ over SS. (3分)

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

For an in-order threaded binary tree, if the pre-order and in-order traversal sequences are B E A C F D and A E C B D F respectively, which pair of nodes' right links are both threads? (3分)

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

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

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

Which one of the following is the expression tree corresponding to the postfix expression aef+*bc+*? (3分)

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

Which one of the following is a possible postorder traversal sequence of a binary search tree? (3分)

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

For a directed graph, comparing to the representation of the adjacency lists, the adjacency matrix representation is easier to: (3分)

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

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

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

Given a weighted graph as shown by the figure. Which one of the following statements is TRUE about its minimum spanning tree? (3分)

spanning tree.jpg

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

If the hash values of nn keys are all the same, and linear probing is used to resolve collisions, then the minimum total number of probings must be __ to insert these nn keys . (3分)

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

Given an array a[]of n integers, the function MissingMin is to find and return the minimum positive integer which is NOT in the array. For example, given { 3, -1, 8, 1, 0 }, 2 is the smallest positive integer which is missing.

int MissingMin( int a[], int n )
{
    int i, j, min, missing=1;
		
    for( i=0; i<n; i++ ){
        min = i;
        for( j = i+1; j < n; j++ )
            if ((3分))  min = j;	
        if ( min != i )  swap(a[i], a[min]);
        if ( a[i] == missing )  missing++;
        else if ( a[i] > missing )  (3分);
    }
    return missing;
} 

评测结果:答案正确(6 分)
序号结果得分
0答案正确3
1答案正确3
5-2

The function is to turn an array A[] of N elements into a min-heap.

#define leftchild(i) ( 2*(i)+1 )

void BuildMinHeap( ElementType A[], int N )
{  int i, j, child;
   ElementType Tmp;

   for ( i = (N-1)/2; i >= 0; i-- ) {
      j = i;
      for ( Tmp = A[j]; leftchild(j) < N; j = child ) {
         child = leftchild(j);
         if ((2分))
            child ++;
         if ((2分))   A[j] = A[child];
         else  break;
      }
      (2分);
   }
}

Thanks to DOU Yan from Yanshan University for the correction!

评测结果:答案正确(6 分)
序号结果得分
0答案正确2
1答案正确2
2答案正确2
函数题总分:8得分:8
6-1
Shortest Path [2]

Write a program to find the weighted shortest distances from any vertex to a given source vertex in a digraph. It is guaranteed that all the weights are positive.

Format of functions:

void ShortestDist( MGraph Graph, int dist[], Vertex S );

where MGraph is defined as the following:

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;
    int Ne;
    WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;

The shortest distance from V to the source S is supposed to be stored in dist[V]. If V cannot be reached from S, store -1 instead.

Sample program of judge:

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

typedef enum {false, true} bool;
#define INFINITY 1000000
#define MaxVertexNum 10  /* maximum number of vertices */
typedef int Vertex;      /* vertices are numbered from 0 to MaxVertexNum-1 */
typedef int WeightType;

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;
    int Ne;
    WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;

MGraph ReadG(); /* details omitted */

void ShortestDist( MGraph Graph, int dist[], Vertex S );

int main()
{
    int dist[MaxVertexNum];
    Vertex S, V;
    MGraph G = ReadG();

    scanf("%d", &S);
    ShortestDist( G, dist, S );

    for ( V=0; V<G->Nv; V++ )
        printf("%d ", dist[V]);

    return 0;
}

/* Your function will be put here */

Sample Input (for the graph shown in the figure):

7 9
0 1 1
0 5 1
0 6 1
5 3 1
2 1 2
2 6 3
6 4 4
4 5 5
6 5 12
2

Sample Output:

-1 2 0 13 7 12 3 
代码
void ShortestDist( MGraph Graph, int dist[], Vertex S ){
    int known[MaxVertexNum];
    int i,j,min,mini;
    for(i=0;i<MaxVertexNum;i++){
        known[i]=0;
        dist[i]=INFINITY;
    }
    dist[S]=0;
    while(1){
        min=INFINITY;
        for(i=0;i<Graph->Nv;i++){
            if(known[i]==1)continue;
            if(dist[i]<min){
                min=dist[i];
                mini=i;
            }
        }
        if(min==INFINITY)break;
        known[mini]=1;
        for(i=0;i<Graph->Nv;i++){
            if(known[i]==1)continue;
            if(Graph->G[mini][i]<=0||Graph->G[mini][i]==INFINITY)continue;
            if(dist[i]>dist[mini]+Graph->G[mini][i]){
                dist[i]=dist[mini]+Graph->G[mini][i];
            }
        }
    }
    for(i=0;i<Graph->Nv;i++){
        if(dist[i]==INFINITY)dist[i]=-1;
    }
    return;
}
评测结果:答案正确(8 分)
测试点结果得分耗时内存
0答案正确42 ms256 KB
1答案正确32 ms280 KB
2答案正确12 ms256 KB
a.c: In function ‘ShortestDist’:
a.c:91:11: warning: unused variable ‘j’ [-Wunused-variable]
     int i,j,min,mini;
           ^
a.c: In function ‘ReadG’:
a.c:55:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Nv);   /* 读入顶点个数 */
  ^~~~~~~~~~~~~~~~
a.c:58:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &(Graph->Ne));   /* 读入边数 */
  ^~~~~~~~~~~~~~~~~~~~~~~~~
a.c:63:7: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.c: In function ‘main’:
a.c:80:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &S);
     ^~~~~~~~~~~~~~~