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

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

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

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.

.wp-block-code{border:0;padding:0}.wp-block-code>div{overflow:auto}.shcb-language{border:0;clip:rect(1px,1px,1px,1px);-webkit-clip-path:inset(50%);clip-path:inset(50%);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px;word-wrap:normal;word-break:normal}.hljs{box-sizing:border-box}.hljs.shcb-code-table{display:table;width:100%}.hljs.shcb-code-table>.shcb-loc{color:inherit;display:table-row;width:100%}.hljs.shcb-code-table .shcb-loc>span{display:table-cell}.wp-block-code code.hljs:not(.shcb-wrap-lines){white-space:pre}.wp-block-code code.hljs.shcb-wrap-lines{white-space:pre-wrap}.hljs.shcb-line-numbers{border-spacing:0;counter-reset:line}.hljs.shcb-line-numbers>.shcb-loc{counter-increment:line}.hljs.shcb-line-numbers .shcb-loc>span{padding-left:.75em}.hljs.shcb-line-numbers .shcb-loc::before{border-right:1px solid #ddd;content:counter(line);display:table-cell;padding:0 .75em;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;white-space:nowrap;width:1%}MULTIPOP(S,k):

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

POP(S)

k = k - 1Code language: plaintext (plaintext)

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.

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

### 二、Algorithms (50%)

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

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

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.

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

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 CCode language: plaintext (plaintext)