浙江大学2019-20秋冬《数据结构基础》期中模拟练习(45分钟)
开始时间01/01/2016 8:00:00 AM
结束时间01/18/2038 8:00:00 AM
答题时长45分钟
考生Raul
得分100
总分100

判断题得分:15总分:15
1-1

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

       

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

1-2

If a linear list is represented by a linked list, the addresses of the elements in the memory must be consecutive. (3分)

       

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

1-3

ADT is the abbreviation for Abstract Data Type in the textbook of data structures. (3分)

       

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

1-4

NlogN\sqrt{N}logN is O(N)O(N). (3分)

       

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

1-5

In Union/Find algorithm, if Unions are done by size, the depth of any node must be no more than N/2N/2, but not O(logN)O(logN). (3分)

       

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

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

Given the shape of a binary tree shown by the figure below. If its inorder traversal sequence is { e, a, c, b, d, g, f }, then the node on the same level of c must be: (5分)

mt2.JPG

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

2-2

list.jpg

Which one of the following is the data structure that is best represented by the above picture? (1分)

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

2-3

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

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

2-4

For the following function

int func ( int n )
{   int i = 0, sum = 0;
    while ( sum < n )  sum += ++i;
    return i;
}

the time complexity is: (5分)

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

2-5

If a binary search tree of NN nodes is also a complete binary tree, then among the following, which one is FALSE? (5分)

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

2-6

If graph G is NOT connected and has 14 edges, then it must have at least __ vertices. (5分)

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

2-7

How many distinct topological sequences are there in the following DAG?(5分)

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

2-8

Given the popping sequence of a stack as {1, 2, 3, 4, 5}. Among the following, the impossible pushing sequence is: (5分)

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

2-9

A full tree of degree 3 is a tree in which every node other than the leaves has 3 children. How many leaves does a full tree of degree 3 have if it has 127 nodes? (5分)

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

2-10

For a sequentially stored linear list of length NN, the time complexities for query and insertion are: (5分)

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

2-11

The following figure shows the AOE network of a project with 8 activities. The earliest and the latest completion times of the activity d are __, respectively. (5分)

GRE19-5.jpg

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

2-12

Since the speed of a printer cannot match the speed of a computer, a buffer is designed to temperarily store the data from a computer so that later the printer can retrieve data in order. Then the proper structure of the buffer shall be a: (5分)

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

2-13

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

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

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

Please fill in the blanks in the program which deletes a given element at position p from a min-heap H.

Deletion ( PriorityQueue H,  int p )  /* delete the element H->Elements[p] */
{
   ElementType temp;
   int child;

   temp = H-> Elements[ H->Size-- ];
   if ( temp < H->Elements[p] ) {
      while ( (p != 1) && (temp < H->Elements[p/2]) ) { 
         (3分);
         p /= 2;
      } 
   }
   else {
      while( (child = 2*p) <= H->Size) {
         if ( child != H->Size && (3分) )
            child ++;
         if ( (3分) ) {
            H->Elements[p] = H->Elements[child];
            p = child;
         }
         else
            break;
      }
   }
   H->Elements[p] = temp;
}
评测结果
答案正确(9 分)
测试点得分
序号结果得分
0答案正确3
1答案正确3
2答案正确3

5-2

The function is to return the reverse linked list of L, with a dummy header.

List Reverse( List L )
{
    Position Old_head, New_head, Temp;
    New_head = NULL;
    Old_head = L->Next;

    while ( Old_head )  {
        Temp = Old_head->Next;
        (3分);  
        New_head = Old_head;  
        Old_head = Temp; 
    }
    (3分);
    return L;
}
评测结果
答案正确(6 分)
测试点得分
序号结果得分
0答案正确3
1答案正确3

5-3

The function Dijkstra is to find the 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 MGraph is defined as the following:

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;  /* Number of vertices */
    int Ne;  /* Number of edges    */
    WeightType G[MaxVertexNum][MaxVertexNum]; /* adjacency matrix */
};
typedef PtrToGNode MGraph;
void Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
{
    int collected[MaxVertexNum];
    Vertex V, W;

    for ( V=0; V<Graph->Nv; V++ ) {
        dist[V] = Graph->G[S][V];
        path[V] = -1;
        collected[V] = false;
    }
    dist[S] = 0;
    collected[S] = true;

    while (1) {
        V = FindMinDist( Graph, dist, collected );
        if ( V==ERROR ) break;
        collected[V] = true;
        for( W=0; W<Graph->Nv; W++ )
            if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {
                if ( (4分) ) {
                    dist[W] = (3分);
                    path[W] = (3分);
                }
            }
    } /* end while */
}
评测结果
答案正确(10 分)
测试点得分
序号结果得分
0答案正确4
1答案正确3
2答案正确3