108 年 國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《資料結構》

核心觀念

Stack（堆疊）遵循 後進先出（Last In, First Out, LIFO）原則。push 將資料放入堆疊頂端，pop 則從堆疊頂端取出最近加入的資料。

以陣列實作堆疊時，使用變數 top 記錄頂端元素位置：

• top = -1：堆疊為空
• top >= 0：堆疊非空
• 空堆疊執行 pop 時發生 underflow（下溢）

解題方法

執行 pop 必須依序完成以下動作：

1. 檢查堆疊是否為空。
2. 儲存頂端元素。
3. 將 top 往下移一格。
4. 回傳原本的頂端元素。

偽程式碼

假設堆疊以陣列 S[0 ... MAX-1] 表示，且 top 初始值為 $-1$：

POP(S, top)
    if top == -1 then
        report "Stack Underflow"
        return ERROR
    end if

    item ← S[top]
    top ← top - 1
    return item

若使用需要傳回更新後 top 的寫法，可表示為：

POP(S, top)
    if top < 0 then
        report "Stack Underflow"
    else
        item ← S[top]
        top ← top - 1
        return item
    end if

例如堆疊內容為：

$$[10,\ 20,\ 30]$$

核心觀念

本題考查單向鏈結串列中，已知某個節點指標時的刪除操作。

每個節點包含：

• data：節點資料
• next：指向下一個節點的指標

若只知道串列首指標 Head，通常需要從頭走訪，找到待刪節點的前一個節點，才能修改前驅節點的 next。

但本題額外給定 Mid，且明確指出它是中間節點，因此 Mid->next 必定存在。可採用以下技巧：

1. 將 Mid 下一個節點的資料複製到 Mid。
2. 讓 Mid 跳過原本的下一個節點。
3. 釋放原本的下一個節點。

如此即可在不知道前驅節點的情況下，刪除 Mid 所代表的串列元素。

---

解題方法

令：

struct Node *Temp = Mid->next;

原始結構如下：

前一節點 → Mid → Temp → 下一節點

先將 Temp 的資料複製到 Mid：

Mid->data = Temp->data;

此時邏輯上的資料已變成：

前一節點 → Mid(原 Temp 的資料) → Temp → 下一節點

再令：

Mid->next = Temp->next;

結構變成：

前一節點 → Mid(原 Temp 的資料) → 下一節點

最後釋放 Temp：

free(Temp);

原本 Mid 節點的位置仍然存在，但它已經承接下一個節點的資料，因此達成刪除 Mid 所代表元素的效果。

---

關鍵程式碼

核心觀念

Merge sort（合併排序）採用「分而治之」：

1. 將序列遞迴切成兩半。
2. 將左右子序列分別排序。
3. 以線性時間合併兩個已排序的子序列。

合併時，比較左右兩邊目前最前面的元素，將較小者放入結果序列，直到兩邊元素全部處理完畢。

其遞迴式為：

$$T(n)=2T\left(\frac{n}{2}\right)+\Theta(n)$$

其中 $2T(n/2)$ 代表排序左右兩半，$\Theta(n)$ 代表合併兩個已排序序列的成本。

---

解題方法與排序過程

原始序列為：

$$\{50,43,51,83,60,33,21\}$$

第一步：遞迴分割

依序切分為：

$$\{50,43,51,83,60,33,21\}$$ $$\rightarrow \{50,43,51\}\quad \{83,60,33,21\}$$

左半部繼續分割：

$$\{50,43,51\} \rightarrow \{50\}\quad \{43,51\} \rightarrow \{50\}\quad \{43\}\quad \{51\}$$

右半部繼續分割：

$$\{83,60,33,21\} \rightarrow \{83,60\}\quad \{33,21\}$$ $$\{83,60\}\rightarrow \{83\}\quad \{60\}$$ $$\{33,21\}\rightarrow \{33\}\quad \{21\}$$

分割至每個子序列只剩一個元素後，開始進行合併。

---

第二步：合併左半部

先合併：

$$\{43\}+\{51\}$$

比較 $43$ 與 $51$：

$$\{43,51\}$$

再合併：

$$\{50\}+\{43,51\}$$

比較過程：

• 比較 $50$ 與 $43$，取出 $43$
• 比較 $50$ 與 $51$，取出 $50$
• 剩餘 $51$，取出 $51$

因此：

$$\{50\}+\{43,51\} \rightarrow \{43,50,51\}$$

---

第三步：合併右半部

先合併：

$$\{83\}+\{60\}$$

因為 $60<83$，所以：

$$\{83\}+\{60\} \rightarrow \{60,83\}$$

再合併：

$$\{33\}+\{21\}$$

因為 $21<33$，所以：

$$\{33\}+\{21\} \rightarrow \{21,33\}$$

最後合併：

$$\{60,83\}+\{21,33\}$$

比較過程：

核心觀念

本題考查區塊鏈的核心密碼學技術：雜湊函數（Hash Function），實務上常以 SHA-256 為代表。

雜湊函數會將任意長度的輸入資料，轉換成固定長度的摘要值：

$$h = H(m)$$

其中：

• $m$：輸入資料，例如交易紀錄或區塊內容。
• $H$：雜湊函數。
• $h$：固定長度的雜湊值，亦稱摘要或指紋。

