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

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

If the inorder and the postorder traversal sequences of a binary tree have exactly the same order, then none of the nodes in the tree has a right subtree. (2分)

       

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

If keys are pushed onto a stack in the order abcde, then it's impossible to obtain the output sequence cedab. (2分)

       

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

If NN numbers are stored in a singly linked list in increasing order, then the average time complexity for binary search is O(logN)O(logN). (2分)

       

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

Shell sort is stable. (2分)

       

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

Given a binary search tree with 20 integer keys which include 5, 6, and 7, if 5 and 7 are on the same level, then 6 must be their parent. (2分)

       

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

For a graph, if each vertex has an even degree, we can find an Euler circuit that visits every vertex exactly once. (2分)

       

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

logN20logN^{20} is O(N)O(N). (2分)

       

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

To sort NN records by quick sort, the worst-case time complexity is O(NlogN)O(NlogN). (2分)

       

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

Quadratic probing is equivalent to double hashing with a secondary hash function of Hash2(k)=kHash_2(k) = k. (2分)

       

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

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

       

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

Use Dijkstra algorithm to find the shortest paths from 1 to every other vertices. In which order that the destinations must be obtained? (3分)

Dij1.JPG

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

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

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

For the quicksort implementation with both the left and the right pointers stop when an element with the same key as the pivot is found during the partitioning, what is the running time when all keys are equal? (3分)

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

The following is the part of depth-first search tree to find the articulation points, and the Num(v) value has been marked beside each vertex v. The back edges are not shown. Which of the following situation is impossible? (3分)

288a38a2-e5cc-484f-b0d3-ded92aa32648.jpg

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

To find the minimum spanning tree with Prim's algorithm for the following graph, a sequence of vertexes 6, 1, 2, 3 was found during the algorithm's early steps. Which one vertex will be added in the next step? (3分)

c.jpg

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

The maximum flow from v1 to v6 is __: (3分)

b.jpg

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

A graph with 100 vertices and 12 edges must have at most __ connected component(s). (3分)

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

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

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

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

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

It is known that a 3-heap is a heap whose nodes have 3 children. Suppose that the level-order traversal sequence of a max-3-heap is {88, 76, 65, 82, 68, 46, 52, 44, 62, 33, 75, 28, 55, 60}. Use the linear algorithm to adjust this max-3-heap into a min-3-heap, and then run DeleteMin. As a result, there are __ nodes whose positions are not moved in the process. (3分)

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

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

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

Suppose that the size of a hash table is 11, and the hash function is H(key)=key%11. The following 4 elements have been inserted into the table as Addr(14)=3, Addr(38)=5, Addr(61)=6, Addr(86)=9. When open addressing with quadratic probing is used to solve collisions, the address of the element with key=60 will be . (3分)

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

Given input {15, 9, 7, 8, 20, -1, 4}. If the result of the 1st run of Shell sort is {15, -1, 4, 8, 20, 9, 7}, then the initial increment must be: (3分)

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

Following is the C-like pseudo code of a function that takes a Queue as an argument.

void foo(Queue Q)
{
    Stack S = CreateStack();  // create an empty stack

    while (!IsEmpty(Q))
    {
        // dequeue an item from Q and push it into S
        Push(S, Dequeue(Q));
    }

    while (!IsEmpty(S))
    {
        // pop an item from S and enqueue it into Q
        Enqueue(Q, Pop(S));
    }
		
    DisposeStack(S);
}

What does the above function do? (3分)

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

In order to convert the infix expression 4 * 3 + (6 * 3 - 12) to postfix expression using a stack SS, then the minimum size of SS must be: (3分)

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

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

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

Insert {18, 23, 4, 26, 31, 33, 17, 39} one by one into an initially empty hash table of size 13 with the hash function H(Key)=Key%13H(Key) = Key\%13, and linear probing is used to resolve collisions. What is the loading density when the first collision occurs? (3分)

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

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

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

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

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

Let TT be a tree created by union-by-size with NN nodes, then the height of TT can be . (3分)

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

The function is to find the K-th smallest element in a list A of N elements. The function BuildMaxHeap(H, K) is to arrange elements H[1] ... H[K] into a max-heap. Please complete the following program.

