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

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

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

       

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

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

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

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

       

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

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

       

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

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

       

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

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

Mergesort is stable. (2分)

       

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

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

       

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

(logN)3(logN)^3 is O(N)O(N). (2分)

       

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

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

Given input { 46, 79, 56, 38, 40, 84 }. Which one of the following is the initial heap built by heap sort? (3分)

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

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

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

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

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

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

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

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

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

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

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

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' right links are both threads? (3分)

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

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

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

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

b.jpg

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

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

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

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

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

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

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

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

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

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

Let TT be a tree of NN nodes created by union-by-size without path compression, then the minimum depth of TT may be (3分)

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

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

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

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
函数题总分: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
代码
bool IsTopSeq( LGraph Graph, Vertex Seq[] ){
	int Indegree[Graph->Nv];
	int i;
	for(i=0;i<Graph->Nv;i++){
		Indegree[i]=0;
		Seq[i]--;
	}
		
	PtrToAdjVNode T;
	for(i=0;i<Graph->Nv;i++){
		T=Graph->G[i].FirstEdge;
		while(T!=NULL){
			Indegree[T->AdjV]++;
			T=T->Next;
		}
	}
	for(i=0;i<Graph->Nv;i++){
		Vertex V=Seq[i];
		if(Indegree[V]!=0)return false;
		T=Graph->G[V].FirstEdge;
		while(T!=NULL){
			Indegree[T->AdjV]--;
			T=T->Next;
		}
	}
	return true;
} 

评测结果:答案正确(8 分)
测试点结果得分耗时内存
0答案正确42 ms256 KB
1答案正确12 ms376 KB
2答案正确12 ms256 KB
3答案正确12 ms384 KB
4答案正确129 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]);
             ^~~~~~~~~~~~~~~~~~~~