以 SHA-256 為例，不論輸入資料大小為何，輸出皆為 $256$ 位元的雜湊值，通常表示成 $64$ 位十六進位數字。

解題方法

區塊鏈中的每個區塊通常包含：

1. 多筆交易資料；
2. 前一個區塊的雜湊值；
3. 時間戳記；
4. Nonce 等欄位。

目前區塊的雜湊值可表示為：

$$Hash_i = H(Data_i \Vert Hash_{i-1} \Vert Nonce_i)$$

其中 $\Vert$ 表示資料串接。

因此，第 $i$ 個區塊會記錄第 $i-1$ 個區塊的雜湊值。若攻擊者修改早期區塊中的任一筆交易資料，該區塊的雜湊值就會改變，後續所有區塊所記錄的前一區塊雜湊值也會不一致，節點即可發現資料遭到竄改。

雜湊函數在區塊鏈中主要提供以下特性：

1. 單向性

由輸入 $m$ 計算 $H(m)$ 很容易，但僅由 $H(m)$ 反推出原始資料 $m$ 在計算上不可行。

2. 雪崩效應

輸入只要有一個位元改變，輸出的雜湊值就會產生大幅度變化，無法由輸出判斷輸入只做了微小修改。

3. 抗碰撞性

不同輸入產生相同雜湊值的情況稱為碰撞：

$$m_1 \ne m_2,\quad H(m_1)=H(m_2)$$

良好的密碼學雜湊函數應使尋找碰撞在計算上極為困難。

4. 固定長度輸出

輸入資料可以是任意長度，但輸出摘要長度固定，方便儲存、比對及串接區塊。

與工作量證明的關係

核心觀念

本題要求將二元樹進行左右翻轉（flip left-right），也稱為鏡像（mirror）。

對每一個節點而言，翻轉後必須滿足：

• 原本的左子樹變成右子樹。
• 原本的右子樹變成左子樹。
• 左、右子樹本身也必須繼續進行相同翻轉。

因此，這是一個典型的遞迴問題。其遞迴結構為：

$$\text{Flip}(T) = \begin{cases} \text{NULL}, & T=\text{NULL}\\ \text{翻轉左右子樹後交換}, & T\neq\text{NULL} \end{cases}$$

解題方法

設目前節點為 root。

處理順序如下：

1. 若 root == NULL，表示已到達空樹，直接返回。
2. 遞迴翻轉左子樹。
3. 遞迴翻轉右子樹。
4. 交換目前節點的 left 與 right 指標。
5. 返回翻轉後的樹根。

交換可以使用暫存指標完成：

$$temp = root.left$$ $$root.left = root.right$$ $$root.right = temp$$

關鍵程式碼

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
};

TreeNode* flip(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }

    flip(root->left);
    flip(root->right);

    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;

    return root;
}

此程式採用原地（in-place）翻轉，不建立新的節點，只調整原有節點的左右子樹指標。

遞迴流程範例

原始二元樹：

        A
       / \
      B   C
     / \   \
    D   E   F

遞迴處理完成後：

核心觀念

圖形（Graph）常見的儲存方式有兩種：

1. 鄰接矩陣（Adjacency Matrix）
2. 鄰接串列（Adjacency List）

設圖有 $V$ 個頂點、$E$ 條邊。

• 鄰接矩陣以二維陣列表示任兩個頂點之間是否相鄰。
• 鄰接串列為每個頂點建立一條串列，只記錄與該頂點直接相連的頂點。

本題重點是比較兩者的記憶體使用量，並說明圖形稀疏程度對空間效率的影響。

---

一、鄰接矩陣

定義

建立一個 $V \times V$ 的矩陣 $A$：

$$A[i][j] = \begin{cases} 1, & \text{頂點 } i \text{ 與頂點 } j \text{ 有邊相連}\\ 0, & \text{頂點 } i \text{ 與頂點 } j \text{ 沒有邊相連} \end{cases}$$

若為加權圖，矩陣元素可直接儲存邊的權重。

記憶體需求

因為矩陣固定有 $V^2$ 個位置，所以空間複雜度為：

$$\boxed{O(V^2)}$$

即使圖中實際只有少量邊，沒有使用到的矩陣位置仍然必須保留，因此鄰接矩陣的空間需求與 $E$ 無直接關係。

優點

• 判斷兩個頂點是否直接相連非常快速，時間為 $O(1)$。
• 適合邊數很多的稠密圖（dense graph）。
• 矩陣結構簡單，實作容易。
• 進行 Floyd-Warshall 等矩陣型圖形演算法時較方便。

缺點

• 記憶體需求固定為 $O(V^2)$。
• 對於頂點很多但邊很少的稀疏圖（sparse graph），大量空間只存放不存在的邊。
• 列舉某一頂點的所有鄰居，必須掃描整列，時間為 $O(V)$。

---

二、鄰接串列

定義

對每個頂點建立一條串列，串列中記錄所有與該頂點相鄰的頂點。

例如，若有邊：

$$(1,2),\ (1,3),\ (2,4)$$

則可表示為：

• $1 \rightarrow 2,3$
• $2 \rightarrow 1,4$
• $3 \rightarrow 1$
• $4 \rightarrow 2$

記憶體需求

首先需要為 $V$ 個頂點建立串列標頭；每條邊則需要儲存其相鄰資訊。

對於有向圖，每條邊通常記錄一次，因此空間為：

$$O(V+E)$$