---
# System prepended metadata

title: 清大 105 軟體
tags: [NTHU, '105', 軟體]

---

# 清大 105 軟體
###### tags: `NTHU` `105` `軟體`
1. (A) prefix: */+abc-de / postfix: ab+c/de-*
(B)

                A
               /|\
              / | \
             /  |  \
            B   D   G
           / \ / \
          C  EF   I
            /
           H
    \(C\)

                55             45
               /  \           /  \
              37  77         37  77
              \    /         \    /
              41  60         41  60
             /  \   \        /  /  \
            38  45  70      38 55  70
            \               \
            40              40
    (D) preorder 最開頭的為根，在 inorder 中，根的兩邊即為左右子樹，不會有第二種可能。

    (E) 當只有一個子樹時，子樹可為左子樹或右子樹。舉例:

        pre: AB, post: BA 有兩種可能:
            A           A
           /             \
          B               B 
(F)
```c=
void longestDelay(node *root, int AccDelay)
{
    if (root == NULL) {
        MAX = MAX < AccDelay ? AccDelay : MAX;
        return;
    }
    longestDelay(root->lchild, AccDelay + root->delay);
    longestDelay(root->rchild, AccDelay + root->delay);
}
```
2. (A) $A^* = \{(a, b)\ |\ there\ is\ a\ path\ of\ length \ge\ 0\ between\ a\ and\ b\ in\  G\}$\
(B) All-pairs shortest path
\(C\) 如果圖中不包含 cycle of odd length，則可以用以下方式建構二分圖:

        a. 隨機選取一個點，加進 L
        b. 將與 L 所有相鄰的點加進 R。R 中的點不可能相鄰，否則就會有 odd cycle
        c. 將所有與 R 相鄰的點加進 L。同理，L 中的點不可能相鄰。
        重複 bc 直到所有點皆屬於 R 或 L

    (D) topological sort: $<v_{i_1}, v_{i_2}, ...,v_{i_n}>$ 滿足: $\forall x, y, 1\le x<y\le n\ such\ that\ (v_{i_y}, v_{i_x}) \notin E$
    (E) 用 DFS 遍歷所有點，紀錄離開的時間。以離開的時間依序由大到小排序的結果，即為 topological sort

3. (A) 4, 2, 9
(B) 9
\(C\) $a_n=2\times 4^n$, $b_n=4^n$
4. (A) $\frac{7!}{2!3!}$
(B) 
$$
g(x) = a_1 + a_2x+a_3x^2+a_4x^3+...\\
-8g(x)=-8a_1x  -8a_2x^2-8a_3x^3-...\\
$$
兩式相加得
$$
(1-8x)g(x)=9+10x+(10x)^2+(10x)^3+...=8+\frac{1}{1-10x}\\
g(x)=\frac{4}{1-8x}+\frac{5}{1-10x}
$$
得 $a_n=4\cdot8^{n-1}+5\cdot10^{n-1}$
\(C\) 無聊
5. (A)
將 u 和 v 分成 $$u_2\cdot2^\frac{n}{2}+u_1\\ v_2\cdot2^\frac{n}{2}+v_1$$
分別計算:
$$
(u_2+u_1)(v_2+v_1)\\
(u_2-u_1)(v_2-v_1)\\
u_1v_1
$$
三式聯立可得:
$$
u_1v_1\\
u_2v_2\\
u_1v_2+u_2v_1
$$
$u_1v_1 + u_2v_2\cdot2^n+(u_1v_2+u_2v_1)\cdot2^\frac{n}{2}$ 即為所求
    (B) FFF
6. (A) $\begin{pmatrix}1&1&-1\\2&2&1\\-1&-1&3\end{pmatrix}$
    (B) 51