整卷連續作答，作答時答案與解析隱藏；按「交卷」後揭曉正解、標準解析並自動批改（申論／計算題不計分，供自行對照）。

1. 第 1 題選擇

   (5 points) Assuming we have $n$ data points. Among the variant characteristics of the data points, please select the correct descriptions.

   • (A)
     If the worst-case running time is the most important, merge sort can be a good choice with $O(n \log n)$ time.
   • (B)
     If the input happens to be sorted already, bubble sort can be a best choice with $O(n)$ time.
   • (C)
     If the input array is in random order and the average sorting time is most important, quick sort can be a good choice with $O(n \log n)$ time.
   • (D)
     If the exchanges of the items in the array are very expensive, selection sort will incur the least "swaps" or "moves".
   • (E)
     If the input array consists of integers in the range $1 \dots n^k$, radix sort with radix $n$ with $O(k \log n)$ time.
2. 第 2 題選擇

   (5 points) B+ tree is an extension of B tree. The major differences from B tree are (1) all leaf nodes are linked together in a doubly-linked list, and (2) data points are stored on the leaf nodes only; internal nodes only hold keys and act as routers to the correct leaf node; the left child is smaller than the key and the right child is larger or equal than that. Please find any/all violations of a B+ tree structure in the following diagram. Assume the tree node can at most contain 4 data points (keys).

   樹結構（由根往下；括號為標記候選）：

   • 根：20
     • 左子（標記 (A)）：10
       • 6,8 → 葉 1,2,3 / 6,7 / 8,9
       • （標記 (B)）13,20 → 葉 10,11 / 13,14 / （標記 (C)）20,21
     • 右子：30,40
       • 22,27 → 葉 （標記 (D)）22,23 / 24,25 / 27,28
       • 33,36 → 葉 （標記 (E)）30,31 / 33,34 / 36,37
       • 47,52 → 葉 40,43 / 47,49 / 52,55
   • (A)
     節點 10
   • (B)
     節點 13,20
   • (C)
     葉 20,21
   • (D)
     葉 22,23
   • (E)
     葉 30,31
3. 第 3 題選擇

   (5 points) Please find the following table for the characters and their corresponding occurring probabilities. Please design a Huffman encoding tree and select the correct descriptions.

   Symbol ($X$)	A	B	C	D	E	F	G
   Prob ($X$)	0.15	0.06	0.24	0.21	0.09	0.21	0.03

   • (A)
     The codeword length for symbol C is 3
   • (B)
     The codeword length for symbol G is 5
   • (C)
     The codeword length for symbol E is 5
   • (D)
     The codeword length for symbol A is 4
   • (E)
     none of above is correct
4. 第 4 題選擇

   (5 points)（單選）We now use several algorithms to traverse a binary tree. Assuming there are a total number of $N$ nodes, how many of the following statements about the worst-case space complexity are TRUE?

   • Using DFS to traverse a balanced binary tree takes $O(N)$.
   • Using DFS to traverse a binary tree takes $O(N)$.
   • Using BFS to traverse a balanced binary tree takes $O(N)$.
   • Using BFS to traverse a binary tree takes $O(N)$.
   • (A)
     0
   • (B)
     1
   • (C)
     2
   • (D)
     3
   • (E)
     4
5. 第 5 題選擇

   (5 points)（單選）In a traditional merge sort, two sorted sub-arrays are combined to form a single, fully sorted array. This is referred to as a 2-way merge. The problem at hand is to extend this concept by merging $N$ sorted arrays of integers, where $N$ and $M$ are given integers representing the number of arrays and the number of integers in each array, respectively. Please choose the correct worst-case time complexity of this $N$-way merge.

   • (A)
     $O(N \log M)$
   • (B)
     $O(NM \log M)$
   • (C)
     $O(N^2 \log M)$
   • (D)
     $O(NM \log N)$
   • (E)
     none of the above is correct.
