---
# System prepended metadata

title: 台大 109 軟體
tags: [NTU, '109', 軟體]

---

# 台大 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。
