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

1. 第 1 題選擇

   (4%) Let $n$ an $m$ be the sizes of two sets, assume $n < m$, if the sets are implemented using sorted lists, what is the time complexity to find the intersection of the two sets?

   • (A)
     $O(n+m)$
   • (B)
     $O(n \times m)$
   • (C)
     $O(n\log m)$
   • (D)
     $O(m\log n)$
   • (E)
     $O(\log n \times \log m)$
2. 第 2 題選擇

   (4%) Consider again the above question, what if the sets are implemented using AVL trees, instead of sorted lists?

   • (A)
     $O(n+m)$
   • (B)
     $O(n \times m)$
   • (C)
     $O(n\log m)$
   • (D)
     $O(m\log n)$
   • (E)
     $O(\log n \times \log m)$
3. 第 3 題選擇

   (4%) If an array is used to implement a binary search tree with $n$ nodes, where index 1 (the first position) of the array stores the root, what is the maximal index $i$ that stores the smallest key in the tree?

   • (A)
     1
   • (B)
     $n$
   • (C)
     $\lceil \log n \rceil$
   • (D)
     $2^{n-1}$
   • (E)
     $2^n+1$
4. 第 4 題選擇

   (4%) Which of the following statement concerning hashing is false?

   • (A)
     While hash function is designed based on arithmetic operation, hashing is also suitable for strings.
   • (B)
     If there is no collision, the worst time complexity for searching an element in a hash table is $O(1)$.
   • (C)
     A good hash function should produce the same hash value for similar keys.
   • (D)
     Hashing is typically used for symbol tables in compilers.
   • (E)
     The size of the hash table should ideally be a prime number to reduce the likelihood of collisions.
5. 第 5 題選擇

   (4%) Given a logical expression represented as an expression tree, along with the Boolean values assigned to the operands, which algorithm is best suited to evaluate the logical expression?

   • (A)
     Pre-order Traversal
   • (B)
     In-order Traversal
   • (C)
     Post-order Traversal
   • (D)
     Breadth-First Search
   • (E)
     Depth-First Search
6. 第 6 題選擇

   (4%) Given the following algorithm, which is likely to be the result if the input variable N is -1?

   Boolean Magic (int N)
   {   if (N==1)
         Return True
       else if (N==0)
         Return False
       else { N = N-2;
         Return Magic(N);
       };
   }
   

   • (A)
     -3
   • (B)
     True
   • (C)
     False
   • (D)
     Stack Overflow
   • (E)
     Syntax Error
7. 第 7 題選擇

   (4%) Which sorting algorithm will produce the following results of pass 0, 1 and 2 for 33, 7, 63, 50, 31, 20?

   Pass 0: 7, 33, 63, 50, 31, 20
   Pass 1: 7, 20, 63, 50, 31, 33
   Pass 2: 7, 20, 31, 50, 63, 33
   

   • (A)
     Insertion Sort
   • (B)
     Selection Sort
   • (C)
     Bubble Sort
   • (D)
     Merge Sort
   • (E)
     Quick Sort
8. 第 8 題選擇

   (4%) If an array is used to implement a max-heap, where index 1 (the first position) of the array stores the root, what is the maximal index $i$ that stores the 3rd ranked element?

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

   (4%) Given an undirected connected graph $G$ of $n$ vertices and $m$ edges, which of the following statement concerning spanning trees is false?

   • (A)
     The minimum spanning tree should not include the heaviest edge in any cycle of $G$.
   • (B)
     The maximum spanning tree can be found by modifying Kruskal's algorithm to sort edges in descending order by weight.
   • (C)
     Each spanning tree contains exactly $n-1$ edges.
   • (D)
     Both Prim's and Kruskal's algorithms are greedy algorithms.
   • (E)
     Heap is commonly used to implement Kruskal's Algorithm for finding minimum spanning tree efficiently.
10. 第 10 題選擇

    (4%) Given an undirected graph of $n$ vertices, $m$ edges and $p$ connected components, what is the minimum number of edges required to make this graph connected?

    • (A)
      $n-p+1$
    • (B)
      $p-1$
    • (C)
      $n-1$
    • (D)
      $p$
    • (E)
      $n$
