# 成大 108 軟體
###### tags: `NCKU` `108` `軟體`
1. (1) F, $O(v^2)$
(2) F
(3) F, open addressing 為 $O(\frac{1}{1-\alpha})$， chaining 為 $O(1+\alpha)$

2. (1)

||0|1|2|3|4|5|6|7|8|
|-|:-|:-|:-|:-|:-|:-|:-|:-|:-|
|e|0|9|4|7|11|11|16|18|19|
|l|0|9|9|7|11|11|18|18|19|

(2) $v_0,v_1,v_3,v_4,v_5,v_7,v_8$
(3)$$<v_0,v_1,v_4,v_7,v_8>\\<v_0,v_3,v_5,v_7,v_8>$$
3. (4) $O(nlgk)$
4. 1)證明欲證的問題可在多項式時間內被驗證 2)證明某個已知為 NPC 的問題，可在多項式時間內被 reduce 成欲證問題
5. 想了老半天還是想不到 $O(V)$ 的演算法...
6. (a) F, Dynamic programming
(b) T
\(c\) T
(d) F
(e) T
7. $O(lgn)$