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
* N3
* NlogN2
* N2logN
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(N2)
* O(N3logN)
* O(N3)
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 )
* k2
* 2k−1
* 2k
* 2k−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 .
List Reverse( List L ) { Position Old_head, New_head, Temp; New_head = NULL;
Old_head = L->Next; while ( Old_head ) { Temp = Old_head->Next; (6 branch ); New_head
= Old_head; Old_head = Temp; } (6 branch ); return L; }
Technology