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

1. 第 1 題選擇

   (3 points) Which of the following sorting algorithms is considered a non-comparison-based sort?

   • (A)
     Heap Sort
   • (B)
     Quick Sort
   • (C)
     Counting Sort
   • (D)
     Merge Sort
2. 第 2 題選擇

   (3 points) Which of the following sorting algorithms has the best worst-case time complexity?

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

   (3 points) You are designing a program to compute the maximum achievable value from a limited set of resources with constraints. Which of the following techniques would you use to solve this problem most efficiently?

   • (A)
     Greedy approach
   • (B)
     Graph traversal algorithms
   • (C)
     Divide and conquer
   • (D)
     Dynamic programming
4. 第 4 題選擇

   (3 points) Given a weighted directed graph with potential negative edge weights, which of the following algorithms would you use to compute the shortest path from a single source to all other vertices?

   • (A)
     Bellman-Ford Algorithm
   • (B)
     Kruskal's Algorithm
   • (C)
     Dijkstra's Algorithm
   • (D)
     Prim's Algorithm
5. 第 5 題選擇

   (3 points) Consider the following statements about NP-complete problems:

   1. Every NP-complete problem is also in NP.
   2. If an NP-hard problem is in NP, it is NP-complete.
   3. All NP problems can be reduced to an NP-complete problem in polynomial time.
   4. The Halting Problem is an NP-complete problem.

   Which of the above statements are true?

   • (A)
     1 and 3 only
   • (B)
     1, 2, and 3 only
   • (C)
     2, 3, and 4 only
   • (D)
     All of the above
6. 第 6 題選擇

   (3 points) Given the text $T =$ "abcdefg" and the pattern $P =$ "bcd", which algorithm would use hashing to compute the index of the first match efficiently?

   • (A)
     Knuth-Morris-Pratt Algorithm
   • (B)
     Boyer-Moore Algorithm
   • (C)
     Naive String Matching Algorithm
   • (D)
     Rabin-Karp Algorithm
7. 第 7 題選擇

   (3 points) What is the result of sorting the array $[38, 27, 43, 3, 9, 82, 10]$ in ascending order using Merge Sort?

   • (A)
     $[3, 9, 10, 27, 38, 43, 82]$
   • (B)
     $[3, 10, 9, 27, 38, 82, 43]$
   • (C)
     $[3, 9, 10, 27, 43, 38, 82]$
   • (D)
     $[27, 38, 43, 3, 9, 10, 82]$
8. 第 8 題選擇

   (3 points) Consider the following array of positive integers representing the value of items: values $= [10, 4, 3, 7, 6]$, and their corresponding weights: weights $= [5, 2, 1, 3, 4]$. You are given a knapsack with a maximum capacity of 9 units. Using dynamic programming, calculate the maximum total value you can achieve by selecting items such that their total weight does not exceed the capacity.

   • (A)
     19
   • (B)
     20
   • (C)
     21
   • (D)
     23
9. 第 9 題選擇

   (3 points) Which of the following best describes how Depth-First Search (DFS) detects a cycle in a directed graph?

   • (A)
     By checking if any vertex is visited more than once during traversal.
   • (B)
     By identifying back edges that point to an ancestor in the recursion stack.
   • (C)
     By verifying if any edge weight is negative during traversal.
   • (D)
     By counting the total number of strongly connected components.
10. 第 10 題選擇

    (3 points) Which of the following statements about topological sorting in a directed acyclic graph (DAG) is true?

    • (A)
      A DAG can have multiple valid topological orders.
    • (B)
      A strongly connected graph always has at least one topological order.
    • (C)
      Topological sorting guarantees a unique order in any DAG.
    • (D)
      A directed graph with a cycle can still have a valid topological order.
11. 第 11 題選擇

    (3 points) Which of the following operations typically takes $O(1)$ time in an array-based stack implementation?

    • (A)
      Pushing an element onto the stack
    • (B)
      Searching for a specific element in the stack
    • (C)
      Removing an element from the bottom of the stack
    • (D)
      Reversing the entire stack
12. 第 12 題選擇

    (3 points) In a linked list, what is the main advantage of using a doubly linked list over a singly linked list?

    • (A)
      It requires less memory per node
    • (B)
      It allows traversal in both forward and backward directions
    • (C)
      It makes searching for elements faster in the average case
    • (D)
      It eliminates the need for a tail pointer
13. 第 13 題選擇

    (3 points) If you have a binary search tree (BST) containing the numbers 1 through 100, which element's search time would be the shortest (assuming balanced distribution)?

    • (A)
      1
    • (B)
      50
    • (C)
      100
    • (D)
      75
14. 第 14 題選擇

    (3 points) Which of the following data structures is best suited for implementing the undo operation in a text editor?

    • (A)
      Stack
    • (B)
      Queue
    • (C)
      Binary Search Tree
    • (D)
      Hash Table
