# 交大 106 軟體

###### tags: `NCTU` `106` `軟體`

1. f(4)=1,f(5)=2,f(6)=3,f(7)=-1,f(8)=1
:::info
題目給的函數定義有點問題就是了，不過看得出來是想考 KMP
:::
2. (a) +A/*B-CDE (b) ABCD-*E/+ \(c\) 6
3. 3 2 7 8
4. (a) min heap is a binary tree which the child of the node in the heap is less than the node itself. (b)

            6
           /  \
          8    10
         / \   /
        9  18 15

5.

            B
           / \
          A   C
             / \
            D   E
               /
              F

6. (a) 12, 2, 7 (b) 3 \(c\) 0,9
7. (a)

            30
           /  \
          15  40
         / \    \
        10 20   50

(b)

             30
            /  \
           20   50
          /    /  \
         10   40  60

\(c\)

                3(B)
               /   \
              1(B) 5(B)
              \    /   \
             2(R) 4(R) 6(R)

8. (a) 215 (b)

             5
           /   \
          3     7
         / \   / \
       1|2 4  6   9

9. (a) Y (b) N \(c\) Y (d) Y
10. 楓業本裡有更詳細的解說。幾個重點：
- 關鍵在比較的次數
- 距離為 k 的兩個元素，兩者有發生比較的機率為 $\frac{2}{k+1}$
像是距離為 1、也就是兩兩相鄰元素，兩者有比較的機率為 $\frac{2}{1+1}=1$，也就是說不管如何一定都會比較到

比較次數的期望值為：$\sum_{k=1}^{n-1}(n-k)\frac{2}{k+1}\le n\sum\frac{2}{k+1}\le nlgn$

11.
step 1. choose the shortest two list $L_i, L_j$
step 2. merge $L_i$ and $L_j$ into $L_k$
step 3. add $L_k$ into the list set
step 4. if the set has only one list then it's done. Otherwise go back to step 1.
:::info
類似霍夫曼編碼
:::

12. (S1) T (S2) F(S3) F
:::info
2-SAT 可以利用強連通圖解決
:::

13. $O(n^{lg_23})$
14. 如果 $(v_i,v_{i+1})$ 屬於某個 minimum spanning tree，則在環上必存在一個邊 $(v_a,v_b)$，把它拿去替換掉 $(v_i,v_{i+1})$，必為 spanning tree，且 weight 更小，與假設矛盾。因此 $(v_i,v_{i+1})$ 必不屬於任何 MST
15. 先選紅的，再選藍的
16. A,C,E,B,D | (A,B,C,D,E)=(0,7,3,9,5)