110 年 國立中央大學資訊工程學系碩士班《資料結構與演算法》

核心觀念

中序轉後序時，運算元直接輸出；運算子依優先順序與結合性進入或離開堆疊。括號左括號會留在堆疊中，遇到右括號時，先輸出左括號上方的運算子，再移除左括號。

優先順序為乘除高於加減；同一優先順序的運算子依左結合處理。堆疊中的「項目數」包含尚未輸出的運算子與左括號。

解題方法

掃描中序式，追蹤運算子堆疊。選項（A）與（D）要檢查整個掃描過程中的堆疊最大深度；（B）直接依照運算子優先順序與左結合性轉換；（C）則從後序式逐一取出運算子，依序合併運算元或子式。

選項分析

（A）正確。

掃描 $a*(b+c/d)*(e-f)+g$ 時，進入 $b+c/d$ 這段後，堆疊依序為：

• 讀到第一個 $*$：堆疊為 $[*]$。
• 讀到左括號：堆疊為 $[*,(]$。
• 讀到 $+$：堆疊為 $[*,(,+]$。
• 讀到 $/$：因為除法優先順序高於加法，直接推入堆疊，成為 $[*,(,+,/]$。

此時堆疊共有 $4$ 個項目。右括號會依序彈出 $/$ 與 $+$，並移除左括號；後續的 $(e-f)$ 與末尾的 $+g$ 都不會使堆疊超過 $4$ 個項目。因此最多有 $4$ 個項目，敘述正確。

（B）錯誤。

括號內的減法與加法同優先順序，依左結合性計算：

$$(a+b-c)=(a+b)-c$$

核心觀念

AVL 樹是高度平衡的二元搜尋樹。對每個節點，左右子樹高度差必須符合

$$|h_L-h_R|\leq 1$$

因此，AVL 樹不要求左右子樹高度完全相同。AVL 樹的高度為 $O(\log n)$，所以搜尋與插入的時間複雜度為 $O(\log n)$；刪除也需要沿樹高往上檢查並修復平衡，時間複雜度為 $O(\log n)$。

解題方法

逐項檢查選項是否符合 AVL 樹的平衡條件、操作成本與最少節點數性質。特別注意，題目問的是哪些敘述「錯誤」，而高度平衡代表高度差至多為 $1$，並非一定為 $0$。

選項分析

(A) 錯誤。 刪除鍵值 $k$ 時，先沿搜尋路徑找到節點，耗時 $O(\log n)$。刪除後，平衡可能沿著從該節點到根的路徑逐層失衡，需要往上檢查並旋轉修復。因此刪除的時間複雜度是 $O(\log n)$，不是 $O(1)$。

核心觀念

WBLT（weight-biased leftist tree，重量偏斜左偏樹）同時滿足：

1. 堆積順序：最大堆中，每個父節點的鍵值都不小於其子節點。
2. 重量偏斜條件：對每個內部節點 $y$，
   $w(\mathrm{LeftChild}(y))\geq w(\mathrm{RightChild}(y)),$
   其中 $w(x)$ 是以 $x$ 為根的子樹內部節點數，外部節點的重量為 $0$。

重量偏斜條件限制的是沿著最右路徑能走多深；它不限制左子樹的高度，因此不能直接推論整棵子樹的高度也是對數級。

解題方法

沿最右路徑考察任一內部節點 $y$。令其右子節點為 $r$。由於左子樹重量至少與右子樹相同，

$$w(y)=1+w(\mathrm{LeftChild}(y))+w(r)\geq 1+2w(r).$$

因此，每往右走一層，子樹重量至少縮小一半。若最右路徑上有 $k$ 個內部節點，反覆套用上式可得

$$w(x)\geq 2^k-1,$$

所以

$$k\leq \log_2(w(x)+1).$$

這能驗證最右路徑的長度界，也說明合併操作只需沿著受限的最右路徑進行。至於整體高度，左子樹可以很高，重量條件並未排除這種情況。

選項分析

核心觀念

本題考遞迴函式的效率、終止性分析與手動追蹤。

選項分析

• (A) 正確。 一般而言，遞迴版本每次呼叫都要建立堆疊框（保存參數、區域變數、返回位址），有額外的呼叫開銷與 $O(\text{遞迴深度})$ 的堆疊空間，時間與空間效率通常比對應的迭代版本差。

• (B) 正確。 偶數輸入直接回傳 $x/2$；只需檢查奇數 $x$。把 $x+1$ 寫成 $x+1=2^k m$（$m$ 奇數，$k\ge1$）。

  對奇數 $x$，$F1(x)=F1(F1(3x+1))$。因為 $3x+1$ 是偶數，$F1(3x+1)=\dfrac{3x+1}{2}$，所以

  $$F1(x)=F1(y),\qquad y=\frac{3x+1}{2},\qquad y+1=\frac{3(x+1)}{2}=3\cdot2^{k-1}m .$$
  • 若 $k=1$：$y+1=3m$ 是奇數，所以 $y$ 是偶數，$F1(y)=y/2$ 直接回傳，遞迴結束。

核心觀念

在 C 語言中，arr 是二維陣列 int arr[5][5]。運算式中的 arr 會轉成「指向一列 5 個整數的指標」，型別為 int (*)[5]。因此，arr + i 前進的是 $i$ 列，而不是 $i$ 個整數。

常用規則是：

• *(arr + i) 表示第 $i$ 列，使用時會轉成指向該列第一個元素的指標。
• a[b] 等價於 *(a + b)。
• arr[i][j] 等價於 *(*(arr + i) + j)。

所以 arr[3][2] 是第 3 列、第 2 欄的元素。

解題方法

將各選項改寫成列與欄的索引，並確認每次指標運算的型別與位置。陣列索引從 0 開始；合法範圍是列、欄索引皆介於 0 到 4。

選項分析

• (A) *(*(arr+17))：錯誤。
  arr + 17 是指向第 17 列的指標，已超出 arr 的 5 列範圍。即使依指標型別展開，*(*(arr+17)) 對應第 17 列第 0 欄，並非 arr[3][2]；此運算也超出陣列範圍，行為未定義。

核心觀念

題目比較輸入（PUSH）與輸出（POP）的先後順序，判斷能否由佇列（Queue）或堆疊（Stack）產生。PUSH 順序固定為 $1,2,3,4$（或題目指定的序列），但 PUSH 與 POP 可以交錯進行。

• 佇列遵守先進先出（FIFO）：每次 POP 都取出目前最早 PUSH、尚未 POP 的元素。
• 堆疊遵守後進先出（LIFO）：每次 POP 都取出目前最後 PUSH、尚未 POP 的元素。

因此，只要排出一組符合規則的 PUSH／POP 操作順序，就能證明該序列「可以」由該資料結構產生。

解題方法

逐一檢查每個 POP 序列：

1. 依序讀取目標 POP 順序。
2. 依資料結構規則安排 PUSH 與 POP。
3. 若能安排出完整操作順序，該結構就能產生此序列。
4. 特別注意選項中的 must be，它表示「必定是」；只要另一種結構也能產生該序列，這個說法就不成立。

選項分析

(A) PUSH $1,2,3,4$；POP $1,2,3,4$：It must be a Queue.

這個序列可以由佇列產生，但也可以由堆疊產生。例如：

$$\operatorname{PUSH}(1),\ \operatorname{POP}(1),\ \operatorname{PUSH}(2),\ \operatorname{POP}(2),\ \operatorname{PUSH}(3),\ \operatorname{POP}(3),\ \operatorname{PUSH}(4),\ \operatorname{POP}(4)$$

每次堆疊中都只有一個元素，因此堆疊也能依序輸出 $1,2,3,4$。「必定是佇列」不成立，此選項為假。

(B) PUSH $1,2,3,4$；POP $2,1,3,4$：It must be a Stack.

堆疊可以這樣操作：

核心觀念

$h(k,i)=(k+i)\bmod 17$ 是**線性探測（linear probing）**的開放定址雜湊。刪除時不能直接把格子清空——否則同一個探測鏈（cluster）中位於它之後的鍵，查找時會在這個空格提前停止而「找不到」。正確作法是刪除後，把該 cluster 後面的鍵依序檢查：若某鍵的探測路徑經過剛空出的格子，就把它往前移到該空格，再以它留下的新空格繼續檢查，直到遇到真正的空格。

解題方法

1. 依序插入（括號內為 $k \bmod 17$）：

鍵	起始位置	最後位置
23	6	6
12	12	12
34	0	0
46	12	13
28	11	11
11	11	14（11、12、13 已滿）
6	6	7
7	7	8
0	0	1
33	16	16
30	13	15（13、14 已滿）
45	11	2（11～16、0、1 都滿，繞回）

插入後：位置 0:34、1:0、2:45、6:23、7:6、8:7、11:28、12:12、13:46、14:11、15:30、16:33。位置 11～2（繞回）是一整串連續的 cluster。

核心觀念

QuickSort 每次選定 pivot，將其餘紀錄分成左右兩個子問題，再加上一次分割所需的線性時間。因此遞迴式具有以下形式：

$$T(n)=T(k)+T(n-k-1)+cn$$

其中 $k$ 是 pivot 左側的紀錄數，$cn$ 表示分割成本。

• 最佳情況：每次分割都接近平分，遞迴式約為 $T(n)=2T(n/2)+cn$，時間複雜度為 $\Theta(n\log n)$。
• 最壞情況：每次 pivot 都落在一端，遞迴式為 $T(n)=T(n-1)+cn$，時間複雜度為 $\Theta(n^2)$。

解題方法

逐項檢查遞迴式是否符合 QuickSort 的分割方式，以及題目指定的最佳或最壞情況。QuickSort 一次分割只會產生左右兩個遞迴子問題，且兩者大小總和為 $n-1$。

選項分析

(A) 錯誤。
$T(n)=2T(n/2)+cn$ 描述左右子問題大小接近平分的情況，屬於最佳情況的典型遞迴式，並非最壞情況。最壞情況應是一個子問題大小為 $n-1$，另一個子問題為空。

核心觀念

反轉單向鏈結串列的標準三指標法：P（previous，已反轉部分的頭）、C（current，目前處理的節點）、N（next，暫存下一個節點）。每一輪把目前節點的 next 改指向前一個節點，然後三個指標一起往前推進一格。

解題方法

void reverse(NPtr *HRef) {
    NPtr P = NULL, C = *HRef, N = NULL;
    while (C != NULL) {      // (1) 還有節點沒處理
        N = C->next;         // 先記住下一個節點
        C->next = P;         // 反轉目前節點的指標
        P = C;               // P 前進到目前節點
        C = N;               // C 前進到下一個節點
    }
    *HRef = P;               // (2) 迴圈結束時 C 為 NULL，P 是新的頭
}

核心觀念

AOE 網路中，頂點代表事件，邊代表活動；邊上的 dur 是活動所需時間。事件 $i$ 的最早發生時間 $ve(i)$，取所有前置活動完成時間的最大值；事件的最晚發生時間 $vl(i)$，則由終點向前回推，取所有後續活動所允許時間的最小值。

若一條由起點到終點的路徑總工期等於整個網路的工期，這條路徑就是關鍵路徑。

解題方法

圖中從頂點 $0$ 到 $8$ 的活動為：$0\to1$（5）、$0\to2$（4）、$0\to3$（5）、$1\to4$（2）、$2\to4$（3）、$3\to5$（2）、$4\to6$（9）、$4\to7$（7）、$5\to7$（5）、$6\to8$（2）、$7\to8$（5）。表中的 count 是各事件的前置活動數，可用來確認前置關係。

先由起點往後計算最早發生時間：

核心觀念

本題考查 多項式時間歸約的傳遞性，以及 NP-complete 的定義。

依題目定義，$X_1 \propto X_2$ 表示可透過一個能解決 $X_2$ 的多項式時間演算法，在多項式時間內解決 $X_1$。NP-complete 的問題必須同時滿足：

1. $D\in\mathrm{NP}$；
2. 每一個 NP 問題都能在多項式時間內歸約至 $D$。

解題方法

題目已給定：

$$\mathrm{SAT}\propto B,\qquad B\propto C,\qquad C\propto D,\qquad D\in\mathrm{NP}.$$

多項式時間歸約具有傳遞性，因此把連續的歸約串接起來，可得：

$$\mathrm{SAT}\propto D.$$

依 Cook 定理，每一個 NP 問題都能在多項式時間內歸約至 SAT。任取 $X\in\mathrm{NP}$，便有：

$$X\propto\mathrm{SAT}.$$

再利用歸約的傳遞性：

核心觀念

本題考查 NP 完全問題的定義。依題目定義，問題 $X$ 為 NP 完全問題，必須同時滿足：

1. $X\in\mathrm{NP}$。
2. 每一個 NP 問題都能多項式時間歸約到 $X$。

因此，若 $X_2$ 是 NP 完全問題，任何屬於 NP 的問題都能多項式時間歸約到 $X_2$。

解題方法

令 $X_1$、$X_2$ 都是 NP 完全問題。由於 $X_1$ 是 NP 完全問題，依定義可知 $X_1\in\mathrm{NP}$。

又因為 $X_2$ 是 NP 完全問題，所有 NP 問題都能多項式時間歸約到 $X_2$。而 $X_1$ 屬於 NP，所以：

$$X_1\propto X_2$$

核心觀念

本題考查 NPC 的定義與多項式歸約的傳遞性。依題目定義，若問題 $Y$ 是 NP 問題，且 $Y \propto X$，代表可透過一個多項式時間的歸約程序，使用 $X$ 的解題演算法解決 $Y$。

NPC 問題 $X$ 同時滿足：

1. $X \in \mathrm{NP}$。
2. 每一個 NP 問題都可多項式時間歸約至 $X$。

解題方法

設 $X$ 是 NPC 問題，且題目假設 $X$ 有一個確定型多項式時間演算法。任取一個 NP 問題 $Y$。

由於 $X$ 是 NPC，依定義有：

$$Y \propto X$$

因此，可以先用多項式時間歸約程序，將 $Y$ 的問題轉成 $X$ 的問題，再執行 $X$ 的確定型多項式時間演算法，即可解決 $Y$。

核心觀念

題目要求從 $x$ 到 $y$ 找總權重最小的路徑。由於每條邊的權重皆非負，可使用 Dijkstra 演算法。

令 $d[v]$ 表示目前已知從 $x$ 到頂點 $v$ 的最短距離估計值。對每條邊 $(u,v)$，若經由 $u$ 到達 $v$ 比目前估計更短，就更新：

$$d[v]\leftarrow \min\bigl(d[v],\ d[u]+w(u,v)\bigr)$$

用前驅陣列記錄每次更新的來源頂點，便能在取得距離後重建路徑。

解題方法

使用鄰接串列儲存圖，並以最小優先佇列維護尚未確定最短距離的頂點。初始化 $d[x]=0$，其他頂點距離設為無限大。每次取出目前距離最小的頂點 $u$，鬆弛其所有相鄰邊。

當 $y$ 從優先佇列取出時，$d[y]$ 已是從 $x$ 到 $y$ 的最短距離，可以停止搜尋。若優先佇列清空後 $d[y]$ 仍為無限大，表示 $y$ 無法從 $x$ 到達。

核心觀念

最短路徑距離必須同時滿足兩個條件：

1. 沿每條邊都不能下降得太快：若邊 $(u,v)$ 的權重為 $w(u,v)$，則

   $$d[v]\le d[u]+w(u,v),\qquad d[u]\le d[v]+w(u,v).$$

   這兩個不等式表示候選距離不會大於任何從 $s$ 出發、沿邊走到該點的路徑長度。

2. 每個有限距離都能由一條路徑達到：對每個距離有限的頂點 $v$，必須存在一條從 $s$ 到 $v$ 的路徑，其長度恰為 $d[v]$。

只檢查邊的不等式還不夠：候選值可能比實際最短距離小，卻沒有任何路徑能達到它。因此還要檢查哪些頂點能透過「距離等式成立」的邊從 $s$ 抵達。

解題方法

將每條無向邊 $\{u,v\}$ 視為兩個方向。對有限距離的端點，若

$$d[u]+w(u,v)=d[v],$$

就把 $u\to v$ 視為一條緊密邊。這表示若已找到長度為 $d[u]$ 的路徑到達 $u$，再走這條邊即可得到長度為 $d[v]$ 的路徑到達 $v$。

接著依序執行：

1. 確認 $d[s]=0$，且所有有限的 $d[v]$ 都非負。
2. 掃描每條邊，檢查兩端是否同時為有限距離或同時為無限距離。若一端有限、另一端無限，宣告不正確。
3. 對有限距離的端點檢查兩個邊不等式。任一不成立，宣告不正確。
4. 從 $s$ 出發，只沿緊密邊搜尋。若搜尋到的頂點集合恰好等於所有 $d[v]$ 有限的頂點，宣告正確；否則宣告不正確。

無限距離以 $+\infty$ 表示，代表該頂點無法從 $s$ 抵達。第 2 步確保無限距離頂點不會與有限距離頂點位於同一連通分量。

正確性說明

若演算法宣告正確，搜尋到的每個有限距離頂點都能沿緊密邊從 $s$ 抵達。每走一條緊密邊 $u\to v$，都有 $d[v]=d[u]+w(u,v)$；由 $d[s]=0$，沿搜尋路徑加總可得該路徑長度恰為 $d[v]$。

另一方面，對任意從 $s$ 到有限距離頂點 $v$ 的路徑，邊不等式逐段相加可知 $d[v]$ 不大於該路徑長度。因此 $d[v]$ 不大於實際最短距離；而緊密邊搜尋找到一條長度為 $d[v]$ 的路徑，因此實際最短距離也不大於 $d[v]$。兩者相等。

所有無限距離頂點都不與 $s$ 所在連通分量相連，故確實不可由 $s$ 抵達。反之，若候選陣列是真正的最短距離，最短路徑上的每一段都可延伸成等長的最短路徑，所以每段對應的邊都會滿足緊密邊等式；搜尋必能抵達每個有限距離頂點，且邊不等式也都成立。

關鍵程式碼

以下以 INF 表示無限距離，adj[u] 儲存頂點 $u$ 的鄰接表，每個項目包含鄰點及邊權重。