110 年 國立成功大學資訊工程系碩士班《程式設計》

核心觀念

二元搜尋樹（BST）中，每個節點的左子樹鍵值小於該節點，右子樹鍵值大於該節點。依序將前序走訪序列中的鍵值插入 BST，即可重建題目所指的樹。

根節點所在層級為第 1 層；每往下一條邊，層級增加 1。因此，樹的層數等於根節點到最深葉節點的邊數加 1。

解題方法

依序插入各鍵值：

1. $50$ 為根節點。
2. $15<50$，放在 $50$ 左側；$11<50$ 且 $11<15$，放在 $15$ 左側。
3. $3<11$，放在 $11$ 左側；$2<3$，放在 $3$ 左側。
4. $22<50$ 但 $22>15$，放在 $15$ 右側。
5. $84>50$，放在 $50$ 右側；$80<84$，放在 $84$ 左側；$77<80$，放在 $80$ 左側。
6. $90>84$，放在 $84$ 右側；$95>90$，放在 $90$ 右側。

建出的樹如下：

             50                 第 1 層
           /    \
         15      84             第 2 層
        /  \    /  \
      11   22  80   90          第 3 層
     /         /       \
    3         77        95      第 4 層
   /
  2                            第 5 層

最深的節點是 $2$。從根節點 $50$ 到 $2$ 經過 $4$ 條邊，所以其層級為 $4+1=5$。其他葉節點 $77$、$95$ 都在第 4 層。

關鍵程式碼與複雜度

以下程式依序插入鍵值，並以遞迴計算樹的最大層數：

核心觀念

霍夫曼編碼（Huffman coding）是一種依字元出現頻率建立的最佳前綴碼。每次取出頻率最小的兩個節點，合併成頻率為兩者總和的新節點，直到只剩一個根節點。

若字元 $c$ 的頻率為 $f_c$，其霍夫曼碼長度為 $\ell_c$，總位元數為：

也可以直接將每次合併產生的新節點頻率加總，得到相同的總位元數。每次合併都會讓合併內兩個子樹中的每個字元多增加一個碼元，因此合併頻率正好是這次增加的位元數。

解題方法

將所有頻率放入最小堆積，每次取出最小的兩個頻率並合併：

因此，總位元數等於所有新頻率的總和：

可用碼長度加權和驗算。依照上述合併順序，各字元的碼長度如下：

核心觀念

雜湊函數會把鍵值映射到雜湊表索引。本題的雜湊函數為

當不同字串映射到相同索引時，就發生碰撞。

解題方法

四個字串都是 abcdef 的字元輪替，因此每個字串都包含 a 到 f 各一次，ASCII 值總和相同：

計算雜湊索引：

核心觀念

雜湊函數會把字串映射到雜湊表的索引。若兩個不同字串得到相同索引，就發生一次碰撞。本題的雜湊函數為

其中 $i$ 是字元在字串中的位置，從 $1$ 開始計算。要計算碰撞數，只需找出四個字串各自的索引，再檢查是否有重複索引。

解題方法

依照各字串中每個字元的位置，將 ASCII 值乘上位置權重後加總，再取模 $11$。

「abcdef」

「bcdefa」

「cdefab」

核心觀念

這題考的是 for 迴圈的執行範圍，以及等差級數求和。每次迴圈都會把目前的 $i$ 加到 sum 中；題目片段沒有寫出 sum 的宣告，依題意它是用來累加的變數，初始值為 $0$（若初值為 $s_0$，輸出就是 $s_0+46$）。

解題方法

當 $n=4$ 時，第一個迴圈從 $i=1$ 執行到 $i=2n=8$，累加 $1$ 至 $8$：

第二個迴圈從 $i=n=4$ 倒數至 $i=1$，累加 $4$ 至 $1$：

因此輸出為：

關鍵程式碼與複雜度

核心觀念

本題考查迴圈的執行次數與漸進時間複雜度。若每次迴圈執行的工作量為常數，執行 $k$ 次的迴圈需要 $\Theta(k)$ 時間；依序執行的程式，其總時間是各部分時間的總和。

解題方法

第一個迴圈的索引從 $1$ 遞增至 $2n$，因此執行 $2n$ 次：

第二個迴圈的索引從 $n$ 遞減至 $1$，因此執行 $n$ 次：

兩個迴圈依序執行，再加上最後輸出的常數時間，總時間為：

核心觀念

最小成本生成樹（MST）要在連通圖中選出連接所有頂點、且不含環的邊，使總權重最小。含 $V$ 個頂點的生成樹恰有 $V-1$ 條邊；Kruskal 演算法依邊權重由小到大檢查，只有在加入後不會形成環時才選取。

解題方法

圖中有六個頂點 $1$ 至 $6$，邊與權重為：$1\!-\!6:2$、$2\!-\!4:2$、$3\!-\!4:3$、$5\!-\!6:4$、$1\!-\!5:5$、$2\!-\!3:5$、$2\!-\!6:6$、$1\!-\!2:7$、$3\!-\!6:8$。依 Kruskal 演算法由小到大選邊：

