跳轉到

107 資料結構與演算法

說明

  • 注意：請用 2B 鉛筆作答於答案卡，並先詳閱答案卡上之「畫記說明」
  • 注意: (I), (II), (III), (IV) 四大題共 16 題選擇題考生應劃卡作答於『答案卡』。選擇題不答零分，答錯倒扣當題分數
  • 非選擇題請作答於試卷內之「非選擇題作答區」，請標明題號依序作答

選擇題

第 I 題（14%）— Time Complexity

For each of the following algorithms, what is the tightest asymptotic upper bound of its runtime complexity? Please use the following table of (A)-(E) choices when answering.

(A) (B) (C) (D) (E)
\(O(1)\) \(O(n)\) \(O(\lg n)\) \(O(n \lg n)\) \(O(n^2)\)

  1. (2 points) quick sort for \(n\) numbers (worst-case time)

  2. (2 points) quick sort for \(n\) numbers (expected time)

  3. (2 points) bucket sort for \(n\) numbers (expected time)

  4. (2 points) MAX-HEAPIFY for \(n\) numbers (expected time)

  5. (2 points) PUSH/POP on stack of \(n\) keys (expected time)

  6. (2 points) SEARCH on hash table with \(n\) static keys and perfect hashing (worst-case time)

  7. (2 points) INSERT/DELETE on red-black tree with \(n\) keys (worst-case)

我的答案

1.

2.

3.

4.

5.

6.

7.

第 II 題（8%）— Min-Heap

In a min-heap stored in an array, please answer the following questions after these 11 numbers have been inserted: 12, 8, 23, 21, 6, 1, 7, 25, 24, 22, 26.

  1. (2 points) What is the height of the heap? (A) 2 (B) 3 (C) 4 (D) 5

  2. (3 points) What is the value of the node at index 3? (A) 1 (B) 6 (C) 7 (D) 8

  3. (3 points) What is the value of the left child of the node with value 12? (A) 22 (B) 24 (C) 25 (D) 26

我的答案

8.

9.

10.

第 III 題（8%）— Hash Table Collision

There are various collision resolution strategies for hash tables. Please answer the following questions under the assumption of simple uniform hashing and all keys are unique, given a hash table \(H\) with \(m\) slots to store \(n\) elements.

  1. (3 points) Suppose we use chaining with the hash function \(h(k) = k \mod 5\), and insert the following 13 keys into \(H\) with 5 slots in the exact sequence: 32, 39, 21, 3, 6, 40, 34, 24, 15, 25, 7, 13, 50. What is the expected number of key comparisons for searching for an element with the key \(k\)? (A) 1.0 (B) 2.6 (C) 3.0 (D) 3.6

  2. (5 points) Suppose we use double hashing of the form \(h(k, i) = (h_1(k) + i h_2(k)) \mod m\), where the primary hash function is defined as \(h_1(k) = k \mod 7\) and the secondary hash function is defined as \(h_2(k) = 5 - (k \mod 5)\). Given \(H\) with 7 slots to insert the following 4 keys in the exact sequence: 35, 42, 3, 21. What is the index of the slot storing the element with the key 21? (A) 0 (B) 3 (C) 4 (D) 5

我的答案

11.

12.

第 IV 題（10%）— Trees

Suppose we want to use trees to store the following 10 elements, inserted in this exact sequence: 88, 93, 76, 50, 46, 3, 32, 85, 30, 95.

  1. (2 points) What is the height of the tree if we insert these 10 elements in sequence into a Binary Search Tree? (A) 4 (B) 6 (C) 7 (D) 8

  2. (2 points) In the Binary Search Tree from the previous question, suppose we remove the node with value 76, what's the parent of the node with value 50? (A) 46 (B) 85 (C) 88 (D) 93

  3. (3 points) Suppose we insert these 10 elements in sequence into an AVL Tree, what's value of the parent of the node with value 76? (A) 46 (B) 85 (C) 88 (D) 93

  4. (3 points) In the AVL tree from the previous question, suppose we remove the node with value 32, what's the parent of the node with value 30? (A) 3 (B) 46 (C) 50 (D) 76

