114 年 國立中正大學電機工程學系碩士班計算機工程組《資料結構》

第 1 題：Hashing

核心觀念

IPv4 位址由 4 個位元組組成，共有

$$2^{32}=4,294,967,296$$

種可能的位址。雜湊表的工作是將 32 位元的 IP 位址轉換成較小的索引值，對應至有限個 bucket。

本題需要處理三個重點：

1. 將 IPv4 位址轉成整數型態的 key。
2. 設計能平均分散 key 的 hash function。
3. 使用碰撞處理方法，並依照資料量選擇合理的表格大小。

雜湊表的負載因子定義為

$$\alpha=\frac{n}{m}$$

其中 $n$ 是目前儲存的 IP 數量，$m$ 是 bucket 數量。負載因子越大，碰撞越頻繁，查詢時間也越長。

---

解題方法一：將 IPv4 轉成 32 位元整數

設 IPv4 位址為 a.b.c.d，其中每個欄位皆介於 $0$ 到 $255$，則可定義 key 為

$$K=(a\ll24)+(b\ll16)+(c\ll8)+d$$

也就是

$$K=a\times2^{24}+b\times2^{16}+c\times2^8+d$$

例如：

$$192.168.1.7$$

可轉換為

$$K=192\times2^{24}+168\times2^{16}+1\times2^8+7$$ $$K=3,232,235,783$$

將 IP 儲存成 32 位元整數比直接儲存字串有效率，因為：

• 每個不同的 IPv4 位址都有唯一的 $K$。
• 比較整數比比較字串快速。
• 不會受到字串格式差異影響。
• 雜湊函數可以同時使用所有 32 個位元。

---

解題方法二：儲存方式與碰撞處理

採用「分離鏈結法」處理碰撞。建立一個大小為 $m$ 的陣列：

$$T[0],T[1],\ldots,T[m-1]$$

每個陣列元素指向一條鏈結串列，串列節點包含：

Entry = (IP_key, value, next)

其中：

• IP_key：32 位元的 IP 整數。
• value：該 IP 所對應的資料，例如封包數量、使用者資訊或路由資料。
• next：指向同一 bucket 中下一筆資料。

插入或查詢時，先計算

$$i=h(K)$$

再到 $T[i]$ 所指向的鏈結串列中，以完整的 $K$ 進行比對。

即使兩個不同的 IP 產生相同的 hash 值，也能放在同一條鏈結串列中，因此不會遺失資料。分離鏈結法的優點是刪除資料簡單，也不需要保留大量空白槽位。

---

解題方法三：Hash function 設計

可使用隨機化的 universal hash function：

$$h(K)=\bigl((A K+B)\bmod p\bigr)\bmod m$$

其中：

• $p$ 是大於 $2^{32}$ 的質數，例如 $$p=4,294,967,311$$
• $A$ 是 $1$ 到 $p-1$ 之間隨機選取的整數。
• $B$ 是 $0$ 到 $p-1$ 之間隨機選取的整數。
• $m$ 是 hash table 的 bucket 數量。

實作乘法時，$A K+B$ 應使用足夠寬度的中間變數，例如 128 位元整數，以避免溢位。

這個 hash function 的設計理由如下：

1. 使用完整的 32 位元 IP 資訊
   不只取最後一個欄位，也不只計算四個欄位的總和。

2. 隨機化可降低規律輸入造成的碰撞
   IP 位址通常以網段成批出現，例如大量位址可能集中在同一個 /16 或 /24 網段。隨機選取 $A$、$B$ 可打散這種結構。

3. 碰撞機率維持在 $1/m$ 的量級
   在輸入分布正常且 hash seed 不被攻擊者預先知道時，每個 bucket 的平均負載接近 $\alpha$，查詢時間的期望值為 $O(1+\alpha)$。

4. 不可能保證完全沒有碰撞
   當 $m<2^{32}$ 時，根據鴿籠原理，一定存在不同 IP 對應到同一個 bucket，因此仍須搭配分離鏈結法。

---

合理的 table size

題目僅提供第 ii 小題，未附第 i 小題的 hashing proposal；以下明確採用「表格大小為質數的開放定址法，碰撞處理採雙重雜湊」作為前題設計。

核心觀念

雜湊函式將鍵值 $k$ 映射到雜湊表索引：

$$h_1(k)\in\{0,1,\ldots,m-1\}$$

其中 $m$ 為雜湊表大小。若該位置已有其他資料，使用探測函式尋找下一個位置。雙重雜湊的探測公式為：

$$p(k,i)=\bigl(h_1(k)+i\cdot h_2(k)\bigr)\bmod m$$

