100成大資工程設[參考解答]

一、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.

$$圖片請看原檔$$

參考解答：(a) AVL tree (b) B tree (C) Max Heap

---

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

參考解答：147

---

二、Algorithms (50%)

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

參考解答：$\Theta (nlglgn)$

---

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.

參考解答：a: 01, b: 0000, c: 001, d: 101, e: 11, f: 0001, g: 100.

---

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)$

---

試題(pdf)：連結

有任何問題，或想要完整解釋的，歡迎在下方留言唷！