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 fieldds 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 complete 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 then 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

1. Worst‑case time complexity of the referenced algorithm: O(nⁿ)
2. First element of a sequential list is at address 0x11ff7c. Each element is 4 bytes. Address of the 5th element: 0x11ff8c
3. In a singly linked list, logically adjacent elements are not necessarily adjacent in memory.
4. Accessing the i‑th element in a singly linked list takes time O(n).
5. 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.
6. When implementing a queue with a singly linked list, the front of the queue is at the head of the list.
7. 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).
8. 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.
9. Target T = "abccdcdccbaa", pattern P = … The 5th match succeeds.
10. For a tree of degree 3 with 50 nodes, its minimum height is 5.
11. Postorder: DABEC, Inorder: DEBAC. Preorder is CEDBA.
12. A Huffman tree contains 215 nodes. The number of distinct codewords it can produce is 108.
13. In the adjacency matrix of a directed graph with n vertices and e edges, the number of zero entries is n² – e.
14. The maximum number of directed edges in a graph with n vertices is n(n‑1).
15. 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 exact 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.

Iteration	U (selected set)	D[0] … D[10]	p[0] … p[10]
Init	{3}	1 25 M 0 M M 13 M 9 M 3	3 3 0 3 0 0 3 0 3 0 3
1	{3,0}	1 25 7 0 7 18 13 M 9 M 3	3 3 0 3 0 0 3 0 3 0 3
2	{3,0,10}	1 18 7 0 7 5 13 M 9 M 3	3 10 0 3 0 10 3 0 3 0 3
3	{3,0,10,5}	1 17 6 0 7 5 13 15 9 M 3	3 5 5 3 0 10 3 5 3 0 3
4	{3,0,10,5,2}	1 17 6 0 7 5 13 12 9 M 3	3 5 5 3 0 10 3 2 3 0 3
5	{3,0,10,5,2,4}	1 17 6 0 7 5 11 10 8 22 3	3 5 5 3 0 10 4 4 4 4 3
6	{3,0,10,5,2,4,8}	1 17 6 0 7 5 11 10 8 22 3	3 5 5 3 0 10 4 4 4 4 3
7	{3,0,10,5,2,4,8,7}	1 17 6 0 7 5 11 10 8 17 3	3 5 5 3 0 10 4 4 4 7 3
8	{3,0,10,5,2,4,8,7,6}	1 16 6 0 7 5 11 10 8 15 3	3 6 5 3 0 10 4 4 4 6 3
9	{3,0,10,5,2,4,8,7,6,9}	1 16 6 0 7 5 11 10 8 15 3	3 6 5 3 0 10 4 4 4 6 3
10	{3,0,10,5,2,4,8,7,6,9,1}	1 16 6 0 7 5 11 10 8 15 3	3 6 5 3 0 10 4 4 4 6 3

(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):

Address	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Key	14	01	68	27	55	19	20	84	79	23	11	10
Probes (success)	1	2	1	4	3	1	1	3	9	1	1	3

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

Sequence: {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