# 清大 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)

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