-
Three of the following statements are incorrect. Pick out and correct them. (15 points)
(A) If $T(n) = 2T(\dfrac{n}{2}) + O(n)$ and $T(1) = O(1)$, then $T(n) = O(nlogn).$
(B) If $T(n) = T(\dfrac{n}{2}) + O(n)$ and $T(1) = O(1)$, then $T(n) = O(n).$
(C) $n^{10} + 1.1^n = O(n^{10})$
(D) $2n^2 + 1.5nlog^5n = O(n^2)$
(E) The number of odd degree nodes in an undirected graph must be odd.
(F) To obtain the breadth first search tree of a graph, we need to use a stack data structure.
參考解答：
C, wrong: $O(n^{10})$, correct: $O(1.1^n)$.
E, wrong: odd, correct: even.
F, wrong: stack, correct: queue.
$\quad$ -
Suppose that you are asked to code a C function subprogram to compute the Fibonacci sequence, which is recursively defined as $F_{n} = F_{n-1} + F_{n-2}, \, F_{0} = F_{1} = 1.$ In particular, you are asked to get the value of $F_{500}$. Will you code it as a recursive function or an iterative function? Why? (10 points)
參考解答： I prefer to use iterative function. Since recursive function recalculates a lot of values that has already been calculated, so it takes more time and space.
$\quad$ -
The following array represents a complete binary tree. Adjust it to be a max heap by showing each step. (15 points)
$$| \, 10 \, | \, 9 \, | \, 20 \, | \, 6 \, | \, 15 \, | \, 48 \, | \, 14 \, | \, 8 \, | \, 90 \, | \, 17 \, |$$
參考解答：
$\quad$ -
(a) Give conditions under which quick sort algorithm has the worst case behavior in terms of time complexity. Explain your answer. (10 points)
(b) Which sorting algorithm(s) is(are) stable, bubble sort, quick sort, merge sort, heap sort? (10 points)
參考解答：
(a) In an ordered sequence(ex: 1, 2, 3, 4, 5), if we choose the first element as pivot, the time becomes $T(n) = T(n-1) + O(n)$ which is $O(n^2)$.
(b) bubble sort, merge sort.
$\quad$ -
Let $G = (V, E)$ be a weighted undirected graph with any two vertices connected by at most one edge and $H$ be a subgraph of $G$ obtained by deleting an edge $e_{i}$ from $G, \, i.e., \, H = (V, E-\{e_{i}\}).$ True or false? Explain if false. (15 points)
(a) Minimal cost spanning tree of $G$ is unique.
(b) The path from vertex $A$ to vertex $B$ on a minimal cost spanning tree of $G$ is a shortest path from $A$ to $B$.
(c) If the total cost of minimal cost spanning tree of $H$ is greater than that of $G$, then $e_{i}$ must be an edge in any minimal cost spanning tree of $G$.
參考解答：
(a) False. If there are edges with the same weight, then it might not be unique.
(b) False.
(c) True.
$\quad$ -
Consider a sequence of keys: 27, 49, 17, 20, 61, 23, 92, 33, 77, 11, 31.
(a) Draw, step by step (showing clearly the type of rotation used), the result of inserting these keys into an empty AVL tree. (20 points)
(b) Write down the inorder sequence of the AVL tree in (a). (5 points)
參考解答：
(a)
(b) 11, 17, 20, 23, 27, 31, 33, 49, 61, 77, 92
試題(pdf)：連結
有任何問題，或想要完整解釋的，歡迎在下方留言唷！
發佈留言