# 清大 106 軟體
###### tags: `NTHU` `106` `軟體`
1-2. min-heap
1-3. 5,7,10,15,29,28,19,34,60

2-1. ACD
2-2. AD
2-3.
- AVL 的左右子樹也是 AVL。
- 高度為 h 的最小 AVL，其左右子樹的高度必差 1
- $n\ge N_h$
根據以上觀察，可得出以下遞迴式：$N_h=N_{h-1}+N_{h-2}+1$
解遞迴得: $N_h=c_1(\frac{1+\sqrt{5}}{2})^h+c_2(\frac{1-\sqrt{5}}{2})^h-1$
因為 $|\frac{1-\sqrt{5}}{2}|\lt 1$，所以當 h 增加時，此項趨近於 0。
所以可再簡化為: $N_h=c_1(\frac{1+\sqrt{5}}{2})^h-1$
根據第三個觀察，$n\ge N_h=c_1(\frac{1+\sqrt{5}}{2})^h-1$
兩邊取 log 得 $lgn\ge lgc_1+hlg(\frac{1+\sqrt{5}}{2})$
移項得 $h\le lg(\frac{1+\sqrt{5}}{2})(lgn-lgc_1)=O(lgn)$

4-1. $\frac{10}{26}$
4-2. 對應的 slot 已經沒位置/yes/2 號 slot
4-3. chaining

5-A. incorrect
令 n = 10000, $3n^2-100n+6=300000000-1000000+6\gt 10000$
5-B. correct
$lg(n!)=lg1+lg2+...+lgn\le lgn+lgn+lgn+...+lgn=O(nlgn)$
$lg(n!)=lg1+lg2+...+lgn\ge lg\frac{n}{2}+lg(\frac{n}{2}+1)+...+lg(n)\ge lg\frac{n}{2}+\frac{n}{2}+...+\frac{n}{2}=\frac{n}{2}lg\frac{n}{2}=\Omega(nlgn)$
得 $lg(n!)=\Theta(nlgn)$
5-C. correct
$n!=n(n-1)(n-2)...(2)(1)\le nnnnn...n=O(n^n)$
5-D. correct
$(n+a)^b=\sum_{i=0}^{b}\binom{b}{i}a^in^{b-i}=n^b\sum_{i=0}^{b}\binom{b}{i}a^in^{-i}=n^b(a+\frac{1}{n})^b=\Theta(n^b)$
5-E. incorrect
證明同上

6. BrillianGeneius: 資料平均分佈在 $[0,1)$, ASuperStar:...可能是要 stable sort ...吧

7-1. YES
NP-Complete 本身就是 NP 和 NP-hard 的交集
7-2. NO
NP 是指能在多項式時間內被驗證的問題集合，所以 P 也屬於 NP
7-3. NO
第二步應該是 reduce any known NP-complete problem to X (in polynomial time)
7-4. NO
2-approximation

8-1.
clipue problem 就是 1-plex problem，所以 k-plex problem 為 NP-hard
8-2.
如果 $S'$ 是 k-plex，令 $a\in S$，則 $S-\{a\}$ 的最小 degree 為 $|S|-k-1$，依然為 k-plex。重複此步驟下去，就能得到任意子集合，且皆為 k-plex。

9-1. $2^7+2^7-2^5=96$
9-2. 96
9-3. $\binom{7}{3}=35$, $\binom{9}{3}=84$

10-1. $(-3)^9$
10-2. $a_n=-2^{n+1}+3^{n+1}$