112 年 國立中央大學資訊管理學系碩士班甲組《資料結構》

核心觀念

• Max‑Heap：滿足「父節點 ≥ 子節點」的完全二元樹。常以陣列 $A[1\ldots n]$ 表示，父子關係為
  $\text{parent}(i)=\lfloor i/2 \rfloor,\ \text{left}(i)=2i,\ \text{right}(i)=2i+1$。
• 建構 Max‑Heap：可採「自底向上」的 heapify（$O(n)$）或「一次插入」的 $O(n\log n)$ 方法。題目要求「至少顯示初始樹與最終樹」，因此先依輸入順序列出原始二元樹（未調整），再執行自底向上 heapify。
• Heap Sort：重複把根節點（最大值）與最後一個節點交換，將根節點「下沉」至適當位置，最後得到遞減序列。一次排序（一次 extract‑max）會使堆大小減 1，根節點被交換至陣列尾端，剩餘的 $n-1$ 個元素仍保持 Max‑Heap 性質。

---

(a) 建構 Max‑Heap

1. 初始二元樹（依輸入順序填入陣列）

索引 $i$	1	2	3	4	5	6	7	8	9
元素	24	58	89	36	48	77	10	94	99

對應的樹形（左子右子）：

          24
       /      \
     58        89
    /  \      /  \
   36  48   77   10
  / \
 94 99

此時明顯違反 Max‑Heap（根節點 24 不是最大）。

2. 自底向上 Heapify
從最後一個非葉節點 $\lfloor n/2 \rfloor=4$ 開始向上執行 max‑heapify：

步驟	作用節點	子樹最大值	交換結果（陣列）
①	$i=4$ (36)	max(94,99)=99 → 99 > 36	36↔99 → [24,58,89,99,48,77,10,94,36]
②	$i=3$ (89)	max(77,10)=77 < 89 → 無交換	unchanged
③	$i=2$ (58)	max(99,48)=99 → 99 > 58	58↔99 → [24,99,89,36,48,77,10,94,58]
④	$i=2$ 再次下沉至 4 (36) → max(94,36)=94 > 36	36↔94 → [24,99,89,94,48,77,10,36,58]
⑤	$i=1$ (24)	max(99,89)=99 → 99 > 24	24↔99 → [99,24,89,94,48,77,10,36,58]
⑥	$i=1$ 再次下沉至 2 (24) → max(94,48)=94 > 24	24↔94 → [99,94,89,24,48,77,10,36,58]
⑦	$i=2$ 再次下沉至 4 (24) → max(36,58)=58 > 24	24↔58 → [99,94,89,58,48,77,10,36,24]

最終陣列：[99,94,89,58,48,77,10,36,24]

最終 Max‑Heap 樹形

(a) 合併排序步驟

原始序列：$[88,\;67,\;34,\;98,\;17,\;26,\;35,\;4,\;23,\;30]$

1. 第一次分割

   • 左半部 $L_1=[88,67,34,98,17]$
   • 右半部 $R_1=[26,35,4,23,30]$

2. 再次分割

   • $L_1\rightarrow L_{11}=[88,67]\;$、$\;L_{12}=[34,98,17]$
   • $R_1\rightarrow R_{11}=[26,35]\;$、$\;R_{12}=[4,23,30]$

3. 直至單元素

   • $[88,67]\rightarrow[88]\;$、$\;[67]$ → 合併 $\to[67,88]$
   • $[34,98,17]\rightarrow[34]\;$、$\;[98,17]\rightarrow[98]\;$、$\;[17]$ → 合併 $\to[17,98]$ → 再與 $[34]$ 合併 $\to[17,34,98]$
   • $[26,35]\rightarrow[26]\;$、$\;[35]$ → 合併 $\to[26,35]$

核心觀念

• 斐波那契數列：定義 $F_0 = 0,\;F_1 = 1$，對 $n \ge 2$ 有 $F_n = F_{n-1}+F_{n-2}$。
• 遞迴：直接使用函式呼叫自身，符合定義式，可展開為樹狀結構。
• 迴圈（非遞迴）：利用迭代方式累加前兩項，避免遞迴的重複計算。
• 停止條件：列印的最後一個斐波那契數必須 小於 1000，因此在產生下一項時需先檢查是否會超過 999。

---

解題方法

1. 遞迴版

   • 仍以「列印」為主流程：先列印 $F_0,F_1$，再呼叫遞迴函式 fibPrint(prev, cur)，其中 prev 為前一項、cur 為當前項。
   • 在每一次呼叫前檢查 cur < 1000，若不符合則結束遞迴。
   • 這樣的遞迴深度等於產生的斐波那契項數（約 $\log_{\phi}1000 \approx 16$），不會造成堆疊溢位。

