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

核心觀念

本題考查兩個重點：

1. 能畫出符合條件的 Heap。
2. 能用 C 語言或虛擬碼定義 Heap 的資料結構。

Heap 是一種以「完全二元樹」為基礎的樹狀資料結構，並且必須滿足堆積性質：

• Max Heap（最大堆積）：每個父節點的值皆大於或等於子節點。
• Min Heap（最小堆積）：每個父節點的值皆小於或等於子節點。

題目未指定種類，因此以下以最常見的 Max Heap 為例。

解題方法：畫出一個合法的 Heap

取下列 Max Heap：

             90
           /    \
         70      60
        /  \    /  \
      20   40  50  10

此樹符合兩項條件：

1. 完全二元樹

除了最後一層外，每一層皆填滿；最後一層的節點由左至右排列，中間沒有空缺。

本例各層節點數如下：

• 第 1 層：90
• 第 2 層：70、60
• 第 3 層：20、40、50、10

因此符合完全二元樹的形狀限制。

2. 滿足最大堆積性質

逐一比較父節點與子節點：

• $90 \geq 70,\ 90 \geq 60$
• $70 \geq 20,\ 70 \geq 40$
• $60 \geq 50,\ 60 \geq 10$

所有父節點皆不小於其子節點，因此這是一個合法的 Max Heap。

以陣列表示 Heap

Heap 通常不使用指標表示，而是利用陣列儲存完全二元樹。

上述 Heap 可表示為：

$$A = [90,\ 70,\ 60,\ 20,\ 40,\ 50,\ 10]$$

若採用 1-based indexing，節點位置關係為：

• 父節點位置：

$$parent(i)=\left\lfloor \frac{i}{2}\right\rfloor$$

• 左子節點位置：

$$left(i)=2i$$

• 右子節點位置：

$$right(i)=2i+1$$

陣列內容如下：

位置 $i$	值	父節點位置
1	90	無
2	70	1
3	60	1
4	20	2
5	40	2
6	50	3
7	10	3

若採用 0-based indexing，則公式改為：

$$parent(i)=\left\lfloor \frac{i-1}{2}\right\rfloor$$ $$left(i)=2i+1$$ $$right(i)=2i+2$$

C 語言資料結構定義

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int size;
} MaxHeap;

其中：

• data：儲存 Heap 中的元素。
• size：目前 Heap 內的元素個數。
• data[0]：根節點，也是最大值所在位置。
• data[i] 的子節點位置為 2*i+1 與 2*i+2，因為此定義採用 0-based indexing。

若以 0-based indexing 儲存前述範例：

data[0] = 90
data[1] = 70
data[2] = 60
data[3] = 20
data[4] = 40
data[5] = 50
data[6] = 10
size = 7

關鍵操作的虛擬碼

插入元素

新元素必須先放在陣列尾端，以維持完全二元樹的形狀，再向上調整，恢復最大堆積性質。

題目資訊假設

題幹引用的「上述資料結構」未附於題目內容。以下採用標準的「整數陣列表示最大堆（max-heap）」定義，陣列採 0-based indexing，且函式直接在原陣列上建堆。

核心觀念

最大堆必須同時符合：

1. 結構是一棵完全二元樹。
2. 每個節點的值大於或等於其子節點。

對於 0-based 陣列中的節點 i：

