一、Data Structures (50%)
1. (10%) Given inorder and preorder traversal of a tree as follows.
inorder: JHKFIDGBEAC
preorder: ABDFHJKIGEC
(5%) reconstruct the binary tree
(5%) show the postorder traversal of this tree
參考解答:
(a)
(b) JKHIFGDEBCA
2. (10%) Suppose there are 11 slots available from 250, please give the hashing function to insert the keys, 42, 77, 85, 113, 315, 433, 474, 479, 574, 582, 698, to the 11 slots without collision by using the division method, and show the hashing table.
參考解答:$h(x) = (x \, mod \, 11) + 250$
3. (10%) What are the minimum and maximum numbers of elements in a heap of height $h?$
參考解答:$min = 2^{h-1}, \, max = 2^h – 1.$
4. (10%) Given an $O(nlgk)$-time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists.
參考解答:Use loser (winner) tree and extract 1 item at a time.
5. (10%) Given a sequence $K = (k_1, \, k_2,…, \, k_6)$ of 6 distinct keys in sorted order with probabilities $0.06, \, 0.08, \, 0.10, \, 0.04, \, 0.12, \, 0.14.$ Some searches may be for values not in $K,$ and so we also have 7 dummy keys, $d_0, \, d_1,…, \, d_6,$ with probabilities $0.07, \, 0.07, \, 0.07, \, 0.07, \, 0.06, \, 0.06, \, 0.06.$ Because we have probabilities of searches for each key and each dummy key, we can determine the expected cost a search in a given binary search tree $T.$ Suppose the expected cost of a search in $T$ is $E[\text{search cost in }T] = \sum_{i = 0}^n (depth_T(d_i)+1) \cdot q_i,$ where $depth_T$ denotes a node’s depth in the tree $T.$ Determine the cost of an optimal binary search tree.
參考解答:2.99
二、Algorithms (50%)
1. (18%) Answer each part TRUE or FALSE for the little $o$ notation.
(a) $n = o(8n)$
(b) $2^n = o(n^3)$
(c) $2^n = o(4^n)$
(d) $1 = o(n^2)$
(e) $n = o(lgn)$
(f) $1 = o(\dfrac{1}{n})$
參考解答:(a) F (b) F (c) T (d) T (e) F (f) F
2. (12%) Given an $O(V)$-time algorithm that determines whether or not a given undirected graph $G=(V,E)$ contains a cycle.
參考解答:
(1) Set color of all vertices to white.
(2) Set color of the source vertex to gray.
(3) Recursively perform DFS.
(4) If a color gray vertex is found, return True, else return False.
3. (10%) Use the master method to give tight asymptotic bounds for the following recursive $T(n) = 7T(\dfrac{n}{2}) + \Theta(n^2).$
參考解答:$\Theta(n^{lg7})$
4. (10%) A directed graph $G=(V,E)$ is a semiconnected if, for all pairs of vertices $u,v \in V, \, u$ is reachable from $v$ through a directed path, or $v$ is reachable from $u$ through a directed path. Given a linear-time algorithm to determine whether or not $G$ is semiconnected.
參考解答:
(1) 找 SCC(G).
(2) 建立 Component graph G’.
(3) 對 G’ 做 Topological sort.
(4) 若有 linear chain 則為 semi-connected.
試題(pdf):連結
有任何問題,或想要完整解釋的,歡迎在下方留言唷!
發佈留言