The time complexity of the following program segment is ()
for(I =； I & ltn；; i++)p = " " & gt； & lt/n； i++)& gt；
for(j = 1； j & ltm； j++)p = " " & gt； & lt/m； j++)>
a[I][j]= 0；
A.(m+n+ 1) C.O(m+n) D.O(m*n)
2. In the single linked list, the pointer P points to the node whose element is X, and the statement to realize "delete the successor of X" is ().
p = p-& gt； Next; b . p-& gt； next = p-& gt； Next-> Next;
C.p->next = p； d . p = p-& gt； Next-> Next;
3. In a single circular linked list with a head pointer and a table length greater than 1, the pointer p points to a node in the linked list. If p->; Next-> Next =
Head, and then ()
A.p points to the head node, and B.p points to the tail node.
The direct successor of C.*p is the head node D.*P The direct successor of C. * P is the tail node.
4. The condition for judging that the first node chain queue is empty is ()
A.Q.front==NULL
C.Q.front==Q.rear D.Q.front！ =Q.rear
5. There are two strings T and P, and the string operation to find the position where P first appears in T is called ().
A. join B. find substring C. character positioning D. substring positioning
6. The length of the generalized table A=(a, (b), (), (c, d, e)) is ().
a4 b . 5 c . 6d . 7
7. The height of a binary tree with 18 nodes is at least ().
a3 b . 4 c . 5d . 6
8. It is known that the preorder sequence of a binary tree is ABDECF, the middle sequence is DBEAFC, and the postorder sequence is ().
A.DEBCFA D.DEBFCA
9. The degree of vertex in undirected graph refers to () of graph.
A. the number of simple paths through vertex B. The number of vertices adjacent to the vertex
C. number of loops passing through a vertex D. number of vertices connected with the vertex
10. Given the following figure, the possible sequence obtained by breadth-first traversal from vertex A is ().
Britain, France and Germany
British Airways
Royal British Airways
D.a c d b f e
1 1. Among the following sorting methods, the average time performance is O(nlogn), and the best spatial performance is ().
A. Quick sorting B. Heap sorting C. Merge sorting D. Cardinal sorting
12. A group of keywords is called {25, 48, 36, 72, 79, 82, 23, 40, 16, 35}, where every two adjacent keywords are ordered subsequences. The result of merging these subsequences. WingwIT.CoM is ().
A.{25,36,48,72,23,40,79,82, 16,35}
B.{25,36,48,72, 16,23,40,79,82,35}
C.{25,36,48,72, 16,23,35,40,79,82}
D.{ 16,23,25,35,36,40,48,72,79,82}
13. Let the linear table stored in sequence have 123 elements, which are divided into three blocks according to the requirements of block search. If the index table uses sequential search to determine blocks and performs sequential search in the determined blocks, when the search probabilities are equal, the average search length when the block search is successful is ().
2 1
14. The characteristic of indexing non-sequential files is ()
A. There is something wrong with the main file and the index table. B. The main file is in order and the index table is out of order.
C. The master file is in order, and the index table is in order. D. the main file is out of order, and the index table is out of order.
15. The main advantage of inverted files is ()
A. Easy to insert and delete operations B. Easy to recover files.
C, convenient multi-keyword query d, saving storage space.
2. Fill in the blanks (this big question has 10 small questions, each with 2 points. If there are two spaces, each space has 1 points, a total of 20 points)
16. The characteristic of abstract data type is to encapsulate _ _ _ _ _ _ _ _ and _ _ _ _ _ together, so that the real information is hidden.
17. When deleting an element from the sequential table, all elements after the deleted element in the table need a _ _ _ _ _ _ _ position.
18. In the queue, the end of the allowed insert operation is called _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
19. As shown in the figure, two stacks share a vector space, and top 1 and top are pointers to the top elements of two stacks, so the judgment condition of "stack full" is _ _ _ _ _ _ _ _ _.
20. let S 1= "good", S2= ""and S3= "book", then S 1, S2 and S3 are connected in turn, and the result is _ _ _ _ _ _ _.
2 1. Assuming that the three-dimensional array A[ 10][9][8] is stored in the order of row priority, if each element occupies 3 storage units and the first address is 100, the storage address of element A[9][8][7] is _ _ _ _ _ _.
22. It is known that in a tree with n nodes, there are only branch nodes with degree k and leaf nodes with degree 0, so the number of leaf nodes contained in the tree is _ _ _ _ _ _ _ _ _.
23. The graph that can successfully complete topological sorting must be _ _ _ _ _ _ _ _.
24. If the keyword order before sorting is close to positive or reverse order, it is more appropriate to choose _ _ _ _ _ _ _ _ _ between heap sorting and quick sorting.
25. Assuming that the table length of the hash table is m and the hash function is H(key), if the conflict is solved by linear probe method, the probe address sequence is expressed as _ _ _ _ _ _ _ _ _ _.
Third, answer the question (this big question has four small questions, each with 5 points, a total of 20 points)
26. Suppose the character set used in the communication message is {a, b, c, d, e, f}, and the frequency of the first character in the message is 34,5,12,23,8, 18. Try to design a huffman encoding for these six characters. Please draw the Huffman tree you constructed first (the weight of the left child node in the tree is required to be less than the weight of the right child node), and then write the code corresponding to each character separately.
27. It is known that a graph is shown in the following figure, and its vertices are stored in the vertex table of the adjacency table in the order of A, B, C, D, E and F. Please draw the adjacency table of this graph so that the vertex sequence obtained by depth-first traversal according to this adjacency table is acbefd, and the vertex sequence obtained by breadth-first traversal is acbdfe.
28. The ternary table of two known 4×5 sparse matrices is as follows:
0 1 4 16 0 1 1 32
1 2 2 18 1 2 2 - 22
2 3 4 - 25 2 2 5 69
3 4 2 28 3 3 4 25
4 4 2 5 1
Please draw a ternary table of the sum of these two sparse matrices.
29. Starting from the empty tree, insert keywords 40, 8, 90, 15, 62, 95, 12, 23, 56, 32 in turn to construct a binary sort tree.
(1) Draw a binary tree.
(2) After deleting the node with the element value of 90 in the tree, draw a binary sort tree.
Fourth, the algorithm reading problem (this big problem has four small questions, each with 5 points, a total of 20 points)
30. As shown in the figure, two queues are implemented using the same cyclic vector space, and the type of queue 2 is defined as follows:
Typedef structure {
Data type data [maxsize];
int front[2]，length[2]；
} Queue2
For i=0 or 1, front[i] and length[i] are the head pointer and length field of the i-th queue, respectively. Please fill in the appropriate content in the blank to realize the enqueue operation of the I-th circular queue.
int EnQueue(Queue2*Q，int i，DataType x)
{//If the i-th queue is not satisfied, element X enters the queue and returns 1, otherwise it returns 0.
If (I<0 | | i> 1) returns 0;
If ((1))
Returns 0;
q->； data[(2)]= x；
q->； Length [(3)]++;
Returns1;
}
( 1)
(2)
(3)
The storage structure of the clue list of 3 1. binary tree is shown in Figure (b), where P is the pointer to the root node and Figure (a) is the node structure. Read the following algorithm and answer the questions:
(1) Write the output result of executing function call f(p);
(2) Briefly describe the function f.
Void f (binary tree t) {
while(t)
{
printf(t-& gt； Data);
if(t->； lchild)
t = t-& gt； lchild
other
t = t-& gt； rchild
}
}
( 1)
(2)
32. The function FindCycle(G, i) below is to find a simple loop through vertex v i by using depth-first search strategy for a directed graph G with adjacency table as storage structure. The array cycle_path is used to save the cycle formed in the search process, and cycle_path[k]=j(j≥0) means that the next vertex of vertex v k in the cycle is v j, so please fill in the blanks with appropriate contents to make it a complete algorithm.
Vertex first side
The node structure of vertex table of known adjacency table is:
Next up is adjvex
The edge table node EdgeNode has the following structure:
int cycle _ path[MaxNum]；
int FindCycle(ALGraph*G，int i)
{//If there is a loop, return 1, otherwise return 0.
int j；
for(j = 0； j n； j++)cycle _ path[j]=- 1；
Returns DFSPath(G, i, i);
}
Int DFSPath (algebra *G, int j, int i)
{
edge node * p；
int cycled = 0；
for(p = G-& gt； adjlist[j]。 Firstedge Procter & Gamble. & amp！ Circulation; p = p-& gt； Next)
{
cycle _ path[j]= p-& gt； adjvex
If ((1)) cycle =1; //Find the circuit.
other
If (circular path [p->; Adjvex] =-1) Cycle = (2);
}
Regression (3)
}
( 1)
(2)
(3)
33. Read the following function algorithm and answer the questions.
(1) Suppose the integer array A [1...8] is (3, 8, 9, 1, 7, 4, 2, 6) in turn. When the execution function calls algo(A, 8), how many times does the loop body of the outer while execute? What is the return value of the function?
(2) Briefly describe the function of algo(L, n).
int algo(int L[]，intn)
{
int i=0，j，s= 1，t = n；
And (me! =(n+ 1)/2)
{
int x = L[s]；
I = s； j = t；
While (I & ltj)p = "">；; & lt/j)>