103清大資工計科[參考解答]

1. (8%) Find the formula $S_n$ which satisfies $S_n = -S_{n-1} + 6S_{n-2} \text{ for } n \geq 2,$ so that $S_0 = 7$ and $S_1 = 4.$

參考解答：$S_n = 2 \cdot (-3)^n + 5 \cdot 2^n, \, n \geq 0.$

---

2. (9%) Prove that every tree with a vertex of degree k has at least k leaves.

參考解答：
$T(V,E), \, n = |E|$ 且leaves有 $l$ 個
$k = 1$ 時，trivial
$k \geq 2$ 時，assume $l \leq k – 1$
令 $m$ 為 $T$ 中所有點的度數和， $m = 2|E| = 2(n-1) = 2n-2$
另外， $T$ 具有1個點度數為1，一個為 $k$ ， $n-l-1$ 個點度數大於等於 $2$
$m \geq l + k + 2(n-l-1) \\ = l + k + 2n – 2l – 2 \\ = 2n + (k-1) – l – 1 \geq 2n + l – l – 1 \\ = 2n – 1$
Contradiction found.

---

3. (10%) Determine whether each of the following statements is true or false. Justify your answers.

(a) The propositions $(p \to q) \to r$ and $p \to (q) \to r$ are logically equivalent.
(b) The proposition $(p \land (q \to \neg p)) \to \neg q$ is a tautology.
(c) The argument form is valid:
$$p \to r \\ p \lor q \\ \neg q \\ \therefore r$$
(d) If $A = \{1,2,3\} \text{ and } B = \{1,3,4\},$ then $(1,4) \in P(A \times B).$ ($P(S)$ is the power set of a set $S; \, A \times B$ is the Cartesian product of the two sets $A$ and $B.$)
(e) For all integers $a,b,c \text{ with } c \neq 0,$ if $ac | bc, \text{ then } a | b.$

參考解答：(a) F (b) T (c) T (d) F (e) T

---

4. (7%) Answer the following questions.

(a) Give a recursive definition with initial condition(s) to calculate the sequence $a_n = n! (mod \, m),$ where $n,m$ are positive integers.
(b) The Fibonacci numbers are defined by $f_0 = 0, \, f_1 = 1, \text{ and } f_n = f_{n-1} + f_{n-2} \text{ for } n \geq 2.$ Show that $f_1^2 + f_2^2 +…+ f_n^2 = f_nf_{n+1}$ when $n$ is a positive integer.

參考解答：
(a) $a_n = na_{n-1} (mod \, m), \, a_1 = 1.$
(b)
When $n = 1, \, f_1^2 = f_1f_2$ is true
Assume the statement is true for all $n \leq k$
When $n = k + 1, \, f_1^2 + f_2^2 +…+ f_k^2 + f_{k+1}^2 = [f_kf_{k+1}] + f_{k+1}^2 = [f_kf_{k+1}] + [f_k + f_{k-1}]^2 = [f_kf_{k+1}] + [f_{k+1}]^2 = [f_kf_{k+1}] + [f_{k+1}f_{k+1}] = f_{k+1} [f_k + f_{k+1}] = f_{k+1}f_{k+2}.$
得證。

---

5. (5%) Assume you are the system designer for the CS website and want to keep news records into the system. Please analyze the requirements and choose the most suitable storage mechanism and indexing structure from the following candidates.

Singly Linked Lists, Dynamically Linked Stacks, Dynamically Linked Queues, Doubly Linked Lists, Binary Trees, Heap, Dynamic Hashing, B-Trees.

You should specify the indexing keys for the selections and explain the reasons.

參考解答：If the system wants to keep new records into the system, that means we’ll often do operations on the front and rear of the data, so the candidates will be Dynamically Linked Queues and Doubly Linked Lists.

---

6. (12%) Assume you are the system designer for Far Eastern Electronic Toll Collection System and want to keep the distance-based transportation records for customers to check. Please analyze the requirements and choose the most suitable storage mechanism and indexing structure from the following candidates.

Singly Linked Lists, Dynamically Linked Stacks, Dynamically Linked Queues, Doubly Linked Lists, Binary Trees, Heap, Dynamic Hashing, B-Trees.

You should specify the indexing keys for the selections and explain the reasons.

參考解答：Since the records are distance-based, that means we’ll often compare the distances between the data, so the candidates will be Heap and B-Trees.

---

7. (9%) Answer the following questions.

(a) A sorting algorithm is said to be stable if equal keys remain in the same relative order in the output as they are in the initial array. For quick sort, merge sort, bubble sort, insertion sort, selection sort, and heap sort, which sorting algorithms are stable?
(b) For quick sort, merge sort, bubble sort, insertion sort, selection sort, and heap sort, which sorting algorithms have the best-case time complexity in $O(n)?$

參考解答：
(a) merge sort, bubble sort, insertion sort.
(b) bubble sort, insertion sort.

---

8. (8%) Answer the following questions.

(a) What is the number of hash functions that can be used to assign positions to $n$ items in a table of $m$ positions (for $n \leq m$)?
(b) Following (a), what is the number of perfect hash functions?

參考解答：(a) $m^n$ (b) $P_n^m$

---

9. (7%) Answer the following questions, where multiple selections are allowed.

(a) Which one is the running time complexity for the fractional knapsack problem, where a store has $n$ items? (A) $O(nlogn)$ (B) $O(n^2)$ (C) $O(n^2 logn)$ (D) $O(n^3)$.
(b) Which one is the running time complexity for the general 0-1 knapsack problem? (A) polynomial (B) exponential (C) NP-complete (D) none of above.

參考解答：(a) A (b) B

---

10. (8%) Let $B_n$ denote the number of binary trees of $n$ nodes and let $H_n$ denote the number of different binary trees of height $h.$ Write down the recurrence equations of $B_n$ and $H_n$ respectively.

參考解答：
$B_n = \sum_{i=0}^{n-1} B_iB_{n-1-i}, \, n \geq 2. B_0 = B_1 = 1. \\ H_n = H_{n-1}H_{n-1} + 2H_{n-1}(\sum_{i=0}^{h-2} H_i), \, n \geq 2. H_0 = 1, H_1 = 3.$

---

11. (12%) Given a connected, undirected graph $G=(V,E)$ with a weight function $w: E \to R^+,$ a bottleneck spanning tree $T$ of $G$ is defined to be a spanning tree of $G$ whose largest edge weight is minimum over all spanning trees of $G.$ Moreover, the weight of the maximum-weight edge of $T$ is called the value of the bottleneck spanning tree.

(a) Either prove that the following statement is true or give a counterexample to show that it is false: Any bottleneck spanning tree is also a minimum spanning tree.
(b) Either prove that the following statement is true or give a counterexample to show that it is false: Any minimum spanning tree is also a bottleneck spanning tree.
(c) Give an $O(|V| + |E|)$ time algorithm to solve the following problem: Given a graph $G$ and a positive integer $k,$ determine whether the value of the bottleneck spanning tree is at most $k.$

參考解答：(a) F (b) T (c) Use DFS and visit the edges with higher weights first.

---

12. (5%) The degree-constrained spanning tree problem is defined as follows: Given a graph $G=(V,E)$ and a positive integer $k,$ does $G$ contain a spanning tree $T$ such that all vertices in $T$ have degree at most $k?$ Either give a polynomial time algorithm to solve the degree-constrained spanning tree problem, or prove that this problem is NP-hard.

參考解答：略

---

試題(pdf)：連結

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