ElementType FindKthSmallest ( int A[], int N, int K )
{   /* it is assumed that K<=N */
    ElementType *H;
    int i, next, child;

    H = (ElementType *)malloc((K+1)*sizeof(ElementType));
    for ( i=1; i<=K; i++ ) H[i] = A[i-1];
    BuildMaxHeap(H, K);

    for ( next=K; next<N; next++ ) {
        H[0] = A[next];
        if ( H[0] < H[1] ) {
            for ( i=1; i*2<=K; i=child ) {
                child = i*2;
                if ( child!=K && (3分) ) child++;
                if ( (3分) )
                    H[i] = H[child];
                else break;
            }
            H[i] = H[0];
        }
    }
    return H[1];
}

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

The function is to find the K-th largest element in a list A of N elements. The initial function call is Qselect(A, K, 0, N-1). Please complete the following program.

ElementType Qselect( ElementType A[], int K, int Left, int Right )
{
    ElementType Pivot = A[Left];
    int L = Left, R = Right+1;

    while (1) {
        while ( A[++L] > Pivot ) ;
        (3分);
        if ( L < R ) Swap( &A[L], &A[R] );
        else break;
    }
    Swap( &A[Left], &A[R] );
    if ( K < (L-Left) )
        return Qselect(A, K, Left, R-1);
    else if ( K > (L-Left) )
        (3分);
    else
        return Pivot;
}
评测结果:部分正确(3 分)
序号结果得分
0答案正确3
1段错误0
函数题总分:8得分:8
6-1
Is Topological Order

Write a program to test if a give sequence Seq is a topological order of a given graph Graph.

Format of functions:

bool IsTopSeq( LGraph Graph, Vertex Seq[] );

where LGraph is defined as the following:

typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;
    PtrToAdjVNode Next;
};

typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;
struct GNode{  
    int Nv;
    int Ne;
    AdjList G;
};
typedef PtrToGNode LGraph;

The function IsTopSeq must return true if Seq does correspond to a topological order; otherwise return false.

Note: Although the vertices are numbered from 1 to MaxVertexNum, they are indexed from 0 in the LGraph structure.

Sample program of judge:

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

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

typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;
    PtrToAdjVNode Next;
};

typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;
struct GNode{  
    int Nv;
    int Ne;
    AdjList G;
};
typedef PtrToGNode LGraph;

LGraph ReadG(); /* details omitted */

bool IsTopSeq( LGraph Graph, Vertex Seq[] );

int main()
{
    int i, j, N;
    Vertex Seq[MaxVertexNum];
    LGraph G = ReadG();
    scanf("%d", &N);
    for (i=0; i<N; i++) {
        for (j=0; j<G->Nv; j++)
            scanf("%d", &Seq[j]);
        if ( IsTopSeq(G, Seq)==true ) printf("yes\n");
        else printf("no\n");
    }

    return 0;
}

/* Your function will be put here */

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

topord.JPG

6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6

Sample Output:

yes
yes
yes
no
no
代码
//Although the vertices are numbered from 1 to MaxVertexNum, they are indexed from 0 in the LGraph structure
int in[MaxVertexNum];
bool IsTopSeq( LGraph Graph, Vertex Seq[] ){
    int i;
    PtrToAdjVNode temp;
    for(i=0;i<MaxVertexNum;i++)in[i]=0;
    for(i=0;i<Graph->Nv;i++){
        temp=Graph->G[i].FirstEdge;
        while(temp){
            in[temp->AdjV]++;
            temp=temp->Next;
        }
    }
    for(i=0;i<Graph->Nv;i++){
        if(in[Seq[i]-1]!=0)return 0;
        else{
            temp=Graph->G[Seq[i]-1].FirstEdge;
            while(temp){
                in[temp->AdjV]--;
                temp=temp->Next;
            }
        }
    }
    return 1;
}
评测结果:答案正确(8 分)
测试点结果得分耗时内存
0答案正确43 ms256 KB
1答案正确12 ms256 KB
2答案正确13 ms256 KB
3答案正确13 ms256 KB
4答案正确128 ms512 KB
a.c: In function ‘ReadG’:
a.c:68:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Nv);   /* 读入顶点个数 */
  ^~~~~~~~~~~~~~~~
a.c:71:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &(Graph->Ne));   /* 读入边数 */
  ^~~~~~~~~~~~~~~~~~~~~~~~~
a.c:76:7: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &E->V1, &E->V2);
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.c: In function ‘main’:
a.c:90:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ^~~~~~~~~~~~~~~
a.c:93:13: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &Seq[j]);
             ^~~~~~~~~~~~~~~~~~~~