# 台大 109 軟體 ###### tags: `NTU` `109` `軟體` 1. 345 2. 12 :::info 應該是 min(n, m)？不過沒這個答案... ::: 3. 245 :::info 因為是小 o，所以 o(nlgn) 不能選，沒錯吧？ ::: 5. 124 :::info 3.也有可能在最大值的父節點上。 5.第三小的值不一定在第一層 ::: 5. 125 :::info 不知道是我太鑽牛角尖還是...這題目我有點看不太懂它在講什麼。所以直接預設它說的就是楓葉本上的演算法 ::: 6. 345 :::info 2. 假設 n 是偶數。則期望值為: $\frac{n}{2}\{(n-1)+(n-2)+...+(\frac{n}{2}+1)\}=\frac{3}{4}n$ 45. 楓葉本裡有。簡單來講，如果選中 [j, i] 區間以外的數字，則不會有任何影響。如果選中 [j, i] 區間內的數字，假如選到 i 或 j，則兩個就會互相比較，反之，就不會。因此機率為 $\frac{2}{i-j+1}$。4 跟 5 看似有點不同，但題目設定 K 是 [1, n] 的排序，所以是一樣的。 ::: 7. 13 :::info 2.free 得太早了。 45.這兩種做法看不出到底為何能改善 push/pop 的效率 ::: 8. 1245 :::info 3.如果 n 是第一個送進去的話，就不會 4.對於任意 i, j 且 j < i，i 要跳過 j 的機率為 $\frac{1}{2}$，因此 i 要跳過的數量期望值為 $\frac{i-1}{2}$ 5.$\sum_{i=1}^{n} \frac{i-1}{2}=\frac{1}{2}(n)(n-1)$ ::: 9. 145 :::info 23.O(n) 比較恰當...？ 45.反正就是找右子樹的最小值，或是左子樹的最大值來替換。 ::: 10. 45 :::info 1.這個我不是很確定，但楓葉本裡，紅黑樹的高度為 O(lgn) 的證明沒有用到 1，所以我不選。 2.100000 個點不為完全二元樹，如果全黑的話，2就不成立了 34.違反 3 才對 ::: 11. (a) 將陣列分成兩半，假設是 B 和 C。先取 B[0] 和 C[0] 比較，確立當前的最大值和最小值。然後依序往下比較 B[i] 和 C[i]，將比較小的跟當前最小值比較，比較大的跟當前最大值比較。 (b) 第一次的比較次數為 1，接下來每次都有三次比較，總共為 $3(\frac{n}{2}-1)+1=\frac{3}{2}n-2\lt 1.67n$ 12. (a) $f(n)=max\{f(n-1), f(i)+r_n\}$, i is the largest s.t. $l_n-l_i\gt T$, $f(0)=0, l_0=-\infty$ 對於車站 n，如果不選擇在那裡開店，問題就變成「在前 n - 1 個車站開店的最大利潤是多少」，為 f(n-1)；如果要開店，那上一間店就必須距離超過 T，利潤為 $f(i)+r_n$ 最差的情況下，每次都得遍歷一遍找尋最大的 i，所以時間複雜度為 $O(n^2)$ (b) $f(n)=max\{f(n-1), f(n-T-1)+r_n\},f(i)=r_i\ \forall i\le T$ 因為距離都一樣，所以就不需要遍歷了，因此可以在 O(n) 內算出。 13. (a) 對於所有邊 (u, v)，先用 FIND(u)==FIND(v) 判斷兩點是否連通。如果是，則必有環，此圖不為樹。如果不連通，那就執行 UNION(u, v)，然後繼續下一條邊。時間複雜度為 O(nlgm) (b) 原本的比較好。子樹的節點比較少，不代表它的高度比較矮，樹有可能因此失衡。 14. (a) 下圖為兩個 center 和三個 diameter 的樹 ``` O | O <--center | O <--center /|\ O O O <--- 三個 diameter 的端點 ``` (b) 不存在 如果樹存在兩個以上 center，則彼此會位於對方的最長路徑上。畫個圖就可以明白，假設 v 和 u 都是 center，v 到 O 的路徑為 v 的最長路徑，距離為 k： ``` v～～～～～～～～O | u ``` 則 u 的最長路徑的長度一定超過 k，不可能為 center。 所以可以知道，若一個樹存在兩個 center，那一定是這種形式： ``` A~~~~~~~v~~u~~~~~~~~B \______k___/ \____k_____/ ``` v 最長到 B，u 最長到 A，假設距離為 k。如果有第三個 center，那一定位於 u 和 v 中間 (因為 center 要在彼此的最長路徑上)： ``` A~~~~~~~v~~(((ﾟДﾟ;)))~~u~~~~~~~~~B ``` 如果那個中間的點是 center，那 u 跟 v 就不可能是 center。用簡單的數學就可以算出。假設兩點距離為 l，且 l 大於 1（不大於 1 中間就不會有點了） ``` /-l-\ A~~~~~~~v~~~u~~~~~~~~B \______k___/ \____k_____/ ``` 假設那個點剛好在 v 旁邊好了，則它到 A 和 B 的距離分別為 $k-l+1$ ＆ $k-1$，因為 $l\gt 1$，兩個數字都會小於 k，所以 u 和 v 都不會是 center，矛盾。 所以 center 最多只會有兩個 \(c\) 假設不在 diameter 上： ``` O---------------v------------------------O | | | (((ﾟдﾟ))) <--- center | | ... ``` 則它跟 diameter 的匯集點 v 的 eccentricity 會比 center 來得小，矛盾。 15. 廢話很多，就只是 set cover problem。 (a) U={1,2,3,4,5,6} F={{1,2,3}, {1,4}, {2,5}, {3,6}}。用 greedy 會全部都選到，但其實只要選後三個就好了。 (b) 要證明它是 NP，不難，不贅述。證明它是 NP-hard，可用 vertex cover reduce。 給定一個圖 G=(V,E), let n = |V|, m = |E| 令 $U=\{u_1,u_2,u_3,...,u_m\}$, $F=\{f_1,f_2,f_3,...,f_n\}$ $\forall u_i\in U, \forall F_j\in F$, $u_i\in F_j$ if and only if $v_j$ is incident to $e_i$ 則在 (U, F) 找一個 size 為 k 的 set cover 相當於在 G 中找 size 為 k 的 vertex cover。