其中：

• $i=0,1,2,\ldots,m-1$ 為第幾次探測。
• $h_1(k)$ 是初始位置。
• $h_2(k)$ 是每次探測的位移量。
• $m$ 設為質數，且 $h_2(k)$ 不可為 $0$。

本題設定鍵值為整數，並令：

$$h_1(k)=k\bmod m$$ $$h_2(k)=1+(k\bmod(m-1))$$

因此：

$$1\leq h_2(k)\leq m-1$$

當 $m$ 為質數時，$h_2(k)$ 與 $m$ 必定互質，探測序列能走訪雜湊表中的每一個位置。

函式定義

1. 非負取餘函式

• 函式名稱：nonNegativeMod
• 參數：x 為鍵值，mod 為模數
• 回傳值：介於 $0$ 與 mod - 1 之間的整數
• 區域變數：r，儲存取餘結果

2. 主要雜湊函式

• 函式名稱：hashFunction
• 參數：key 為鍵值，tableSize 為雜湊表大小
• 回傳值：初始索引 $h_1(k)$
• 區域變數：無

3. 第二雜湊函式

• 函式名稱：stepHash
• 參數：key、tableSize
• 回傳值：探測位移量 $h_2(k)$
• 區域變數：無

4. 探測函式

• 函式名稱：probingFunction
• 參數：key、attempt、tableSize
• 回傳值：第 attempt 次探測的位置
• 區域變數：home、step、displacement

/* 回傳非負的 x mod mod，mod 必須為正數 */
int nonNegativeMod(long long x, int mod) {
    long long r = x % mod;

    if (r < 0) {
        r += mod;
    }

    return (int)r;
}

/* 主要雜湊函式 h1(k) */
int hashFunction(long long key, int tableSize) {
    return nonNegativeMod(key, tableSize);
}

/* 第二雜湊函式 h2(k)
   tableSize 必須為大於 2 的質數 */
int stepHash(long long key, int tableSize) {
    return 1 + nonNegativeMod(key, tableSize - 1);
}

/* 雙重雜湊探測函式
   attempt = 0, 1, ..., tableSize - 1 */
int probingFunction(long long key,
                    int attempt,
                    int tableSize) {
    int home = hashFunction(key, tableSize);
    int step = stepHash(key, tableSize);
    long long displacement =
        (long long)attempt * step;

    return (int)((home + displacement) % tableSize);
}

呼叫方法

插入資料時，依序呼叫探測函式：

題目資訊與合理假設

題幹未附上所稱的「hashing procedure above」程式碼；以下以最常見的開放定址法為合理假設：先計算 $h(k)$，發生碰撞時依探測序列尋找下一個槽位。

核心觀念

設：

• $n$：目前雜湊表中的資料筆數
• $m$：雜湊表槽位數
• $\alpha=\dfrac{n}{m}$：負載因子（load factor）
• $h(k)$：雜湊函數

在固定長度整數鍵值的模型中，計算 $h(k)$、存取一個槽位、比較一次鍵值皆視為 $O(1)$。因此，雜湊操作的時間主要取決於「發生碰撞後需要探測幾個槽位」。

解題方法與推導

開放定址法的核心流程可表示為：

位置 ← h(k)
當 table[位置] 已被占用且不是目標鍵值：
    位置 ← 下一個探測位置

令一次操作需要探測 $p$ 個槽位，則：

$$T(p)=c_0+c_1p$$

其中 $c_0$ 為計算雜湊值與初始化的固定成本，$c_1p$ 為 $p$ 次槽位檢查。因此：

$$T(p)=\Theta(p)$$

平均時間複雜度

在簡單均勻雜湊假設下，每個槽位被占用的比例約為 $\alpha$。探測至少 $j$ 個槽位的機率可用幾何級數估算：

$$E[p] \leq 1+\alpha+\alpha^2+\alpha^3+\cdots$$

由無窮等比級數：

$$E[p]\leq \frac{1}{1-\alpha}$$

所以單次操作的平均時間為：

$$E[T]=O\left(\frac{1}{1-\alpha}\right)$$

當雜湊表維持在未滿狀態，例如 $\alpha\leq\alpha_0<1$ 時，$\dfrac{1}{1-\alpha}$ 為常數，因此：

$$E[T]=\Theta(1)=O(1)$$

也就是說，雜湊表在良好雜湊函數與適當負載因子下，插入、查找與刪除的平均時間皆為 $O(1)$。

當 $\alpha$ 接近 $1$ 時，平均探測次數會明顯增加。例如：

$$\alpha=1-\frac{1}{m} \quad\Longrightarrow\quad \frac{1}{1-\alpha}=m$$

