1-1

The sum of degrees of all vertices of an undirected connected graph is even . (3 branch )

T         F

Author: DS Course group

Organization: Zhejiang University

1-2

If undirected graph G You must do two breadth first searches to access all of its vertices , be G There must be 2 Connected components . (3 branch )

T         F

Author: DS Course group

Organization: Zhejiang University

1-3

so-called “ Circular queue ” It refers to the queue represented by one-way circular list or circular array . (2 branch )

T         F

Author: DS Course group

Organization: Zhejiang University

1-4

The traversal sequence of a binary tree is exactly the same as that of a binary tree , Then any node in the binary tree must have no right child . (3 branch )

T         F

Author: DS Course group

Organization: Zhejiang University

1-5

The two main aspects of algorithm analysis are time complexity and space complexity analysis . (2 branch )

T         F

Author: DS Course group

Organization: Zhejiang University

1-6

If the input sequence of a stack is {1, 2, 3, 4, 5}, You can't get it {3, 4, 1, 2, 5} Such a stack out sequence . (3 branch )

T         F

Author: Xu Jingchun

Organization: Zhejiang University

1-7

Save a complete binary tree in the array （ The subscript of the root node is 1）. Then the subscript is 23 and 24 The two nodes of are brothers . (3 branch )

T         F

Author: He Qinming

Organization: Zhejiang University

1-8

If you use a linked list to represent a linear list , Then the addresses of the elements in the table must be continuous . (3 branch )

T         F

Author: Chen Yue

Organization: Zhejiang University

1-9

In a tree containing 4,5,6 In the binary search tree composed of a series of integer nodes , If node 4 and 6 On the same level of the tree , Then we can determine the node 5 It must be a node 4 and 6 The father node of . (3 branch )

T         F

Author: DS Course group

Organization: Zhejiang University

1-10

take 1,2,3,4,5,6 Sequentially insert initially empty AVL In the tree , When this is done 6 After insertion of elements , The AVL The result of preorder traversal of the tree is ：4,2,1,3,5,6. (3 branch )

T         F

2-1

In the union search set problem , Known set elements 0~8 Therefore, the corresponding parent node number values are { 1, -4, 1, 1, -3, 4, 4, 8, -2
}（ notes ：−n Represents the tree root and the corresponding set size is n）, Then the element 6 and 8 The set in which it is merged （ Requires that small sets be merged into large sets ） after , What are the tree root and parent node numbers corresponding to the set ? (4 branch )

* 4 and -5
* 8 and -5
* 8 and -6
* 1 and -6
Author: DS Course group

Organization: Zhejiang University

2-2

In the following functions , Which function has the fastest growth rate ? (4 branch )

* N(logN)​4​​
* N​3​​
* NlogN​2​​
* N​2​​logN
Author: DS Course group

Organization: Zhejiang University

2-3

given N×N×N 3D array of A, If the array is not changed , The time complexity of finding the smallest element is ：(4 branch )

* O(NlogN)
* O(N​2​​)
* O(N​3​​logN)
* O(N​3​​)
Author: DS Course group

Organization: Zhejiang University

2-4

Let a non empty complete binary tree  T  All nodes of the leaf are located in the same layer , And every non leaf node has 2 Child node . if  T  Yes  k  Leaf nodes , be  T The total number of nodes for is ：(4 branch )

* k​2​​
* 2k−1
* 2k
* 2​k​​−1
Author: The real question of postgraduate entrance examination

Organization: Zhejiang University

2-5

For the smallest heap （ Small top pile ）{1,3,2,12,6,4,8,15,14,9,7,5,11,13,10} After deleting the smallest element three times , The result sequence was ：(4 branch )

* 4,6,5,12,7,10,8,15,14,9,13,11
* 4,5,6,12,7,10,8,15,14,13,9,11
* 4,5,6,7,8,9,10,11,12,13,14,15
* 4,6,5,13,7,10,8,15,14,12,9,11
Author: DS Course group

Organization: Zhejiang University

2-6

Trident , The degree is 1 There are 5 individual , The degree is 2 Node of 3 individual , The degree is 3 Node of 2 individual , How many leaf nodes does the tree contain ? (4 branch )

* 10
* 13
* 8
* 12
Author: DS Course group

Organization: Zhejiang University

2-7

take {5, 2, 7, 3, 4, 1, 6} Insert the initial empty binary search tree in turn . Then the result of the postorder traversal of the tree is ：(4 branch )

* 1, 4, 3, 2, 6, 7, 5
* 1, 2, 3, 4, 6, 7, 5
* 1, 4, 2, 6, 3, 7, 5
* 5, 4, 3, 7, 6, 2, 1
Author: DS Course group

Organization: Zhejiang University

2-8

expression a*(b+c)-d The suffix expression for is ： (4 branch )

* a b c d * + -
* a b c + * d -
* a b c * + d -
* - + * a b c d
Author: DS Course group

Organization: Zhejiang University

2-9

Let a piece of text contain characters {a, b, c, d, e}, The frequency of occurrence is {3, 2, 5, 1, 1}. After Huffman coding , The number of bytes of text is ： (4 branch )

* 40
* 36
* 25
* 12
Author: DS Course group

Organization: Zhejiang University

2-10

From in graph d The possible results of depth first traversal algorithm are as follows ： (4 branch )

* d,a,e,b,c,f
* d,e,a,c,f,b
* d,f,c,e,a,b
* d,a,c,f,e,b
Author: DS Course group

Organization: Zhejiang University

2-11

In a non empty chain queue without leading nodes , hypothesis f and r The pointer is the head team and the tail team , Insert s The node operation is ( ). (4 branch )

* f->next=s; f=s;
* r->next=s; r=s;
* s->next=s; r=s;
* s->next=f; f=s;
Author: Ice

Organization: Zhejiang University City College

2-12

In a single linked list , if p The node is not the last node , stay p Insert after s Referred node , Then execute  (4 branch )

* s->next=p->next; p->next=s;
* s->next=p; p->next=s;
* s->next=p->next; p=s;
* p->next=s; s->next=p;

5-1

The following code functions from a big top heap H At a specified location p Start filtering .
void PercolateDown( int p, PriorityQueue H ) { int child; ElementType Tmp =
H->Elements[p]; for ( ; p * 2 <= H->Size; p = child ) { child = p * 2; if (
child!=H->Size && (6 branch ) ) child++; if ( H->Elements[child] > Tmp ) (6 branch ); else
break; } H->Elements[p] = Tmp; }
Author: Chen Yue

Organization: Zhejiang University

Time Limit: 400 ms

Memory Limit: 64 MB

5-2

The function of the following code is to return a single linked list of leading nodes L Reverse linked list of .