15. 第 15 題選擇

    (3 points) Consider a hash table implemented with open addressing (linear probing). If the load factor is close to 1, which of the following is most likely to occur?

    • (A)
      Decreased collision frequency
    • (B)
      Improved average search time
    • (C)
      Increased average number of probes per search
    • (D)
      No significant impact on performance
16. 第 16 題選擇

    (3 points) When inserting a key into a B-Tree node that is already full, which operation occurs first to maintain the B-Tree properties?

    • (A)
      Merge two nodes
    • (B)
      Split the full node into two nodes
    • (C)
      Rotate keys from a sibling node
    • (D)
      Remove keys to reduce the node size
17. 第 17 題選擇

    (3 points) What is the time complexity for insertion in a Red-Black Tree?

    • (A)
      $O(\log n)$
    • (B)
      $O(n)$
    • (C)
      $O(1)$
    • (D)
      $O(n \log n)$
18. 第 18 題選擇

    (3 points) After inserting a new node into a Red-Black Tree, which of the following operations might be performed to restore Red-Black properties?

    • (A)
      Rotations and recoloring of nodes
    • (B)
      Complete tree re-balancing from scratch
    • (C)
      Splitting and merging nodes, similar to B-Trees
    • (D)
      Directly moving the newly inserted node to the root
19. 第 19 題選擇

    (3 points) In an array-based circular queue, how do you check if the queue is full?

    • (A)
      By comparing the front and rear indices directly
    • (B)
      By checking if (rear + 1) % size == front
    • (C)
      By ensuring rear == front at all times
    • (D)
      By ensuring (front + 1) % size == rear
20. 第 20 題選擇

    (3 points) Which data structure is commonly used to implement breadth-first search (BFS) on graphs?

    • (A)
      Stack
    • (B)
      Queue
    • (C)
      Heap
    • (D)
      Hash Table
21. 第 21 題計算

    (5%) You are given the following set of activities, where each activity has a start time and an end time. Your task is to select the maximum number of non-overlapping activities that can be scheduled.

    Activity	Start Time	End Time
    A	1	3
    B	2	5
    C	4	6
    D	6	8
    E	5	7
    F	8	9

    Using a greedy algorithm, compute the maximum number of non-overlapping activities that can be selected.

22. 第 22 題計算

    (5%) Given the array $[9, 3, 7, 1, 6, 5, 8]$, perform two passes of the Bubble Sort algorithm in ascending order (smallest number comes first). What is the resulting array after these two passes?

23. 第 23 題計算

    (5%) You are given the sequence of integers 15, 10, 20, 8, 12, 17, 25, 19 to insert into an initially empty binary search tree (BST). After constructing the BST:

    I. Delete the node with value 20 and replace it with its in-order successor. II. Perform a post-order traversal of the updated BST.

    What is the resulting post-order traversal of the BST after the deletion?

24. 第 24 題計算

    (5%) Using Kruskal's algorithm, calculate the total cost of the minimum spanning tree (MST) for the graph shown.

    The graph has vertices $A, B, C, D, E$ with the following weighted edges: $A\text{-}B = 4$, $A\text{-}C = 2$, $B\text{-}C = 1$, $B\text{-}D = 3$, $C\text{-}D = 5$, $C\text{-}E = 6$, $D\text{-}E = 2$.

25. 第 25 題計算

    (10%) Consider a binary min-heap represented by the array $[1, 3, 2, 10, 7, 6, 9]$, where the element 1 is at the root. Suppose you need to insert a new element, 4, into this min-heap. Describe the complete insertion process step-by-step. Your answer should include:

    • Indicating where the new element is initially placed in the array.
    • Explaining the heapify-up (or bubble-up) process in detail, showing each intermediate state of the heap after any necessary swaps.
    • Presenting the final min-heap array once the insertion is complete.

    Make sure to clearly justify the steps taken and the reasoning behind each comparison and swap, based on the fundamental properties of a min-heap.

26. 第 26 題申論

    (10%) Design and describe the implementation of a dynamic array-like container that can grow as elements are added, without requiring a fixed size to be declared at initialization. Your explanation should include:

    • Memory Management: How do you allocate and deallocate memory for the underlying storage? What functions or mechanisms would you use to manage this memory dynamically?
    • Capacity Expansion Strategy: When the container runs out of capacity as new elements are inserted, how do you decide to increase its size? Discuss the growth factor and the trade-offs it involves in terms of memory usage and performance.
    • Indexing Operations: How can you ensure $O(1)$ random access to elements by index? What data structure or access method do you use to guarantee this?
    • Insertion and Deletion Complexity: What is the expected time complexity for inserting and deleting elements at arbitrary positions, and how does this scale as the size of the container grows? Address the concept of amortized complexity and explain why it might differ from the worst-case scenario.