6. 第 6 題選擇

   (5 points) The following is a binary tree and the alphabet on the node is simply the "name" (instead of value) of the node. Please select the correct statements from the following:

   樹結構（節點以名稱標示）：

   • A：左子 B、右子 C
   • B：左子 D、右子 E
   • C：左子 F、右子 G
   • D：右子 H
   • E：右子 I
   • F：左子 J
   • G：左子 K、右子 L
   • L：右子 M
   • (A)
     The successor of node B is E.
   • (B)
     The successor of node A is C.
   • (C)
     The tree is not a AVL tree.
   • (D)
     If we remove node J, the result is an AVL tree.
   • (E)
     If we remove node H, the result is an AVL tree.
7. 第 7 題選擇

   (5 points)（單選）Given a list of binary trees $T = \{t_1, t_2, \dots, t_7\}$ where each node is 0 or 1 shown as below, we would like to insert these trees into a linear-probing hash table of length $N = 11$. The hash function $f(t) = g(h(t)) \bmod N$, where $h(t)$ is the binary sequence obtained from in-order traversal of tree $t$ and $g(\cdot)$ converts a binary sequence to a decimal number. For instance, $g(\text{"1111111"}) = 127$. Here's the question: how many collisions occur during the insertion process?

   七棵樹皆為 7 節點完全二元樹（根；左子 cL、右子 cR；cL 的左右葉 a,b；cR 的左右葉 c,d），中序序列為 [a, cL, b, root, c, cR, d]：

   • $t_1$：root=0, cL=0, cR=1, a=0,b=1,c=1,d=0
   • $t_2$：root=0, cL=0, cR=0, a=0,b=0,c=1,d=0
   • $t_3$：root=1, cL=0, cR=1, a=0,b=0,c=1,d=1
   • $t_4$：root=1, cL=0, cR=0, a=0,b=1,c=1,d=0
   • $t_5$：root=0, cL=0, cR=0, a=0,b=1,c=0,d=1
   • $t_6$：root=1, cL=0, cR=0, a=1,b=1,c=0,d=0
   • $t_7$：root=1, cL=1, cR=0, a=0,b=1,c=1,d=0
   • (A)
     0
   • (B)
     1
   • (C)
     2
   • (D)
     3
   • (E)
     4
8. 第 8 題選擇

   (5 points) Postfix advantages: What is/are the advantage(s) of using postfix notation for math expressions?

   • (A)
     No need to use parentheses
   • (B)
     No need to consider precedence of operators
   • (C)
     Easier for human to read
   • (D)
     Easier for computers to evaluate
   • (E)
     More concise when compared with prefix notation
9. 第 9 題選擇

   (5 points) DFS advantages: To find a feasible solution to the eight-queen problem, what is/are the reason(s) that we prefer to use DFS (depth-first search) instead of BFS (breadth-first search)?

   • (A)
     DFS is more memory efficient.
   • (B)
     DFS can be implemented using a stack.
   • (C)
     DFS usually reaches the terminal states of "good" or "bad" faster.
   • (D)
     DFS is conceptually simpler than BFS.
   • (E)
     BFS cannot be implemented using a stack.
10. 第 10 題選擇

    (5 points) Heap applications: Which one(s) of the following applications may involve the use of heaps to increase time efficiency?

    • (A)
      Find the k largest numbers from a given stream of numbers.
    • (B)
      Given a stream of numbers coming one after another, calculate the median of the currently received set of numbers.
    • (C)
      Compute the page rank of a given set of web pages
    • (D)
      Detect appropriate "buy" and "sell" requests to create transactions in stock market
    • (E)
      Identify the next timing for collisions in event-driven simulation for molecular dynamics
11. 第 11 題選擇

    (5 points) Properties of dynamic programming (DP): Which of the following statements is/are correct about DP?

    • (A)
      Any DP problem can be visualized as the optimal path finding problem.
    • (B)
      Once a DP problem is solved, all the related sub-problems are also solved.
    • (C)
      Once a DP problem is solved, it is straightforward to obtain the second-best solution.
    • (D)
      The optimal solution of a DP problem can be obtained using optimal solutions of its sub-problems.
    • (E)
      A DP problem has overlapping sub-problems which are reused several times when solving the original problem.