核心觀念

主定理用來分析形如

的遞迴式。先比較非遞迴項 $f(n)$ 與臨界項 $n^{\log_b a}$：

• 若 $f(n)$ 與 $n^{\log_b a}$ 同階，主定理第二種情況給出 $T(n)=\Theta(n^{\log_b a}\log n)$。
• 此處假設 $T(1)=\Theta(1)$，且 $n$ 足夠大。

解題方法

本題中 $a=2$、$b=4$，而 $f(n)=\sqrt n$。計算臨界項：

核心觀念

主定理（Master Theorem）適用於形式為

的遞迴式，其中 $a\ge 1$、$b>1$ 為常數。本題的遞迴呼叫是 $T(n-1)$，問題規模每次減少 $1$，不符合主定理的分治形式，因此不能直接套用主定理。

解題方法

假設基底條件為 $T(1)=\Theta(1)$。逐層展開遞迴式：

因此，只需估計總和 $\sum_{k=2}^{n} k\lg k$。

先給上界。對所有 $k\le n$，都有 $k\lg k\le n\lg n$；總共至多 $n$ 項，所以

核心觀念

本題考察主定理（Master Theorem）。對遞迴式

先比較 $f(n)$ 與 $n^{\log_b a}$。本題中 $a=3$、$b=4$，且 $f(n)=n\lg n$。

解題方法

先計算遞迴子問題所對應的基準項：

因為 $\log_4 3<1$，可取 $\varepsilon=1-\log_4 3>0$。因此：

接著檢查主定理第三種情況所需的正則條件：

核心觀念

這題考查主定理（Master Theorem），特別是遞迴式中非遞迴成本與臨界項同階、且多出對數因子的情況。

對遞迴式

先比較 $f(n)$ 與臨界項 $n^{\log_b a}$。若

則主定理的延伸形式給出

解題方法

本題中 $a=4$、$b=2$，因此臨界項為

非遞迴成本是

它與臨界項同階，並多出一個 $\lg n$ 因子，符合上述主定理延伸形式，取 $k=1$，得到

核心觀念

主定理（Master Theorem）適用於

先比較非遞迴成本 $f(n)$ 與臨界函數 $n^{\log_b a}$。本題中 $a=7$、$b=2$、$f(n)=\Theta(n^2)$，因此臨界函數為

解題方法

因為 $2^2=4<7<8=2^3$，所以 $2<\log_2 7<3$，進而有

核心觀念

問題考查多項式時間多對一歸約與 NP 完全的定義。

若問題 $A$ 可在多項式時間歸約到問題 $B$，記作 $A\leq_p B$，表示存在一個多項式時間可計算的轉換 $f$，使得對每個輸入 $x$：

若 $A$ 是 NP 完全問題，且 $A\leq_p B$，便能推出 $B$ 至少和所有 NP 問題一樣難，因此 $B$ 是 NP-hard。但要稱 $B$ 為 NP-complete，還必須證明 $B\in\mathrm{NP}$。

解題方法與敘述判斷

題目只給出「某個 NP 完全問題可多項式時間歸約到 $L$」，沒有提供 $L\in\mathrm{NP}$ 的條件。因此，只能確定 $L$ 是 NP-hard，不能直接確定 $L$ 是 NP 完全。

反例可取停機問題 $HALT$。可將任一布林公式 $\varphi$ 在多項式時間內轉換成一台機器：它依序檢查變數的指派，若找到滿足 $\varphi$ 的指派就停機。於是：

核心觀念

採用標準的多項式時間 many-one 歸約：$A\le_p B$ 表示存在一個可在多項式時間內計算的函數 $f$，使得對每個輸入 $x$，

這表示只要能在多項式時間內判定 $B$，就能先計算 $f(x)$，再判定 $f(x)$ 是否屬於 $B$，進而在多項式時間內判定 $A$。因此，歸約能推出的方向是：

解題方法

題目給的是 $A\in P$，但要推出的是 $B\in P$。這和歸約的推論方向相反，不能由 $A$ 可有效判定，就斷定 $B$ 也可有效判定。

可用反例直接否定此敘述：令 $A=\varnothing$，即不包含任何字串的問題。因為每個輸入都不屬於 $A$，判定 $A$ 只需固定回答「否」，所以 $A\in P$。

核心觀念

$P$ 是可由確定型演算法在多項式時間內判定的問題類別；$NP$ 是可由非確定型演算法在多項式時間內判定的問題類別。等價地，若答案為「是」，$NP$ 中的問題能在多項式時間內驗證一份多項式長度的證明。

解題方法

若 $A\in P$，就存在一個確定型多項式時間演算法 $D$，能判定任意輸入 $x$ 是否屬於 $A$。要證明 $A\in NP$，可以直接讓非確定型演算法執行 $D$；因為確定型演算法也是非確定型演算法的一種特例，執行時間仍是多項式時間。