2. 非遞迴版

   • 使用 while 迴圈，變數 a,b 分別代表前兩項。
   • 每次迭代列印 a，計算下一項 c = a + b，然後更新 a←b, b←c。
   • 迴圈條件同樣是 a < 1000，保證最後列印的數值小於 1000。

3. 時間/空間分析

   • 產生的項數 $k$ 滿足 $F_k < 1000 \le F_{k+1}$，實際 $k = 16$（$F_{16}=987$）。
   • 時間複雜度：兩種寫法皆為 $O(k)$，即 $O(1)$（常數）因 $k$ 固定。
   • 空間複雜度：遞迴版需保留遞迴呼叫棧，深度 $k$，故 $O(k)$；非遞迴版只用常數個變數，為 $O(1)$。

---

遞迴函式偽碼 (Recursive)

【核心觀念】

• 完整圖 (Complete Graph)：在圖論中，若一個無向簡單圖的每一對不同頂點之間皆存在一條邊，則此圖稱為完整圖（英文：complete graph），記作 $K_n$，其中 $n$ 為頂點數。
• 邊數公式：對於 $K_n$，每一頂點與其餘 $n-1$ 個頂點相連，但每條邊會被計算兩次（一次從 $u$ 到 $v$，一次從 $v$ 到 $u$），故實際的邊數為
  $|E(K_n)|=\frac{n(n-1)}{2}.$

---

【解題方法】

(a) 完整圖的定義

1. 圖 $G=(V,E)$ 為無向簡單圖（不允許自迴路與多重邊）。
2. 若對所有 $u,v\in V$，且 $u\neq v$，都有邊 $\{u,v\}\in E$，則 $G$ 為完整圖。
3. 常以 $K_n$ 代表 $n$ 個頂點的完整圖。

核心觀念

• 圖的遍歷：在一個無向或有向圖 $G=(V,E)$ 中，遍歷的目標是從起始節點 $s\in V$ 依照某種規則訪問所有與 $s$ 可達的節點。
• 資料結構：
  • Breadth‑First Search (BFS) 使用 先進先出 (FIFO) 队列 來記錄待拜訪的節點。
  • Depth‑First Search (DFS) 使用 後進先出 (LIFO) 堆疊，或以遞迴方式隱式利用程式呼叫堆疊。
• 遍歷性質：
  • BFS 能夠保證先拜訪離起點最短路徑長度的節點，適合找最短路徑問題。
  • DFS 則會盡可能深入一條路徑，適合檢測連通性、拓撲排序、強連通分量等。

---

(a) Breadth‑First Search (BFS)

解題方法

1. 初始化
   • 建立一個佇列 Q，將起始節點 $s$ 入佇列。
   • 設 $visited[s] \leftarrow true$，其他節點皆為 false。
2. 迭代
   • 當 Q 非空時，取出佇列首端節點 $u$。
   • 依序檢查 $u$ 的所有相鄰節點 $v\in Adj(u)$：
     • 若 $visited[v]=false$，則 $visited[v]\leftarrow true$，並把 $v$ 加入佇列 Q。
3. 終止
   • 佇列空即遍歷完成；所有可達節點皆已按距離層次（層序）被拜訪。

範例

考慮圖 $G$（無向）：

   1 —— 2 —— 5
   | \  |
   3   4

以 $s=1$ 為起點執行 BFS：

步驟	佇列 Q	已拜訪節點 (visited)
初始	[1]	{1}
1	[2,3,4]	{1,2,3,4}
2	[3,4,5]	{1,2,3,4,5}
3	[4,5]	{1,2,3,4,5}
4	[5]	{1,2,3,4,5}
5	[]	{1,2,3,4,5}

拜訪順序為 1 → 2 → 3 → 4 → 5，即層序遍歷。

关键程式碼（C++ 標準庫）

vector<int> bfs(const vector<vector<int>>& adj, int s) {
    int n = adj.size();
    vector<int> order;                 // 記錄拜訪順序
    vector<bool> visited(n, false);
    queue<int> q;

    visited[s] = true;
    q.push(s);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    return order;
}

時間與空間複雜度

• 時間：每條邊至多檢查一次，故 $O(|V|+|E|)$。

核心觀念

• 雜湊函式的安全性基礎為三大屬性：Pre‑image resistance（給定雜湊值找原始訊息）、Second‑pre‑image resistance（給定訊息找另一個產生相同雜湊值的訊息）以及Collision resistance（任意兩個不同訊息產生相同雜湊值的難度）。
• MD5 產生 128‑bit（$2^{128}$）的雜湊值。根據生日悖論，在隨機雜湊函式下，約需要 $2^{64}$ 個不同訊息才會出現 50 % 的碰撞機率。
• 1990‧年代所設計的 MD5 已被證實可在可行計算量內構造碰撞，且還存在長度延伸攻擊（length‑extension）等結構性漏洞。