我的答案

13.

14.

15.

16.

非選擇題

第 V 題（35%）— Deque

In the data structure queue, elements can be added to one end and removed from the other. Different from queues, a deque allows elements to be added to and removed from both ends. For example, suppose a deque contains 5 numbers as follows:

(head) 2, 3, 1, 4, 5 (rear)

One possible generated sequence is < 5, 2, 4, 1, 3 > whose alternative sum is 9.

(a) (15 points) Given a deque with a permutation of the numbers from 1 to \(n\) (\(n \geq 5\)), we want to remove all of the numbers to form a sequence \(< a_1, a_2, a_3, \ldots, a_n >\) that maximizes the alternative sum \((a_1 - a_2 + a_3 \ldots \pm a_n)\), where \(a_1\) is the first number removed, and so on. For example, suppose a deque contains 5 numbers as follows:

(head) 2, 3, 1, 4, 5 (rear)

One possible generated sequence is < 5, 2, 4, 1, 3 > whose alternative sum is 9.

  1. (5 points) Give an example to demonstrate that the problem cannot be solved by a greedy algorithm, which first removes the larger one of the two ends, then removing in the order of the larger one, the smaller one, etc. Show your calculation.

  2. (10 points) Devise an \(O(n^2)\) algorithm to generate the optimal sequence for a given deque. Explain how your algorithm works on the example you give previously.

(b) (20 points) Stacks can be used to implement queues and deques.

  1. (6 points) Describe how to implement a queue using only two stacks. And then describe how to extend the way to implement a deque using the same two stacks.

  2. (7 points) Use the accounting method to prove the amortized time complexity of a sequence of \(n\) queue operations (implemented with stacks) is \(O(n)\). Show your derivation.

  3. (7 points) Prove or disprove that the amortized time complexity of a sequence of \(n\) deque operations (implemented with stacks) is also \(O(n)\). Show your derivation.

我的答案

(a)

1.

2.

(b)

1.

2.

3.

第 VI 題（25%）— Graph Algorithms (Earthquake Roads)

The network of roads in NTU can be modeled as a graph \(G = (V, E)\), where each node \(v_i \in V\) represents a building and each edge \(e_{ij} \in E\) represents a road connecting the buildings \(v_i\) and \(v_j\). Each edge \(e_{ij}\) is associated with a positive weight \(w_{ij}\), i.e., \(w_{ij} > 0\).

(a) (10 points) Consider all roads are bidirectional. Before an earthquake, it is possible to travel between any pair of buildings. However, after the earthquake, all of the roads are damaged and closed until repairs are completed. Suppose the weight \(w_{ij}\) indicates the time required to repair the corresponding road \(e_{ij}\). Assume that all roads are fixed at the same time.

Given two buildings \(v_a\) and \(v_b\), please propose an efficient algorithm to determine a path starting from \(v_a\) to \(v_b\) that can be fixed in the smallest amount of time. Analyze the time complexity of your algorithm.

(b) (15 points) Consider all roads are directional but we don't know their directions in \(G\). Suppose the weight \(w_{ij}\) indicates the time required to travel from the building \(v_i\) to the building \(v_j\). Given two buildings \(v_a\) and \(v_b\) and the following two different conditions, for each condition, please propose an efficient algorithm to determine the directions of the roads in \(G\) so that the time to travel from \(v_a\) to \(v_b\) is minimum. Assume that \(v_b\) is reachable from \(v_a\) in \(G\).

  1. (5 points) Consider all edges have equal weights. Your algorithm should run in linear time.

  2. (10 points) Consider the edges might have different weights. Analyze the time complexity of your algorithm in this question.

我的答案

(a)

(b)

1.

2.