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

1. 第 1 題選擇

   (5 points) When CAN the worst case of Quicksort occur?

   • $C_1$: Quick Sort where leftmost (or rightmost) element is always chosen as pivot
   • $C_2$: leftmost element is chosen as pivot and array is already sorted in SAME order
   • $C_3$: leftmost element is chosen as pivot and array is already sorted in REVERSE order
   • (A)
     $C_1$
   • (B)
     $C_2$
   • (C)
     $C_1$ and $C_2$
   • (D)
     $C_2$ and $C_3$
2. 第 2 題選擇

   (5 points) A typical dynamic programming example is the snake sequence. Given a grid of numbers, find the maximum length snake sequence. A snake sequence is made up of adjacent numbers in the grid such that for each number, the number on the right or the number below it is $+1$ or $-1$ its value. At location $(x, y)$, you can move right $(x+1, y)$ or move down $(x, y+1)$ if that number is $\pm 1$. The length of a snake sequence is defined as the number of moves. Given the following grid ($M$ rows, $N$ columns; rows top-to-bottom):

   9, 6, 5, 2
   8, 7, 6, 5
   7, 3, 1, 6
   1, 1, 1, 7
   

   The maximum LENGTH of snake sequence is?

   • (A)
     6
   • (B)
     7
   • (C)
     5
   • (D)
     4
3. 第 3 題選擇

   (5 points) 承上題（snake sequence，網格為 $M$ 列 $N$ 行）。Time complexity of the above solution is?

   • (A)
     $O(M \times N)$
   • (B)
     $O(M^2)$
   • (C)
     $O(N^2)$
   • (D)
     $O(M)$
4. 第 4 題選擇

   (5 points) 承 snake sequence 題（網格如下，格座標依題目 $(x,y)$ 定義：$x$ 為行方向索引、$y$ 為列方向索引，均由 0 起算）：

   9, 6, 5, 2
   8, 7, 6, 5
   7, 3, 1, 6
   1, 1, 1, 7
   

   The last number of the maximum-length snake sequence is?

   • (A)
     9(0,0)
   • (B)
     6(3,2)
   • (C)
     7(3,3)
   • (D)
     1(2,3)
   • (E)
     7(0,2)
5. 第 5 題選擇

   (5 points) 承 snake sequence 題（網格如下，格座標依題目 $(x,y)$ 定義，均由 0 起算）：

   9, 6, 5, 2
   8, 7, 6, 5
   7, 3, 1, 6
   1, 1, 1, 7
   

   The third number of the maximum-length snake sequence is?

   • (A)
     7(1,1)
   • (B)
     7(0,2)
   • (C)
     3(1,2)
   • (D)
     6(2,1)
   • (E)
     8(0,1)
6. 第 6 題選擇

   (5 points) For questions with sequences, we constantly split the problem into a number of sub-problems that are smaller instances of the same problem, and we try to solve the smaller problems recursively. We called this type of algorithm?

   • (A)
     Dynamic programming
   • (B)
     Divide and conquer
   • (C)
     Greedy algorithms
   • (D)
     Quicksort
7. 第 7 題選擇

   (5 points) There is a large enough array $A$ with indices $p$ and $q$ which are initialized by 0, and functions $f(x)$ and $g()$ are defined as follows. Array $A$ and indices $p$ and $q$ can only be accessed in the functions $f(x)$ and $g()$.

   f(x):
       p ← p + 1
       A[p] ← x
   
   g():
       x ← A[p]
       p ← p - 1
       return x
   

   Which data structure is operated by those functions?

   • (A)
     Queue
   • (B)
     Stack
   • (C)
     Hash
   • (D)
     Heap
8. 第 8 題選擇

   (5 points) 承上題（陣列 $A$ 與索引 $p, q$ 初值皆 0，僅能由 $f, g$ 存取）。If functions $f(x)$ and $g()$ are changed as following:

   f(x):
       A[q] ← x
       q ← q + 1
   
   g():
       x ← A[p]
       p ← p + 1
       return x
   

   Which data structure is operated by those functions?

   • (A)
     Queue
   • (B)
     Stack
   • (C)
     Hash
   • (D)
     Heap
