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

3. (10%) What are the minimum and maximum numbers of elements in a heap of height $h?$

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.

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.

二、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})$

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

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.