考試

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):連結

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

6 留言

  1. daniel

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

  2. micheal

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

  3. minimini

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

    • 文章作者的留言

      mt

      嗨!主要是因為他要用index of words來做dictionary,所以如果hashing function夠好的話,應該是最適合的選則(跟其他選項比的話)~

發佈留言