9. 第 9 題選擇

   (5 points) There is a binary tree stored in an array as:

   $T[] = \{+, a, *, null, null, -, d, null, null, null, null, b, c\},$

   in which $T[i]$ is the parent of $T[2i+1]$ and $T[2i+2]$, where $i$ is an index and $null$ means there is no element in the slot. What is its postorder traversal result?

   • (A)
     $+a*-dbc$
   • (B)
     $a+b-c*d$
   • (C)
     $abc-d*+$
   • (D)
     $+a*-bcd$
10. 第 10 題選擇

    (5 points) 承上題（$T[] = \{+, a, *, null, null, -, d, null, null, null, null, b, c\}$，$T[i]$ 為 $T[2i+1], T[2i+2]$ 之父）。What is its BFS traversal result?

    • (A)
      $+a*-dbc$
    • (B)
      $a+b-c*d$
    • (C)
      $abc-d*+$
    • (D)
      $+a*-bcd$
11. 第 11 題選擇

    (5 points) There are 10 hexadecimal data, 53, 3B, 66, 43, 60, 5B, 7C, 14, 30, 37, inserted in the given order into an empty hash table. The table is implemented using a circular array of 10 slots, and one slot can only have one item. The hash function for the table is $h(k) = k \bmod 9$. Which data is the first one that occurs a collision?

    • (A)
      43
    • (B)
      5B
    • (C)
      14
    • (D)
      37
12. 第 12 題選擇

    (5 points) 承上題（資料 53, 3B, 66, 43, 60, 5B, 7C, 14, 30, 37 依序插入、10 槽環形陣列、$h(k)=k \bmod 9$）。If the hash table uses linear probing to resolve collisions and has no resizing mechanism, which position in the array is 37 inserted?

    • (A)
      3
    • (B)
      8
    • (C)
      4
    • (D)
      0
13. 第 13 題選擇

    (5 points) There is a linked-list with $n$ elements $x_1, x_2, \dots, x_n$. Let $f(n)$ be the time complexity of inserting a new element $x_{n+1}$ to the tail of the list, and $g(n)$ be that of deleting the last element $x_n$. If there is only one pointer pointed to the head of the list, the functions are denoted $f_1(n), g_1(n)$. To improve it, we may also add another pointer pointed to the tail, so the functions become $f_2(n), g_2(n)$. Which of the following option is false if $n$ becomes large?

    • (A)
      $\dfrac{f_1(n)}{g_1(n)} = 1$
    • (B)
      $\dfrac{f_2(n)}{g_2(n)} = n$
    • (C)
      $\dfrac{f_1(n)}{f_2(n)} = n$
    • (D)
      $\dfrac{g_1(n)}{g_2(n)} = 1$
14. 第 14 題選擇

    (5 points) Given the following weighted graph, find its minimum spanning tree. Edges (undirected, weight):

    F-B:1  H-C:2  B-C:3  I-H:4  F-I:5  B-A:6  A-E:7  E-C:8  D-E:9  F-D:10
    D-B:11 D-A:12 A-C:13 E-H:14 G-E:15 D-G:16 F-G:17 I-G:18 G-H:19
    

    What is the sixth edge that Kruskal's algorithm includes (the numbering of the inclusion order starts from 1, not 0)?

    • (A)
      6
    • (B)
      7
    • (C)
      8
    • (D)
      9
15. 第 15 題選擇

    (5 points) 承上題的加權圖（邊如下）：

    F-B:1  H-C:2  B-C:3  I-H:4  F-I:5  B-A:6  A-E:7  E-C:8  D-E:9  F-D:10
    D-B:11 D-A:12 A-C:13 E-H:14 G-E:15 D-G:16 F-G:17 I-G:18 G-H:19
    

    What is the sixth vertex that Prim's algorithm includes if starting from vertex A (the numbering of the inclusion order starts from 1, not 0)?

    • (A)
      C
    • (B)
      E
    • (C)
      H
    • (D)
      I