此時平均成本已退化至 $O(m)$，因此「平均為 $O(1)$」必須建立在負載因子維持常數上限的條件下。

最壞時間複雜度

最壞情況發生在大量鍵值產生相同的雜湊位置，形成長碰撞群集。一次查找或插入可能必須逐一檢查整個表：

$$p_{\max}=m$$

因此：

$$T_{\max}=\Theta(m)$$

若通常設定 $m=\Theta(n)$，則：

$$T_{\max}=\Theta(n)=O(n)$$

所以單次雜湊表操作的結果為：

• 平均時間：$\Theta(1)$，亦即 $O(1)$
• 最壞時間：$\Theta(m)$；當 $m=\Theta(n)$ 時為 $\Theta(n)$

若程序是建立整張雜湊表

核心觀念

本題考查以「鏈結串列」實作佇列（queue）時，如何分別定義：

1. 佇列標頭（queue head）：記錄佇列前端與後端的位置。
2. 佇列儲存節點（queue storage）：實際儲存資料，並以指標串接下一個節點。

佇列遵守先進先出（FIFO）原則：

• 從 front 端刪除元素。
• 從 rear 端加入元素。

因此，為了讓加入與刪除都能在 $O(1)$ 時間完成，標頭必須同時保存 front 與 rear 指標。

解題方法

若採用鏈結串列表示佇列，可將每個儲存節點定義為：

typedef int ElementType;

typedef struct QueueNode {
    ElementType data;
    struct QueueNode *link;
} QueueNode;

其中：

• data 儲存佇列元素。
• link 指向下一個節點。
• 最後一個節點的 link 設為 NULL。

佇列標頭定義為：

typedef struct QueueHead {
    QueueNode *front;
    QueueNode *rear;
} QueueHead;

完整佇列結構可寫成：

typedef struct Queue {
    QueueNode *front;
    QueueNode *rear;
} Queue;

初始化空佇列時：

Queue q;

q.front = NULL;
q.rear = NULL;

此時可表示為：

$$q.front = q.rear = NULL$$

當佇列非空時，結構如下：

$$q.front \longrightarrow \text{第一個節點} \longrightarrow \cdots \longrightarrow \text{最後一個節點} \longleftarrow q.rear$$

題目資訊與基本假設

題目未附上前一小題所定義的節點與資料結構；以下採用最常見的「依優先權排序之鏈結串列」實作，並假設：

• 優先權數值越大，優先順序越高。
• 優先權相同時採先進先出（FIFO）。
• front 永遠指向目前優先權最高的元素。

---

核心觀念

Priority Queue 與一般 Queue 的差異如下：

• 一般 Queue：依進入順序取出，遵守 FIFO。
• Priority Queue：每次取出優先權最高的元素。
• 優先權相同時，再依進入順序取出。

為了讓 Dequeue 能在 $O(1)$ 時間完成，可維持以下不變量：

$$priority_1 \ge priority_2 \ge priority_3 \ge \cdots$$

也就是讓鏈結串列由高優先權排到低優先權。因此：

• Enqueue：找到適當位置插入新節點。
• Dequeue：直接移除串列首端節點。

---

資料結構

typedef struct Node {
    int data;
    int priority;
    struct Node *next;
} Node;

typedef struct {
    Node *front;
} PriorityQueue;

其中 front 指向優先權最高的節點。

---

Enqueue 函式

解題方法

插入新元素時分成三種情況：

1. Queue 為空：新節點成為 front。
2. 新節點優先權高於目前首節點：插入最前端。
3. 其他情況：向後尋找，插入最後一個優先權不低於新節點的位置。

搜尋時使用：

current->next->priority >= priority

如此可使相同優先權的新節點插在既有節點之後，保持 FIFO。

#include <stdbool.h>
#include <stdlib.h>

bool Enqueue(PriorityQueue *q, int data, int priority)
{
    Node *newNode = (Node *)malloc(sizeof(Node));

    if (newNode == NULL) {
        return false;
    }

    newNode->data = data;
    newNode->priority = priority;
    newNode->next = NULL;

    /* Queue 為空，或新節點優先權最高 */
    if (q->front == NULL ||
        priority > q->front->priority) {

        newNode->next = q->front;
        q->front = newNode;
        return true;
    }

    /*
     * 找到最後一個 priority >= 新節點優先權的位置。
     * 相同優先權時插在舊節點後方，維持 FIFO。
     */
    Node *current = q->front;

    while (current->next != NULL &&
           current->next->priority >= priority) {
        current = current->next;
    }

    newNode->next = current->next;
    current->next = newNode;

    return true;
}

