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

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

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

       

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

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

       

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

If a linear list is represented by a linked list, the addresses of the elements in the memory must be consecutive. (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

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

       

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

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

       

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

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

       

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

"Circular Queue" is defined to be a queue implemented by a circularly linked list or a circular array. (2分)

       

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

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

       

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

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 分)
单选题总分:60得分:39
2-1

Suppose that the level-order traversal sequence of a min-heap is {8, 38, 25, 58, 52, 82, 70, 60}. Use the linear algorithm to adjust this min-heap into a max-heap, and then run DeleteMax twice. The inorder traversal sequence of the resulting tree is: (3分)

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

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

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

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

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

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

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

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

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

A relation RR is defined on a set SS. If for any elements aa, bb and cc in SS, we have that if "aa RR bb" is true and "bb RR cc" is true, then "aa RR cc" must be true, then RR is said to be __ over SS. (3分)

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

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

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

The inorder and the postorder traversal sequences of a binary tree are 1 2 3 4 5 6 7 and 2 3 1 5 7 6 4, respectively. Then the preorder traversal sequences is: (3分)

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

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

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

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

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

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

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

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

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

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

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

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

评测结果:未作答(0 分)
2-18

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

评测结果:未作答(0 分)
2-19

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

90.jpg

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

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

评测结果:答案正确(3 分)
程序填空题总分: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;
} 

5-2

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

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

void BuildMaxHeap( 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!

函数题总分: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