$$\text{left}(i)=2i+1$$ $$\text{right}(i)=2i+2$$ $$\text{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor$$

陣列中索引為

$$\left\lfloor\frac{n}{2}\right\rfloor,\ldots,n-1$$

的節點都是葉節點，因此本身已經是堆。最後一個非葉節點為：

$$\left\lfloor\frac{n}{2}\right\rfloor-1$$

建堆時，從最後一個非葉節點反向處理至根節點，對每個節點執行 sift-down，使其子樹符合最大堆性質。

解題方法

對索引 i 執行 sift-down：

1. 比較目前節點與左、右子節點。
2. 找出三者中值最大的節點。
3. 若最大值不是目前節點，交換兩者。
4. 將處理位置向下移動，持續修復受影響的子樹。

之所以必須由下往上處理，是因為處理節點 i 時，其左、右子樹已經先被建成最大堆，此時只需把 i 的值向下調整即可。

C 程式碼

題目資訊與合理假設

題目所稱的 function above 未附在目前題幹中，因此無法對原函式給出唯一複雜度；以下假設該函式只有一個由 $1$ 執行到 $n$ 的迴圈，且迴圈本體每次耗時固定為 $\Theta(1)$。

for (i = 1; i <= n; i++) {
    // 固定時間操作
}

核心觀念

時間複雜度分析是計算基本操作隨輸入大小 $n$ 增加的成長率，並忽略常數係數與低階項。

• $O(f(n))$：表示執行時間的漸近上界。
• $\Theta(f(n))$：表示執行時間的漸近緊確界。
• 單層迴圈若執行 $n$ 次，且每次執行固定時間，總時間為
  $n \times \Theta(1)=\Theta(n)。$

解題方法與詳細計算

令每個基本操作的成本為常數：

1. 初始化 i = 1：執行 $1$ 次，成本為 $\Theta(1)$。
2. 判斷 i <= n：成功進入迴圈 $n$ 次，最後失敗 $1$ 次，因此共 $n+1$ 次。
3. 迴圈本體：每次執行固定時間，共 $n$ 次。
4. i++：每次迭代執行一次，共 $n$ 次。

因此總執行時間可寫成

$$T(n)=c_0+c_1(n+1)+c_2n+c_3n,$$

其中 $c_0,c_1,c_2,c_3$ 都是與 $n$ 無關的常數。整理得

核心觀念

Hashing 的目的是將整數鍵值 $k$ 透過雜湊函數 $h(k)$ 轉換成雜湊表中的陣列索引：

$$h: \mathbb{Z}\rightarrow \{0,1,\ldots,m-1\}$$

其中 $m$ 為雜湊表大小。最基本的除法雜湊法為：

$$h(k)=k\bmod m$$

不同鍵值經過雜湊函數後可能得到相同索引，此現象稱為碰撞（collision）。因此，雜湊表必須指定碰撞處理方法。本題採用 separate chaining，每個陣列位置存放一條鏈結串列，所有雜湊到同一索引的資料放在同一串列中。

負整數在 C 語言中需將餘數正規化為非負值：

$$h(k)=((k\bmod m)+m)\bmod m$$

負責確保索引一定落在 $0$ 到 $m-1$ 之間。

解題方法與雜湊流程

令雜湊表大小為 $m=7$，採用：

$$h(k)=k\bmod 7$$

依序插入鍵值：

$$10,\ 17,\ 24,\ 5,\ 12,\ 31$$

計算結果如下：

鍵值 $k$	$h(k)=k\bmod 7$	說明
10	3	放入第 3 格
17	3	與 10 碰撞
24	3	與 10、17 碰撞
5	5	放入第 5 格
12	5	與 5 碰撞
31	3	與 10、17、24 碰撞

以「新節點插入鏈結串列前端」處理碰撞，流程可表示為：

鍵值 k
  │
  ▼
計算 h(k) = k mod 7
  │
  ▼
取出 bucket[h(k)]
  │
  ├── 該位置為空：建立新節點
  │
  └── 該位置已有資料：將新節點接到鏈結串列前端

最後的雜湊表如下：

索引       鏈結串列
────────────────────────────────
 0         NULL
 1         NULL
 2         NULL
 3         [31] -> [24] -> [17] -> [10] -> NULL
 4         NULL
 5         [12] -> [5] -> NULL
 6         NULL

例如查找鍵值 $24$ 時，先計算：

$$h(24)=24\bmod 7=3$$

接著只需在第 3 格的鏈結串列中依序比對鍵值。

雜湊表資料結構

每個節點包含鍵值、資料內容，以及指向下一個節點的指標；雜湊表則包含大小 $m$ 與存放各串列起點的陣列。

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

typedef struct HashNode {
    int key;
    int data;
    struct HashNode *next;
} HashNode;

typedef struct {
    size_t m;          // 雜湊表大小
    HashNode **bucket; // 每個位置指向一條鏈結串列
} HashTable;

雜湊表初始化：

bool hashInit(HashTable *ht, size_t m)
{
    if (m == 0)
        return false;

    HashNode **array = calloc(m, sizeof(HashNode *));
    if (array == NULL)
        return false;

    ht->m = m;
    ht->bucket = array;
    return true;
}

雜湊函數：

size_t hashIndex(const HashTable *ht, int key)
{
    long long r = (long long)key % (long long)ht->m;

    if (r < 0)
        r += (long long)ht->m;

    return (size_t)r;
}

插入資料時，若鍵值已存在則更新資料；若不存在則建立新節點並接到鏈結串列前端：

核心觀念

雜湊表（hash table）使用雜湊函數將資料鍵值 $k$ 映射到陣列位置：

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

若兩個不同鍵值被映射到相同位置，即發生碰撞（collision）。本題採用開放定址法（open addressing），所有資料都直接存放在雜湊表內；發生碰撞時，使用 probing function 依序尋找下一個空位置。

本題設計如下：

• 雜湊表大小：$m=13$，位置為 $0$ 至 $12$
• 雜湊函數：除法取餘法

$$h(k)=k\bmod 13$$

• 探測函數：線性探測（linear probing）

$$p(k,i)=\bigl(h(k)+i\bigr)\bmod 13,\qquad i=0,1,2,\ldots,12$$

其中 $i=0$ 時先嘗試雜湊函數算出的原始位置；若該位置已被占用，便令 $i=1,2,\ldots$，依序探測下一個位置。

由於每次增加 $1$，並搭配 $\bmod 13$，最多會訪問表中的全部 $13$ 個位置，因此只要表內仍有空位，就能找到儲存位置。

解題方法

資料依下列順序插入：

$$18,\ 41,\ 54,\ 67,\ 80,\ 93,\ 29,\ 42,\ 55,\ 68$$

插入規則為：

1. 計算 $h(k)$。
2. 先檢查 $p(k,0)=h(k)$。
3. 若該位置已占用，依序檢查 $p(k,1),p(k,2),\ldots$。
4. 找到第一個空位置後，將資料存入該位置。

插入資料 $k$	$h(k)=k\bmod13$	探測位置順序	實際存放位置
$18$	$5$	$5$	$5$
$41$	$2$	$2$	$2$
$54$	$2$	$2\rightarrow3$	$3$
$67$	$2$	$2\rightarrow3\rightarrow4$	$4$
$80$	$2$	$2\rightarrow3\rightarrow4\rightarrow5\rightarrow6$	$6$
$93$	$2$	$2\rightarrow3\rightarrow4\rightarrow5\rightarrow6\rightarrow7$	$7$
$29$	$3$	$3\rightarrow4\rightarrow5\rightarrow6\rightarrow7\rightarrow8$	$8$
$42$	$3$	$3\rightarrow4\rightarrow5\rightarrow6\rightarrow7\rightarrow8\rightarrow9$	$9$

核心觀念

題目未指定雜湊表大小與碰撞處理法，以下採用標準假設：鍵值為整數、使用開放定址法，表格容量為正整數 $M$，碰撞採用線性探查（linear probing）。

雜湊函式將鍵值映射至雜湊表的初始位置：

$$h(k)=k\bmod M$$

在 C 語言中，負數取餘數可能得到負值，因此可修正為：

$$h(k)=((k\bmod M)+M)\bmod M$$

若初始位置已有其他資料，便依序探查下一個位置。線性探查的位移函式為：

$$p(i)=i$$

其中 $i$ 為第幾次探查，$i=0,1,\ldots,M-1$。實際探查位置為：

$$P(k,i)=\bigl(h(k)+p(i)\bigr)\bmod M =\bigl(h(k)+i\bigr)\bmod M$$

因此：

• $i=0$：檢查雜湊函式產生的初始位置。
• $i=1$：檢查下一個位置。
• $i=2$：再檢查下一個位置。
• 到達表尾時，透過取餘數回到表首。

解題方法

先以雜湊函式求出鍵值的初始位置，再以探查函式依序產生實際位置。以 $M=11$、$k=37$ 為例：

$$h(37)=37\bmod 11=4$$

探查順序為：

$$4,5,6,7,8,9,10,0,1,2,3$$

這個順序會檢查整張表，適合用於雜湊表的插入與搜尋。

C 語言實作

核心觀念

本小題未附前文所稱的雜湊函式與碰撞處理方式；以下採用標準假設：雜湊表有 $m$ 個位置，儲存 $n$ 筆資料，使用分離鏈結法處理碰撞，且固定長度鍵值的雜湊函式計算為 $O(1)$。

負載因子定義為

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

雜湊法的效率取決於：

1. 雜湊函式計算成本；
2. 是否發生碰撞；
3. 發生碰撞後需要檢查多少筆資料；
4. 負載因子 $\alpha$ 是否維持在常數範圍。

解題方法

一次查找或插入的主要流程可抽象為：

i ← h(key)
p ← table[i]

while p 不為空:
    比較 p.key 與 key
    p ← p.next

其中：

• 計算 $h(key)$：$O(1)$；
• 透過索引取得 table[i]：$O(1)$；
• 掃描碰撞鏈結串列：取決於該串列長度。

設第 $i$ 個位置的鏈結串列長度為 $L_i$。在簡單均勻雜湊的假設下，每筆資料落入任一位置的機率為 $1/m$，因此

$$E[L_i] =\sum_{j=1}^{n}\Pr(h(k_j)=i) =n\cdot\frac{1}{m} =\frac{n}{m} =\alpha.$$

不成功查找平均需檢查 $\alpha$ 筆資料；成功查找平均需檢查的資料筆數約為

$$1+\frac{n-1}{2m} =\Theta(1+\alpha).$$

所以一次操作的平均時間為

$$T_{\text{average}} =O(1)+O(1)+O(1+\alpha) =O(1+\alpha).$$

當雜湊表維持固定負載因子，即 $\alpha=O(1)$ 時，

$$T_{\text{average}}=O(1).$$

最壞情況分析

最壞情況是所有鍵值都被雜湊到同一個位置：

$$h(k_1)=h(k_2)=\cdots=h(k_n).$$

此時該鏈結串列長度為 $n$，查找、刪除或需要先檢查重複鍵值的插入操作，都可能逐一比較全部資料，因此

$$T_{\text{worst}}=O(n).$$

若雜湊函式本身需要逐字掃描長度為 $\ell$ 的字串，則應寫成

核心觀念

Stack（堆疊）遵守 LIFO（Last In, First Out，後進先出）。要表示一個儲存整數的堆疊，至少需要：

1. 儲存整數元素的空間。
2. 記錄堆疊頂端位置的變數 top。
3. 若使用固定大小陣列，還需要定義最大容量。

題幹文字未附所稱的堆疊圖形，也未指定陣列或鏈結串列；以下採最常見的固定容量陣列表示法。

解題方法

令 top 表示「目前元素個數」，同時也是下一個可插入的位置，則資料結構可定義為：

#define MAX_STACK_SIZE 100

typedef struct {
    int data[MAX_STACK_SIZE];
    int top;
} Stack;

初始化時：

void initStack(Stack *s) {
    s->top = 0;
}

當堆疊中有 $n$ 個元素時：

• 有效元素為 data[0] 到 data[n - 1]。
• top == n。
• 堆疊頂端元素為 data[top - 1]。
• 堆疊底端元素為 data[0]。

因此：

• 空堆疊：top == 0
• 堆疊已滿：top == MAX_STACK_SIZE

插入與刪除的關鍵操作為：

/* push */
s->data[s->top] = x;
s->top++;

/* pop */
s->top--;
x = s->data[s->top];

核心觀念

本題考查堆疊（Stack）的抽象資料型態與基本操作。堆疊遵守 後進先出（LIFO, Last In First Out）：

• NEW：建立並初始化空堆疊。
• PUSH：將資料放入堆疊頂端。
• POP：移除並取出堆疊頂端資料。
• 堆疊為空時執行 POP，稱為 underflow。
• 堆疊容量已滿時執行 PUSH，稱為 overflow。

以下採用「陣列＋整數 top」實作，其中 top 表示目前堆疊內的元素數量。因此：

$$0 \leq top \leq capacity$$

當堆疊非空時，頂端元素位於：

$$data[top-1]$$

解題方法

建立結構如下：

• data：存放堆疊元素的陣列。
• capacity：堆疊最大容量。
• top：目前元素個數，空堆疊時為 $0$。

操作流程：

1. NEW(capacity) 配置結構與陣列，並令 top = 0。
2. PUSH 先確認堆疊未滿，再將資料放入 data[top]，最後令 top 加一。
3. POP 先確認堆疊非空，令 top 減一，再取出 data[top]。

函式介面與回傳值

函式	參數	回傳值
NEW(int capacity)	堆疊容量	成功回傳 Stack *，失敗回傳 NULL
PUSH(Stack *s, int value)	堆疊指標、待存入資料	操作狀態
POP(Stack *s, int *value)	堆疊指標、存放取出資料的位址	操作狀態

由於 C 函式只能直接回傳一個值，POP 使用 int *value 將取出的資料寫回呼叫端，並以回傳值表示操作是否成功。

C 程式碼