### 一、Data Structures (50%)

1. (15%) Insert a sequence of keys (27, 49, 17, 20, 61, 23, 92, 33) into a data structure that has no keys in the beginning. The results are depicted as follows. Please answer the corresponding data structure for (a), (b) and (c), respectively.

$$圖片請看原檔$$

2. (25%) We know the red-black tree is one of many search tree schemes that are approximately balanced in order to guarantee that basic dynamic set operations take $O(lg \, n)$ time in the worst case.

(a) Please augment the red-black tree to maintain a dynamic set $Q$ of numbers that supports the operation MIN-GAP, which gives the magnitude of the difference of the two closest numbers in $Q.$ For example, if $Q = \{1, \, 3, \, 9, \, 15, \, 18, \, 22\},$ then MIN-GAP($Q$) returns 2, since 1 and 3 are the two closest numbers in $Q.$ Make the operations MIN-GAP as efficient as $O(lg \, n)$ where $n$ is the size of $Q.$
(b) According to the augmented red-black tree, it is also possible to simultaneously find the two closest numbers that result in the minimum gap in $O(lg \, n)$ time. Please explain how to do it?

(a) Add {minVal, maxVal, minGap} properties to each node.
(b) 略

3. (10%) For the following applications (a)-(f), please choose the most suitable data structure or algorithm from the candidates (1)-(9) to handle them. We denote $N(j) = i$ if application (j) is matched with data structure or algorithm (i) where $j \in \{a, \, b, \, c, \, d, \, e, \, f\}$ and $i \in \{1, \, 2, \, 3, \, 4, \, 5, \, 6, \, 7, \, 8, \, 9\}.$ Please find the value $\sum_{A=a}^{A=f} (N(A))^2 = ?$

(a) A network routing protocol in which the routing algorithm must determine a minimal spanning tree.
(b) The process scheduler in an operation system that needs to dispatch processes in the order of arrival.
(c) The dictionary look-up function that needs the index of words.
(d) The maze problem that needs to keep track of the path visited.
(e) The database query optimizer that needs the index of data records.
(f) The database system that is used in a hospital in which the data of patients accessed will be accessed again frequently.

(1) Stack (2) Queue (3) Splay tree (4) B-tree (5) Red-Black tree (6) Kruskal’s algorithm (7) Dijkstra’s algorithm (8) Topological sorting (9) Hashing

### 二、Algorithms (50%)

1. (20%) Solving the recurrence $T(n) = 2T(n/2) + n/log_2 n$ using $\Theta$ notation.

2. (10%) What is an optimal Huffman code for the following set of frequencies:

a: 25, b: 3, c: 12, d: 16, e: 39, f: 5, g: 13.

3. (10%) Give a $O(V^2lgV + VE)$-time algorithm to find the shortest paths between all pairs of vertices in a weighted and directed graph $G=(V, \, E).$

Johnson’s algorithm:
(1) Reweight the graph if there are negative weight edges in it.
(2) Apply Dijkstra algorithm to every vertex.

4. (10%) Describe an algorithm that, given $n$ integers in the range 0 to $k,$ preprocesses its input and then answers any query about how many of the $n$ integers fall into a range $[a…b]$ in $O(1)$ time, where $a, \, b \in \{0, \, 1,…, \, k\}.$ Your algorithm should use $\Theta (n+k)$ preprocessing time.

We take the preprocess of counting sort.
(1) Prepare an array[0…k] and loop thru every integers and $\forall i \in n$ array[i]++; $\Theta (n+k)$
(2) Output $\sum_{i=a}^{b}$array[i]. $\Theta (1)$

### 6 留言

1. #### daniel

想問一下第三題(a)~(f)分別對應到哪些資料結構或演算法，然後算出147的?

• 文章作者的留言

#### mt

對應如下：
(a)-(6)
(b)-(2)
(c)-(9)
(d)-(1)
(e)-(4)
(f)-(3)

2. #### micheal

想要請問一下第一題的(b)，我印象中B tree中leaf會在同一層，想要請問是我對B tree有理解錯誤嗎? 謝謝。

• 文章作者的留言

#### mt

這題的(b)應該是出錯，左下角的20應該要刪掉，不然會有兩個20～

3. #### minimini

想問一下第三題(c)為什麼是9啊 謝謝><

• 文章作者的留言

#### mt

嗨！主要是因為他要用index of words來做dictionary，所以如果hashing function夠好的話，應該是最適合的選則（跟其他選項比的話）～