16. 第 16 題選擇

    (5 points) What is the value of the maximum flow for the following $st$-flow network? Directed edges (capacity):

    s→A:10  s→C:10  A→B:4  A→C:2  A→D:8  C→D:9  D→B:6  B→t:10  D→t:10
    

    • (A)
      16
    • (B)
      17
    • (C)
      18
    • (D)
      19
17. 第 17 題選擇

    (5 points) The Knuth-Morris-Pratt (KMP) algorithm is a string-matching algorithm. Its core is the prefix function. Given a pattern $P[1..m]$, the prefix function is $\pi:\{1,2,\dots,m\}\to\{0,1,\dots,m-1\}$. What is $\pi[7]$ for the following pattern $P$?

    $i$	1	2	3	4	5	6	7	8	9	10
    $P[i]$	a	b	a	b	a	b	a	b	c	a

    • (A)
      4
    • (B)
      5
    • (C)
      6
    • (D)
      7
18. 第 18 題選擇

    (5 points) Many string-matching algorithms build a finite automata. Below is a partially-completed state transition function $\delta$ for a string $s$ of length 10 over the alphabet $\{A, B, C\}$ (columns are states $0\dots9$; a blank means unspecified). It is possible to reconstruct $s$ from the partial table. How many A's does the string $s$ have?

    $\delta$	0	1	2	3	4	5	6	7	8	9
    A				4	5		2
    B				0	0		7			3
    C				0	0		0			10

    • (A)
      4
    • (B)
      5
    • (C)
      6
    • (D)
      7
19. 第 19 題選擇

    (5 points) What can you infer from the facts that ProblemA is NP-complete and ProblemA linear-time reduces to ProblemB?

    • $C_1$: If there exists an $O(N^3)$ algorithm for ProblemB, then $P = NP$.
    • $C_2$: If there does not exist an $O(N^3)$ algorithm for ProblemB, then $P \ne NP$.
    • $C_3$: If there exists an $O(N^3)$ algorithm for ProblemB, then there exists an $O(N^3)$ algorithm for ProblemA.
    • $C_4$: If there exists an $O(N^3)$ algorithm for ProblemA, then there exists an $O(N^3)$ algorithm for ProblemB.
    • (A)
      $C_1$ and $C_3$
    • (B)
      $C_1$ and $C_4$
    • (C)
      $C_2$ and $C_3$
    • (D)
      $C_2$ and $C_4$
20. 第 20 題選擇

    (5 points) The VERTEX-COVER problem is polynomial-time reducible to the SUBSET-SUM problem. Given an instance $\langle G, k\rangle$ of VERTEX-COVER, one can construct a corresponding instance $\langle S, t\rangle$ of SUBSET-SUM. The given graph $G$ has 5 edges $e_0,\dots,e_4$; with $k=3$, $\{v_1, v_3, v_4\}$ is a vertex cover of size 3. The set $S = \{1, 4, 16, 64, 256, 1040, 1041, 1093, 1284, 1344\}$ is constructed (a modified base-4 encoding: one leading digit plus edge digits $e_4 e_3 e_2 e_1 e_0$):

            e4 e3 e2 e1 e0   decimal
    x0 = 1   0  0  1  0  1  = 1041
    x1 = 1   1  0  0  1  0  = 1284
    x2 = 1   1  1  0  0  0  = 1344
    x3 = 1   0  0  1  0  0  = 1040
    x4 = 1   0  1  0  1  1  = 1093
    y0 = 0   0  0  0  0  1  = 1
    y1 = 0   0  0  0  1  0  = 4
    y2 = 0   0  0  1  0  0  = 16
    y3 = 0   0  1  0  0  0  = 64
    y4 = 0   1  0  0  0  0  = 256
    

    What is the target $t$?

    • (A)
      2389
    • (B)
      3417
    • (C)
      3754
    • (D)
      3758