11. 第 11 題選擇

    (4%) Which of the following statements concerning topological ordering is true?

    • (A)
      It is impossible to give the topological ordering for a direct cyclic graph.
    • (B)
      The shortest paths from a single source in a weighted DAG can be found using an $O(V+E)$-time greedy algorithm based on topological ordering, where $V$ is the number of vertices and $E$ is the number of edges.
    • (C)
      In a DAG, if there is a path from vertex $u$ to vertex $v$, then $v$ appears after $u$ in topological ordering.
    • (D)
      The longest paths from a single source in a weighted DAG can be found using an $O(V+E)$-time greedy algorithm based on topological ordering, where $V$ is the number of vertices and $E$ is the number of edges.
    • (E)
      All of the above.
12. 第 12 題選擇

    (4%) Which of the following statements concerning time complexity is false?

    • (A)
      The time complexity of rotation operation of an AVL tree of size $n$ is $O(\log n)$.
    • (B)
      The worst-case time complexity of merge sort is $O(n\log n)$.
    • (C)
      The time complexity of KMP algorithm to search for a pattern of length $m$ in a text of length $n$ is $O(n+m)$.
    • (D)
      The time complexity of the dynamic programming approach to find the longest common subsequence between two sequences of length $n$ and $m$ is $O(n \times m)$.
13. 第 13 題選擇

    (4%) Which of the following statements concerning reduction is false?

    • (A)
      The bipartite graph matching problem can be reduced to the network flow problem.
    • (B)
      If a problem X is polynomial reducible to a problem Y, then the lower bound of X can be applied to Y.
    • (C)
      A problem X is NP-Complete if X is polynomial reducible to some NP-Complete problem Y.
    • (D)
      A problem X is an NP-hard problem if every problem in NP is polynomial reducible to X.
14. 第 14 題選擇

    (4%) Which of the following statements is false?

    • (A)
      Every problem which can be solved in polynomial time by deterministic algorithms must be a NP problem.
    • (B)
      A problem is NP-hard if it is as least as hard as all NP problems.
    • (C)
      If any NP-Complete problem can be solved in polynomial time, then all NP-hard problems can be solved in polynomial time.
    • (D)
      Every NP-Complete problem must be NP.
15. 第 15 題選擇

    (4%) Which of the following problems is NP-Hard?

    • (A)
      Given an undirected graph, find the maximum number of vertices that form a complete subgraph.
    • (B)
      Given a directed network, find the maximum flow from the source to the sink.
    • (C)
      Given a bipartite graph, find the maximum number of matching pairs.
    • (D)
      Given two sequences, find the common subsequence of maximal length.
16. 第 16 題計算

    Six Degrees of Separation is the theory that any person on the planet can be connected to any other person on the planet through a chain of acquaintances that has no more than five intermediaries on average. For example, in the social network graph below (Figure 1), the degree of separation between Gia and Felix is five. They can be connected by at least four intermediaries. The average degree of separation in this social network is about 2.1. Given a dense social network of $n$ persons, design a dynamic programming algorithm to compute the average degree of separation in this social network.

    Figure 1 (undirected social network graph): vertices $\{\text{Adam, Bill, Clara, Diana, Eva, Felix, Gia}\}$ with edges $\{(\text{Adam,Bill}), (\text{Adam,Clara}), (\text{Adam,Diana}), (\text{Bill,Diana}), (\text{Bill,Eva}), (\text{Diana,Eva}), (\text{Clara,Felix}), (\text{Eva,Gia})\}$.

    (1) (10%) Give the algorithm in pseudo code clearly.

    (2) (5%) Give the recurrence relation.

    (3) (5%) Analyze the time complexity of your algorithm.

17. 第 17 題計算

    Please design an $O(\log n)$ algorithm to search for the $k$-th element in an AVL tree of $n$ elements, while the time complexity of insertion operation remains $O(\log n)$.

    (1) (5%) How to modify the data structure of an AVL tree to support this search operation?

    (2) (10%) Give the $O(\log n)$ algorithm to search for the k-element.

    (3) (5%) How to modify the insertion operation to accommodate for the modification of the data structure.

    (Please illustrate your answer by using the AVL-tree provided in Figure 2.)

    Figure 2 (AVL tree): root $54$; left child $23$, right child $79$; $23$'s children are $11$ (left) and $45$ (right); $79$'s children are $66$ (left) and $88$ (right); $45$'s left child is $36$.