1. The time complexity of an algorithm primarily depends on ( ).
A. Problem size B. CPU clock speed C. Source code length D. Quality of the compiled binary
Answer: A
2. For a sequential list containing n elements, inserting a new element while preserving the existing order requires shifting ( ) elements on average.
A. n B. n/2 C. 2n D. n²
Answer: B
3. Suppose pointer p points to node A in a singly linked list. To delete node A, the correct pointer operations are ( ).
A. q=p->next; p->data=q->data; p->next=q->next; free(q);
B. q=p->next; q->data=p->data; p->next=q->next; free(q);
C. q=p->next; p->next=q->next; free(q);
D. q=p->next; p->data=q->data; free(q);
Answer: A
4. A doubly linked list node has two pointer fields prev and next. Pointer p references an existing node, and q a node to be inserted. Which sequence correctly inserts q before *p?
A. p->prev->next=q; q->next=p; q->prev=p->prev; p->prev=q;
B. p->prev=q; q->next=p; q->prev=NULL; p->prev=NULL;
C. q->prev=p->prev; p->prev->next=q; q->next=p; p->prev=q->next;
D. q->next=p; p->prev->next=q; p->next=q; q->next=p;
Answer: A
5. A stack has a maximum capacity of 4. Push sequence: A, B, C, D, E, F. Which is a possible pop sequence?
A. CBEDAF B. BCEFAD C. ADFEBC D. EDCBAF
Answer: A
6. A circular queue is stored in array A[0…m]. The enqueue operation is implemented as ( ).
A. rear = rear + 1 B. rear = (rear+1) % m
C. rear = (rear+1) % (m+1) D. rear = (rear+1) % (m-1)
Answer: C
7. Array A[50] holds a circular queue with front=13, rear=5. The current number of elements is ( ).
A. 42 B. 8 C. 43 D. 9
Answer: A
8. Given s1 = "ABCDEFG", s2 = "PQRST". Let Con(x,y) be concatenation, Subs(s,i,j) return j characters from index i, and len(s) the length. The result of Con(Subs(s1,2,len(s2)), Subs(s1,len(s2),2)) is ( ).
A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF
Answer: D
9. A symmetric matrix is stored by its lower triangle (row‑major) in a 1‑D array B[1…n(n-1)/2]. For element aij (i < j) in the lower triangle, its index k in B is ( ).
A. i(i-1)/2 + j – 1 B. i(i-1)/2 + j
C. i(i+1)/2 + j – 1 D. i(i+1)/2 + j
Answer: B
10. A telegraph uses 5 letters with frequencies 2, 4, 5, 7, 8. The weighted path length of the Huffman tree built from them is ( ).
A. 10 B. 96 C. 84 D. 58
Answer: D
11. Level 6 of a comlpete binary tree contains 9 leaf nodes. The maximum number of nodes in this tree is ( ).
A. 41 B. 109 C. 40 D. 119
Answer: B
12. A weighted directed graph G is stored as an adjacency matrix. The in‑degree of vertex vi equals ( ) in the matrix.
A. Sum of non‑zero entries in row i
B. Sum of non‑zero entries in column i
C. Number of non‑∞ and non‑zero entries in row i
D. Number of non‑∞ and non‑zero entries in column i
Answer: D
13. A graph with N vertices and E edges is stored using adjacency lists. Computing the in‑degree for every vertex takes ( ) time.
A. O(N) B. O(N²) C. O(N+E) D. O(N×E)
Answer: C
14. Apply one pass of quicksort (ascending) to the sequence (15, 9, 7, 8, 20, 1, 4). The result is ( ).
A. 9, 7, 8, 4, 1, 15, 20
B. 4, 9, 7, 8, 1, 15, 20
C. 1, 9, 7, 8, 4, 15, 20
D. None of the above
Answer: D
15. For a hash table with n elements, the average search length ( ).
A. is O(log₂n) B. is O(n) C. does not depend on n D. depends on the load factor
Answer: D
II. True / False
1. The definition of an operation depends on the logical structure, and its implementation also depends solely on the logical structure, not on the storage structure. ( ) False
2. All basic linear‑list operations are less efficient on sequential storage than on linked storage. ( ) False
3. Every element in a linear list has both a predecessor and a successor. ( ) False
4. Deleting the bottom element is a fundamental stack operation. ( ) False
5. Both queues and stacks are restricted linear lists; operations can be performed at both ends of the list. ( ) False
6. For a string S of length n, the maximum number of substrings is n(n+1)/2. ( ) True
7. The brute‑force substring search for strings S1 (length n) and S2 (length m) has a best‑case time complexity of O(n+m). ( ) True
8. In a complete binary tree, the left sibling (if it exists) of the parent of a leaf node is always a non‑leaf. ( ) False
9. Sequential storage is unsuitable for complete binary trees; only full binary trees fit sequential storage. ( ) False
10. In a complete binary tree, a node without a left child must be a leaf. ( ) True
11. In a graph, the sum of the degrees of all vertices equals twice the number of edges. ( ) True
12. If all edge weights of a connected undirected graph are distinct, the minimum spanning tree is unique. ( ) True
13. In a directed graph, the sum of in‑degrees of all vertices equals the sum of out‑degrees. ( ) True
14. Binary search requires the table to be ordered, and it may be stored either sequentially or linked. ( ) False
15. When deleting an element from a hash table, it is incorrect to simply remove the entry. ( ) True
III. Fill in the Blanks
- Worst‑case time complexity of the referenced algorithm: O(nⁿ)
- First element of a sequential list is at address 0x11ff7c. Each element is 4 bytes. Address of the 5th element: 0x11ff8c
- In a singly linked list, logically adjacent elements are not necessarily adjacent in memory.
- Accessing the i‑th element in a singly linked list takes time O(n).
- If the input sequence of a stack is 1,2,3,…,n and the first output is n, then the i‑th output is n – i + 1.
- When implementing a queue with a singly linked list, the front of the queue is at the head of the list.
- For a circular singly linked list queue of length n with the front fixed at the tail and only a head pointer, enqueue costs O(1).
- Array
A[1..5, 1..6], each element 5 units, stored in row‑major order starting at address 1000. Address of A[5,5] is 1140. - Target T = "abccdcdccbaa", pattern P = … The 5th match succeeds.
- For a tree of degree 3 with 50 nodes, its minimum height is 5.
- Postorder: DABEC, Inorder: DEBAC. Preorder is CEDBA.
- A Huffman tree contains 215 nodes. The number of distinct codewords it can produce is 108.
- In the adjacency matrix of a directed graph with n vertices and e edges, the number of zero entries is n² – e.
- The maximum number of directed edges in a graph with n vertices is n(n‑1).
- Binary searching for 90 in the ordered list (13,18,24,35,47,50,62,83,90,115,134) requires 2 comparisons.
IV. Problem Solving
1. Stack sequences
Five elements A, B, C, D, E are pushed in that order. The first popped element is C, the second is D. List all valid pop sequences.
Solution: CDEBA, CDBAE, CDBEA
2. Full m‑ary tree properties
A full m‑ary tree of height h (root at level 1, leaves at level h). Every non‑leaf has exactly m children. Nodes are numbered level by level, left to right.
(1) Number of nodes at level i: mi‑1
(2) Parent index of node i (when i>1): ⌊(i – 2) / m⌋ + 1
3. Dijkstra’s shortest path
Given the weighted directed graph with 11 nodes and the edges listed, start from node 3. Complete the Dijkstra execution table.
(M denotes infinity)
4. Kruskal’s minimum spanning trees
For the undirected graph shown, illustrate the step‑by‑step construction of all possible MSTs starting from vertex 1 using Kruskal’s algorithm. (Process omitted in text; requires drawing.)
5. Hash table with linear probing
Hash table size = 15, hash function H(k) = k % 13. Keys: 19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79. Draw the resulting table and compute the average successful and unsuccessful search lengths under equal probability.
Hash table (indices 0‑14):
Average successful search length: (1+2+1+4+3+1+1+3+9+1+1+3) / 12 = 2.5
Average unsuccessful search length: (1 + 13 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2) / 13 = 7
6. Two‑way merge sort
Sqeuence: {503, 87, 512, 61, 908, 170, 897, 275, 653, 462}. Show the sorting process using two‑way merge sort (steps can be illustrated with a tree).
V. Algorithm Design
1. In‑place reversal of a singly linked list
Complete the function that reverses the list using only the original storage. The original list L = {0,2,4,6,8,10} should become L = {10,8,6,4,2,0}.
void ReverseList(LinkNode **head) {
LinkNode *cur, *tmp;
cur = ① ;
while ( ② ) {
tmp = cur->next;
③ ;
④ ;
cur = ⑤ ;
}
}
Answers: ① (*head)->next ② cur != NULL ③ cur->next = (*head)->next ④ (*head)->next = cur ⑤ tmp
2. Iterative preorder traversal of a binary tree
void PreorderTraversal(BinTreeNode *root) {
BinTreeNode *stack[15];
int top = -1;
BinTreeNode *node = root;
while ( ① ) {
if (node != NULL) {
stack[ ② ] = node;
printf("%d\t", node->data);
node = ③ ;
} else {
node = stack[ ④ ];
node = ⑤ ;
}
}
}
Answers: ① top != -1 || node != NULL ② ++top ③ node->leftChild ④ top-- ⑤ node->rightChild
3. Adjacency matrix to adjacency list conversion for an undirected graph
Given the structures, complete the conversion routine.
typedef struct {
VertexType vertices[MAXSIZE];
int arcs[MAXSIZE][MAXSIZE];
int vertexCount, edgeCount;
} AdjMatrix;
typedef struct EdgeNode {
int adjVertex;
struct EdgeNode *next;
} EdgeNode;
typedef struct {
VertexType data;
EdgeNode *firstEdge;
} VertexNode;
typedef struct {
VertexNode adjList[MAXSIZE];
int vertexCount, edgeCount;
} AdjList;
void MatToList(AdjMatrix *amat, AdjList *alist) {
alist->vertexCount = ① ;
alist->edgeCount = ② ;
for (int i = 0; i < amat->vertexCount; i++) {
alist->adjList[i].data = ③ ;
④ ;
}
for (int i = 0; i < amat->vertexCount; i++)
for (int j = 0; j < i; j++) {
if (amat->arcs[i][j] != 0) {
EdgeNode *e1 = (EdgeNode *)malloc(sizeof(EdgeNode));
⑤ ;
⑥ ;
⑦ ;
EdgeNode *e2 = (EdgeNode *)malloc(sizeof(EdgeNode));
⑧ ;
⑨ ;
⑩ ;
}
}
}
Answers:
① amat->vertexCount ② amat->edgeCount ③ amat->vertices[i] ④ alist->adjList[i].firstEdge = NULL
⑤ e1->adjVertex = j ⑥ e1->next = alist->adjList[i].firstEdge ⑦ alist->adjList[i].firstEdge = e1
⑧ e2->adjVertex = i ⑨ e2->next = alist->adjList[j].firstEdge ⑩ alist->adjList[j].firstEdge = e2