考試

107成大資聯程設[參考解答]

一、Data Structures (50%)

1. (10%) Suppose that we have numbers between 1 and 1000 in a binary search tree, and we want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined?

(a) 2, 252, 401, 398, 330, 344, 397, 363.
(b) 924, 220, 911, 244, 898, 258, 362, 363.
(c) 925, 202, 911, 240, 912, 245, 363.
(d) 2, 399, 387, 219, 266, 382, 381, 278, 363.
(e) 935, 278, 347, 621, 299, 392, 358, 363.

參考解答:c, e.


2. (10%) Compute the minimum weight spanning tree and its cost of the following graph.

mt01

參考解答:38


3. (10%) Please write down the adjacency matrix of the following graph in the following table.

mt02

參考解答:

$v_1$$v_2$$v_3$
$v_1$011
$v_2$100
$v_3$100

4. (10%) Please compute the total cost of executing n of the stack operations (PUSH, POP, and MULTIPOP).

Stack Operations: PUSH, POP, and MULTIPOP.
PUSH(S,x) pushes object x onto stack S.
POP(S) pops the top of stack S and returns the popped object. Calling POP on an empty stack generates an error.
MULTIPOP(S,k) removes the k top objectives of stack S, popping the entire stack if the stack contains fewer than k objects. The following pseudo code presents the procedure of the MULTIPOP operation.

MULTIPOP(S,k):

while not STACK-EMPTY(S) and k > 0

    POP(S)

    k = k - 1

Both PUSH and POP take $O(1)$ time. The cost of MULTIPOP(S,k) is $1 + min(s,k)$ where s is the number of objects in stack S.
Suppose that there are n stack operations (PUSH, POP, and MULTIPOP) executed.
The stack is empty before those operations start and it is empty after those operations finished.

參考解答:Amortize cost: $O(n)$


5. (10%) What is the maximum numbers of elements in a heap of height h?

參考解答:$2^h – 1$


二、Algorithms (50%)

1. (10%) If someone gives a polynomial algorithm for an NP-hard problem, what conclusions you can draw from this fact?

參考解答:

mt03

2. (10%) Given a sequence of n numbers, what is the lower bound of sorting algorithms using comparison and exchange operations?

參考解答:$\Omega(nlgn)$


3. (10%) The following graph is a maximum flow problem. Each edge is labeled with its capacity. What is the maximum flow from vertex s to vertex t.

mt04

參考解答:Maximum flow: 23


4. (10%) Use master theorem to solve the recurrence $T(n) = 3T(2n/3) + O(1).$

參考解答:$\Theta(n^{log_{\frac{3}{2}}3})$


5. (10%) Given a graph $G=(V,E),$ a vertex cover $C \subseteq V$ is a vertex subset, such that if $(u,v) \in E,$ then $u \in C$ or $v \in C.$ The minimum vertex cover problem is to find a vertex cover $C^*$ of $G$ with the minimum cardinality. The following algorithm is a $\delta$-approximation algorithm to find a vertex cover $C$ satisfying $|c| \leq \delta \cdot |C^*|.$ Please compute the minimum value of $\delta.$

APPROX_VERTEX_COVER(G):

C <- 0

E' <- E(G)

while E' != 0

    do let (u,v) be an arbitrary edge of G

        C <- C union {u,v}

        remove from E' every edge incident on either u or v

return C

參考解答:2


試題(pdf):連結

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

4 留言

  1. Jackson

    請問 DS part (4)
    我寫透過 accounting method : push 為 2, pop 為 0
    整體 cost : (2 * n + 0 * n) / (n + n) = 1
    所以每次 operation cost O(1) time complexity
    因此 n 次 operation cost O(n)
    還有 Algo part (5)
    我直接寫 2 approxiation algorithm
    隨便舉例不超過最佳解 2 被差
    |C| / |C*| <= 2 但感覺不夠嚴謹
    不知道以上寫法安不安全 感謝

    • 文章作者的留言

      mt

      我覺得DS(4)這樣寫沒問題。另外ALGO(5)的話我覺得有寫出最重要的|C| / |C*| <= 2至少就有一半以上的分數了,真的怕的話還是要寫完整的證明比較保險~

  2. ting

    大大你好,請問第五題的答案是建立在root為height=1的情況嗎?
    如果root為height=0的情況the maximum numbers of elements in a heap的答案是2^(h+1) -1 這樣理解對嗎?

    或者說 寫答案前 要先寫上假設root的height是0、1在作答

回覆留言對象 取消回覆