# 交大 107 軟體
###### tags: `NCTU` `107` `軟體`
1. 19
2. 13456789 / 14653987
3.

          [11]
    (2)          [14]
[1]     [7]       (15)
      (5)  (8)
            (9)

          [11]
    (2)          [14]
[1]     (7)       (15)
      [5]  [8]
            (9)

          [11]
     (7)       [14]
  (2)   [8]      (15)
[1] [5]   (9)

       [7]
  (2)       (11)
[1] [5]   [8]  [14]
           (9)   (15)

4. $T(n)=T(\frac{n}{2})+O(1),\ T(n)=lgn$ by master method
5. 19
:::info
所有的節點串起來，會是一棵完全二元樹。
foo1 會將所有節點的左右子樹對調。
foo2 是用後序走訪整棵樹，順序從 0 開始如下(X 代表 NULL)：
XX$n_7$XX$n_6n_3$XX$n_5$XX$n_4n_2n_1$
而順序為偶數的要加起來，有$n_7,n_3,n_4,n_1$
所以答案為 4+1+8+6=19
:::
6. 7
7. (a) $O(VE + V^2lgV)$
(b)
- 所有的邊經過 reweight 後皆為非負整數
proof:
對於任意邊 (u, v)，滿足 $h(v)\le h(u) + w(u,v)$
移項可得 $h(u)-h(v)+w(u,v)\ge 0$
- 任兩點之間的任何路徑，其最短路徑在經過 reweight 後，依然是該兩點之間的最短路徑
proof:
給定任意兩點 u, v，以及任一一條串連兩點的路徑 $<u,v_1,v_2,v_3,...,v_n,v>$
其長度為：$h(u)-h(v_1)+w(u,v_1)+h(v_1)-h(v_2)+w(v_1,v_2)+...+h(v_n)-h(v)+w(v_n,v)=\\h(u)-h(v)+w(u,v_1)+w(v_1,v_2)+...+w(v_n,v)$
可發現任意路徑的權重增幅皆為 h(u)-h(v)。因此原本的最短路徑，經過 reweight 後，依然是該兩點之間的最短路徑。
8. ...略
9. (a) A[i] - k (b) A[i]
:::info
找落差最大的那一段
:::
10.
Suppose G=(V,E)

Step1: let $V'=V\ \cup\ \{s,t,a,b\}$
Step2: let $E'=E\ \cup\ \{\{s,v\},\{v,t\}\ |\ v\in V, v\ne x\}\ \cup\ \{\{a,s\},\{b,t\}\}$
Step3: run HamP(G'=(V',E'))

若 G' 存在 HP，則其必為此形式：
<a,s,u,....,v,t,b>
其中 u 和 v 皆不為 x
把 s, t, a, b 拿掉，即為不以 x 為端點的 HP

反過來講，若 G 存在不以 x 為端點的 HP: <u,...,v>，則利用上述方法構建 G'，必存在一條 HP: <a,s,u,...,v,t,b>