插入範例

原本的 Queue 為：

題目資訊與作答假設

題目未附前文所指定的實作程式碼；以下採用標準鏈結串列佇列，並維護 front 與 rear 指標，使兩端都能直接存取。

核心觀念

佇列（Queue）遵循 FIFO（First In, First Out）：

• Enqueue：從隊尾 rear 加入資料。
• Dequeue：從隊首 front 移除資料。
• 目前佇列含有 $n$ 個元素。

時間複雜度的關鍵，在於操作過程是否需要：

• 逐一走訪 $n$ 個節點；
• 移動或搬移 $n$ 個陣列元素；
• 只執行固定次數的指標更新與資料存取。

解題方法

鏈結串列佇列的結構如下：

$$front \rightarrow \text{第一個節點} \rightarrow \cdots \rightarrow \text{最後一個節點} \leftarrow rear$$

一、Enqueue 的時間複雜度

典型程序如下：

Enqueue(Q, x):
    newNode = 建立節點(x)

    if rear == NULL:
        front = newNode
        rear = newNode
    else:
        rear.next = newNode
        rear = newNode

逐步分析：

1. 建立新節點：$O(1)$
2. 判斷佇列是否為空：$O(1)$
3. 設定節點資料與指標：$O(1)$
4. 更新 front 或 rear：$O(1)$

因此總成本為固定次數的常數操作：

$$T_{\text{Enqueue}}(n) = c_1+c_2+c_3+c_4 = c$$

其中 $c$ 與目前元素數量 $n$ 無關，所以：

$$T_{\text{Enqueue}}(n)=\Theta(1)$$

因此其 Big-O 表示為：

$$\boxed{O(1)}$$

二、Dequeue 的時間複雜度

典型程序如下：

核心觀念

本題考查「合併排序（Merge Sort）」的分治法（Divide and Conquer），核心步驟如下：

1. 將陣列分成左右兩半。
2. 遞迴地將左右兩半排序。
3. 將兩個已排序的子陣列合併成一個有序陣列。

停止遞迴的條件是區間內最多只有一個元素，此時必定已經排序完成。

本解採用 0-based index，排序區間以閉區間 $[left, right]$ 表示：

• 左半部：$[left, mid]$
• 右半部：$[mid+1, right]$

解題方法

合併兩個已排序區間時，分別以指標 i、j 指向左右兩半目前尚未處理的第一個元素：

• 比較 data[i] 與 data[j]。
• 將較小者放入暫存陣列 temp。
• 某一半處理完後，將另一半剩餘元素直接複製進去。
• 最後把 temp[left..right] 複製回原陣列。

使用 <= 而非 <，可在元素相等時優先取左半部元素，使排序具有穩定性。

C 語言參考解答

題目資訊與分析前提

題幹未附上所稱的 merge sort function 程式碼；以下依標準合併排序函式分析：每次將資料分成兩半，遞迴排序兩半，再以線性時間合併。

核心觀念

合併排序（Merge Sort）採用分治法：

1. 將大小為 $n$ 的資料分成兩個約為 $n/2$ 的子問題。
2. 遞迴排序兩個子陣列。
3. 將兩個已排序的子陣列合併。

合併階段使用兩個指標，依序比較兩邊目前最小的元素，每個元素最多被處理一次，因此合併大小為 $n$ 的資料需要

$$\Theta(n)$$

的時間。

解題方法：建立遞迴式

設 $T(n)$ 表示合併排序處理 $n$ 筆資料所需的時間。

兩個遞迴子問題各處理約 $n/2$ 筆資料，合併需要 $\Theta(n)$ 時間，因此：

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

基本情況為只有一筆資料時不需排序：

$$T(1)=\Theta(1)$$

若以常數表示，可寫成：

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

其中 $cn$ 是合併成本，$d$ 是切割及函式呼叫等固定成本。

遞迴樹分析

每一層的合併總成本皆為 $\Theta(n)$：

• 第 $0$ 層：合併一個大小為 $n$ 的陣列，成本為 $cn$。

• 第 $1$ 層：合併兩個大小為 $n/2$ 的陣列，總成本為

  $$2\cdot c\frac{n}{2}=cn$$

• 第 $2$ 層：合併四個大小為 $n/4$ 的陣列，總成本為

  $$4\cdot c\frac{n}{4}=cn$$

• 第 $i$ 層：共有 $2^i$ 個子問題，每個子問題大小為 $n/2^i$，總成本為

  $$2^i\cdot c\frac{n}{2^i}=cn$$

當子問題縮小至 $1$ 筆資料時：

$$\frac{n}{2^k}=1$$

因此：