12. 第 12 題選擇

    (5 points) Properties of shortest path problem: Which of the following statements is/are correct?

    • (A)
      Dijkstra's algorithm can be applied to any directed graph with no negative cycle.
    • (B)
      The heap data structure is likely to be used in Dijkstra's algorithm.
    • (C)
      Floyd-Warshall algorithm can be applied to any directed graph with negative weights.
    • (D)
      Floyd-Warshall algorithm is based on the concept of dynamic programming.
    • (E)
      Every shortest path in a weighted directed graph $G$ will not change if an extra weight is added on every edge of $G$.
13. 第 13 題選擇

    (5 points) Properties of min. spanning tree (MST): Let $T$ be a MST of a weighted graph $G$ with at least 3 vertices. Which of the following statements is/are correct?

    • (A)
      Given an edge $e$ in $G$ but not in $T$, we can form a cycle by putting $e$ to $T$. Then $e$ has the largest weight among edges in $C$ (the cycle).
    • (B)
      If we partition $G$ into two subsets, and let $e$ be the smallest-weight edge across the partition. Then $e$ belongs to some MST in $G$.
    • (C)
      The edge with the smallest weight in $G$ must belong to some MST of $G$.
    • (D)
      The edge with the second smallest weight in $G$ must belong to some MST of $G$.
    • (E)
      The edge with the third smallest weight in $G$ must belong to some MST of $G$.
14. 第 14 題選擇

    (5 points) Prefix, infix, and postfix: Which of the following statements is/are correct?

    • (A)
      We can use a stack to convert an infix to postfix expression.
    • (B)
      We can use a stack to convert a postfix to an infix expression.
    • (C)
      We can derive a binary tree from its infix and prefix notations.
    • (D)
      We can derive a binary tree from its infix and postfix notations.
    • (E)
      We can derive a binary tree from its prefix and postfix notations.
15. 第 15 題申論

    (21 points) Given $k$ singly linked lists, each of which has $n$ nodes. The numbers in the nodes of the $i$-th list are given by $a_{i,1}, a_{i,2}, \dots, a_{i,n}$. Each of the $k$ lists has the numbers sorted in non-decreasing order, i.e., $a_{i,1} \le a_{i,2} \le \dots \le a_{i,n}$. Professor Q asks the students to develop an algorithm to merge these $k$ lists into one singly linked list sorted in non-decreasing order. Three students have come up with different algorithms. For each of these three algorithms, analyze and give their asymptotic worst-case running times with big-O notation and in terms of $k$ and $n$ (tight bound; drop lower-order terms and constant factors other than $k$ and $n$).

    • Student A: Repeatedly iterate over the numbers in the head nodes of the $k$ lists, find the node $M$ with the smallest number, remove $M$ from its original list and append it to the tail of result list $S$; until all $k$ lists are empty.
    • Student B: Create an empty min heap $H$. Remove the $k$ head nodes and insert them into $H$ (each node also carries the index of its source list). Repeatedly remove the min node $M$ from $H$, append it to $S$, and (if its source list $m$ is not empty) remove the head of list $m$ and insert into $H$; while $H$ is not empty.
    • Student C: Recursive divide-and-conquer MergeTwoGroupLists: if only one list, return it; otherwise split the $m$ input lists into two groups of $\lceil m/2 \rceil$ and $\lfloor m/2 \rfloor$ lists, recursively merge each group into one sorted list $S_1, S_2$, then merge the two sorted lists $S_1, S_2$ into one.
16. 第 16 題申論

    (9 points) The pseudo code function to compute the prefix function in the Knuth-Morris-Pratt (KMP) string matching algorithm is given below. Given a pattern string $P[1..m]$, the prefix function is $\pi:\{1,2,\dots,m\}\to\{0,1,\dots,m-1\}$ such that $\pi[q]$ is the length of the longest prefix of $P$ that is a proper suffix of $P_q$ (the $q$-character prefix of $P$). For pattern string $P=$ABACABACABACABAD, how many times is line 7 executed?

    COMPUTE-PREFIX-FUNCTION(P)
    1   m = P.length
    2   let π[1..m] be a new array
    3   π[1] = 0
    4   k = 0
    5   for q = 2 to m
    6       while k > 0 and P[k+1] ≠ P[q]
    7           k = π[k]
    8       if P[k+1] == P[q]
    9           k = k + 1
    10      π[q] = k
    11  return π