# 台大 104 軟體
###### tags: `NTU` `104` `軟體`
1. ABBBBBBBBA
2. (1) $2^i$ (2) $2^{k+1}-1$ (3) $n_0\le \frac{n-n_2}{2} + 1$
:::info
假設 $n_1=$ 度數為1的點數量,$n_2,n_3$ 以此類推。$n$ 為總數量。
則 $n_1+n_2+n_3=n$ 且 $n_1=n_3+2$
可得$$
n_1+n_2+n_1-2=n\\
2n_1+n_2=n+2\\
n_1=\frac{n-n_2}{2}+1
$$
如果根有兩個子節點，則$n_0=n_1$，反之 $n_0=n_1-1$。因此可得 $n_0\le n_1=\frac{n-n_2}{2}+1$
:::
(4) floor($lg(n+1)$) + 1
(5) $n+1$
(7) 21 / 171

4. (1) $O(nlgn)$ (2) $O(n^2)$ (3) {1,2,3,4,5,6}
5. (1) $O(V^2)$ (2) $O(V^{1.5}lgV)$ (3) $O(V^{1.5})$
:::info
(1) 找出離 current minimum spanning tree 最近的點需要 $O(V)$、輪迴 O(V) 次。更新每個點的最近距離需要 $O(E)$。總共為 $O(V^2+E)=O(V^2)$
(2) 找出離 current minimum spanning tree 最近的點需要 $O(lgV)$、輪迴 $O(V)$ 次，更新每個點的最近距離需要 $O(ElgV)$，總共為 $O(VlgV+ElgV)=O(V^{1.5}lgV)$
(3) 承上，但是更新最近距離需要 $O(E)$，總共為 $O(VlgV + V^{1.5})=O(V^{1.5})$
:::
6. (1) $O(NlgN)$ (2) $O(Nlg^2N)$ (3) $O(N^2)$