First, multiple-choice questions (2 points for each small question, ***24 points)
1. Objects recognized, stored and processed by computers are collectively referred to as (a).
A. Data B. Data elements
C. Data structure D. Data type
2. Stack and queue are both (A)
A. Linear structure of restricted access location B. Linear structure of sequential storage
C. Linear structure of chain storage D. Nonlinear structure of restricted access location
3. Compared with sequential stack, chain stack has obvious advantages (D).
A. the insertion operation is more convenient. B. the deletion operation is more convenient.
C. there will be no underflow. D. there will be no overflow.
4. The strings with two different storage structures can be abbreviated as (b) respectively.
A. Main string and substring B. Sequential string and chain string
C. target string and pattern string D. variable string and constant string
5. The storage address of the first element of the vector is 100, and the length of each element is 2, so the address of the fifth element is B.
A. 1 10
C. 100
6. String is a special linear table, and its particularity is reflected in: b
A.it can be stored sequentially. A data element is a character.
C. Linked storage data elements can be multiple characters.
7. Suppose that there are only nodes with degree 0 and degree 2 on a binary tree with height h, then such a binary tree contains at least: c.
A.2h B .2h- 1
C.2h+ 1 D. h+ 1
Www.mscto.com Software Development Network
8. The basic traversal strategy of the tree can be divided into the first traversal and the second traversal; The basic traversal strategies of binary trees can be divided into pre-traversal, mid-traversal and post-traversal. Here, the binary tree that we convert into a tree is called the binary tree corresponding to this tree. Which of the following conclusions is correct? A
A. The antecedent traversal sequence of a tree is the same as its corresponding binary tree.
B the traversal order of the back root of a tree is the same as that of the back order of its corresponding binary tree.
C the traversal order of the first root of a tree is the same as that of the middle order of its corresponding binary tree.
D. none of the above is true
9. How many edges does an undirected graph with n vertices have at most? C
A. Note: n(n- 1)
C.n(n- 1)/2 D. 2n
10. In a graph, how many times is the sum of all vertices equal to all edges? C
A. 1/2 B
C.2 D. 4
1 1. When inserting a new node in the binary sort tree, if there is no node in the tree with the same keyword as the node to be inserted and the keyword of the new node is smaller than that of the root node, the new node will become (a).
A. leaf nodes of the left subtree B. branch nodes of the left subtree
C. Leaf nodes of the right subtree D. Branch nodes of the right subtree
Www.mscto.com Software Development Network
12. For the hash function H(key)=key% 13, the keyword called synonym is (d).
35 and 4 1
C. 15 and 44 D.25 and 5 1
2. It is known that the preorder traversal results of a binary tree are A, B, D, E, G, C, F, H, I, J, and the preorder traversal results are D, B, G, E, A, H, F, I, J, C .. Please draw the specific structure of the binary system. (Pay attention to specific steps) (10 score)
See the textbook 128 for the principle.
3. There is a chart as follows. Please write down the results of depth-first and width-first traversal from vertex c0. (10)
Depth first; C0-C 1-C3-C4-C5-C2
Width priority: C0-C 1-C2-C3-C4-C5
Fourth, as shown in the figure below, the minimum spanning tree is obtained according to Kruskal algorithm. It is required to write out the complete steps. (10)
See page 250 of the textbook for the principle.
5. Give a linear table (12, 23, 45, 66, 76, 88, 93, 103, 166) and try to write method of bisection's process on it. And write method of bisection's algorithm. (20 points)
0 1 2 3 4 5 6 7 8
12 23 45 66 76 88 93 103 166
Process:
mid=(0+8)/2=4
High =3, low =0, medium = 1
High =0, low =0, middle =0 (found 12)
High =8, low =5, medium =6 (93 found)
High =8, low =7, medium =7.
High =8 Low =8 Medium =8
Algorithm: See page 84 of the textbook.
6. The node structure of the knowledge list is as follows
The next data
The following algorithm simply selects and sorts the single linked list L with leading nodes, so that the elements in L are arranged from small to large.
Please fill in the appropriate content in the blank to make it a complete algorithm. (The basic idea and execution process of the algorithm can be explained in words, 10)
void SelectSort(LinkedList L)
{
LinkedList p，q，min
Data type rcd
p =( 1)；
And (p! =NULL) {
min = p；
q = p->； Next;
And (q! =NULL){
If ((2) 2))min = q；;
q = q-& gt； Next;
}
If ((3) ){
rcd = p-& gt； Data;
p->； data = min-& gt； Data;
min->； Data = rcd
}
(4) ;
}
}
This question won't. Hey hey. . . .
7. What are the basic properties of a complete algorithm? Briefly explain the meaning of each attribute. (5 points)
Input:
Four basic attributes: 1. Input: There are zero or more externally provided quantities as the input of the algorithm.
2. Output: The algorithm generates at least one quantity as output.
3. Determinism: Every instruction that constitutes the algorithm is clear and definite.
4.: finiteness: The number of times each instruction is executed in the algorithm is limited, and the time for executing each instruction is also limited.
8. What is the phenomenon of queue "false overflow"? How to solve it? (5 points)
The false overflow phenomenon of the queue refers to the phenomenon that the queue tail pointer has reached the upper bound of the array table and overflowed in the sequential queue realized by exponential group, but there is still some free space before the queue head pointer. One of the solutions is to use circular queue technology to connect the ends of array space.
9. Explain and compare various physical structures of files. (6 points)