核心觀念

近似演算法通常要求在多項式時間內，輸出一個可行解，且解的成本不超過最佳解的固定倍數。對最小化問題而言，$2$-近似演算法必須滿足：

「一般旅行推銷員問題」不要求邊權重滿足三角不等式。這點很重要：不具三角不等式時，任意兩點間的成本可能遠高於繞路成本，不能直接套用度量旅行推銷員問題的近似保證。

解題方法

從哈密頓迴圈問題歸約。給定一張有 $n$ 個頂點的無向圖 $G$，建立一個含相同 $n$ 個頂點的完全圖：

• 若兩頂點在 $G$ 中有邊，令其旅行成本為 $1$。
• 若兩頂點在 $G$ 中沒有邊，令其旅行成本為 $2n+1$。

若 $G$ 有哈密頓迴圈，該迴圈在新圖中的成本是 $n$，所以最佳旅行成本為 $n$。假設存在 $2$-近似演算法，它輸出的旅行成本至多為 $2n$。

核心觀念

二元堆積（binary heap）是一棵完全二元樹：除最後一層外，各層皆滿；最後一層由左至右排列。樹的「高度」通常定義為根到最深節點所經過的邊數，因此根的高度為 $0$。

解題方法

高度為 $h$ 時，最深的一層是第 $h$ 層。若每層都填滿，各層節點數依序為 $1,2,4,\ldots,2^h$，所以最大節點數為：

核心觀念

這題考「交錯字串」的動態規劃。$z$ 是 $x$ 與 $y$ 的 shuffle，表示 $x$、$y$ 的所有字元都要出現在 $z$ 中，而且各自原有的先後順序必須保留。

題目定義：

當且僅當 $z$ 的前 $i+j$ 個字元，能由 $x$ 的前 $i$ 個字元與 $y$ 的前 $j$ 個字元交錯組成。

若 $S[i][j]$ 成立，最後一個字元 $z[i+j-1]$ 必須來自 $x$ 或 $y$：

• 若來自 $x$，必須有 $x[i-1]=z[i+j-1]$，且前面的部分符合 $S[i-1][j]$。
• 若來自 $y$，必須有 $y[j-1]=z[i+j-1]$，且前面的部分符合 $S[i][j-1]$。

解題方法

先檢查長度是否相符。交錯後的字串長度必須滿足 $r=n+m$；長度不同即可直接回傳 false。

初始化邊界時：

• $S[i][0]$ 只使用 $x$ 的字元，因此必須從 $S[i-1][0]$ 延續，並確認 $x[i-1]$ 與 $z[i-1]$ 相同。
• $S[0][j]$ 只使用 $y$ 的字元，因此必須從 $S[0][j-1]$ 延續，並確認 $y[j-1]$ 與 $z[j-1]$ 相同。

核心觀念

Floyd–Warshall 是計算所有頂點配對最短路徑的動態規劃演算法。它逐一把頂點 $k$ 納入可作為中繼點的集合，更新每一對頂點 $(i,j)$ 的最短距離：

解題方法

圖中是頂點 $1$ 至 $6$ 的有向加權圖；本小題問演算法的時間複雜度，與圖上實際的邊權值無關。演算法有三層迴圈：依序選擇中繼點 $k$，再枚舉起點 $i$ 與終點 $j$。

核心觀念

本題考 Floyd–Warshall 演算法的動態規劃遞迴式。$d_{ij}^{(k)}$ 表示從頂點 $i$ 到頂點 $j$，且所有中間頂點都只能取自 $\{1,2,\ldots,k\}$ 時的最短路徑長度。

解題方法

原圖是頂點 $1$ 至 $6$ 的有向加權圖。本小題要求的是通用遞迴式，圖上的邊權不需代入計算。

考慮最短路徑是否經過頂點 $k$ 作為中間頂點：

• 若不經過 $k$，路徑中間頂點只在 $\{1,\ldots,k-1\}$，長度為 $d_{ij}^{(k-1)}$。
• 若經過 $k$，路徑可拆成 $i$ 到 $k$、再由 $k$ 到 $j$ 兩段；

核心觀念

本題考有向圖的最短路徑。Floyd–Warshall 允許邊權為負時，仍可求所有點對的最短距離；前提是圖中沒有負權重環。其遞迴式為

時間複雜度為 $O(|V|^3)$，空間複雜度為 $O(|V|^2)$。

解題方法

圖中與計算相關的有向邊為：$1\to5$ 權重 $-1$、$2\to1$ 權重 $1$、$2\to4$ 權重 $2$、$3\to2$ 權重 $2$、$3\to6$ 權重 $-8$、$4\to1$ 權重 $-4$、$4\to5$ 權重 $3$、$5\to2$ 權重 $7$、$6\to2$ 權重 $5$、$6\to3$ 權重 $10$。

從終點 5 反向計算各點到 5 的最短距離。由圖可得：