---

解題方法

1. 辨識題意：題目問「使用 MD5 處理大量資料，其輸出可能有哪些潛在弱點？」屬於概念性簡答題，重點在於說明 MD5 在大規模應用時的碰撞危險與長度延伸兩大問題。
2. 說明碰撞風險
   • 計算理論碰撞門檻：當資料筆數 $n \approx 2^{64}$ 時，依生日悖論 $\Pr(\text{collision}) \approx 1 - e^{-n^2/(2\cdot2^{128})} \approx 0.5$。
   • 實務上，已有人利用 MD5 的結構缺陷在 $2^{20}$–$2^{30}$ 次運算內生成可預測的碰撞，遠低於理論門檻。
   • 大量資料（如備份、檔案系統、分散式快取）往往超過數億筆，碰撞機率急速提升，會導致資料完整性驗證失效，攻擊者可替換原始檔案而不被偵測。
3. 說明長度延伸攻擊

(a) Quick Sort 過程（使用 Lomuto partition，基準為最後一個元素）

1. 初始序列
   $A = [75,40,61,23,54,12,98,86]$

2. 第一層：基準 $p=86$（$A[7]$）

   • 依序比較 $A[0\sim6]$，全部 $\le 86$，故 $i$ 最終為 $5$。
   • 交換 $A[i+1]$ 與基準：$98 \leftrightarrow 86$
   • 結果 $[75,40,61,23,54,12,\boxed{86},98]$，基準位於索引 $6$。

3. 左子序列 $A[0\sim5]$：基準 $p=12$（$A[5]$）

   • 所有元素均 $>12$，$i$ 保持 $-1$。
   • 交換 $A[0]$ 與基準：$75 \leftrightarrow 12$
   • 結果 $[\boxed{12},40,61,23,54,75,86,98]$，基準位於索引 $0$。

4. 右子序列 $A[1\sim5]$：基準 $p=75$（$A[5]$）

   • $40,61,23,54 \le 75$，最終 $i=4$。
   • 交換 $A[i+1]$ 與基準（同位） → 不變。
   • 結果 $[12,\boxed{40},61,23,54,75,86,98]$，基準位於索引 $5$。

5. 子序列 $A[1\sim4]$：基準 $p=54$（$A[4]$）

   • $40 \le 54$ → $i=1$。
   • $61 > 54$ → 無動作。
   • $23 \le 54$ → $i=2$，交換 $A[2] (61)$ 與 $A[3] (23)$ →
     $[12,40,23,61,54,75,86,98]$
   • 交換 $A[i+1] (61)$ 與基準 $54$ →
     $[12,40,23,\boxed{54},61,75,86,98]$，基準索引 $3$。

6. 子序列 $A[1\sim2]$：基準 $p=23$（$A[2]$）

   • $40 > 23$ → $i$ 不變。
   • 交換 $A[i+1] (40)$ 與基準 $23$ →
     $[12,\boxed{23},40,54,61,75,86,98]$，基準索引 $1$。

7. 其餘子序列長度 $\le1$，停止遞迴。

最終升序結果
$[12,23,40,54,61,75,86,98]$

---

(b) ANSI C Quick Sort 實作（關鍵步驟以註解說明）

核心觀念
本題測試考生對兩種排序演算法 Insertion Sort（插入排序）與 Quick Sort（快速排序）的時間複雜度概念的掌握。須能辨識它們在 最佳情況、平均情況、最壞情況 下的漸進上界（Big‑O 表示），並能以表格形式清楚呈現。

• Insertion Sort：依序將元素插入已排好序的子序列。

  • 最佳情況：輸入已全序（或近乎有序），每次插入只需 $O(1)$ 比較。
  • 平均／最壞情況：需將每個元素向左掃完整個已排好序的子序列，形成嵌套迴圈，時間為 $O(n^2)$。

• Quick Sort：以「分割」（partition）方式將陣列切成兩部份，遞迴排序。

  • 最佳情況：每次分割正好將陣列平分，遞迴深度 $\log_2 n$，每層處理 $O(n)$，總時間 $O(n\log n)$。
  • 平均情況：隨機選取基準值時，期望的分割比例仍接近均等，結果同上 $O(n\log n)$。
  • 最壞情況：基準值恰為最小或最大元素，導致分割極不平衡，遞迴深度 $n$，時間退化為 $O(n^2)$。

---

解題方法

1. 列出每種演算法的三種情況，依照上述概念寫出對應的 Big‑O。
2. 以 Markdown 表格呈現，行代表「情況」（最佳、平均、最壞），列分別為「Insertion Sort」與「Quick Sort」。
3. 如題目標示「(4%)」為本題在整份考卷的配分比例，僅在說明中註記，表格內不必列出分數。

---