113 年 國立政治大學資訊管理學系碩士班科技組《資料結構》

核心觀念

本題考查使用陣列，以 bottom-up construction（由下而上建堆） 建立 Max-Heap。

對於以 $1$ 為起始索引的陣列：

• 第 $i$ 個節點的父節點為 $\left\lfloor i/2 \right\rfloor$。
• 左子節點為 $2i$，右子節點為 $2i+1$。
• Max-Heap 必須滿足：

$$A[\text{parent}] \geq A[\text{child}]$$

底層葉節點本身已經是合法的 Heap，因此只需從最後一個非葉節點開始，依序向根節點進行 heapify-down。

本題共有 $n=18$ 個元素，最後一個非葉節點為：

$$\left\lfloor \frac{n}{2} \right\rfloor = \left\lfloor \frac{18}{2} \right\rfloor =9$$

因此處理順序為：

$$i=9,8,7,\ldots,2,1$$

---

解題方法

初始陣列如下：

$$[1,8,4,53,12,7,35,103,16,14,63,29,20,72,38,18,22,56]$$

每次處理節點 $i$ 時，將其與較大的子節點比較；若子節點較大，就交換並繼續向下調整。

---

Step 1：處理索引 $i=9$

節點 $A[9]=16$，其左子節點為 $A[18]=56$。

因為：

$$56>16$$

交換 $16$ 與 $56$：

$$[1,8,4,53,12,7,35,103,56,14,63,29,20,72,38,18,22,16]$$

---

Step 2：處理索引 $i=8$

節點 $A[8]=103$，子節點為：

$$A[16]=18,\qquad A[17]=22$$

因為 $103$ 已大於兩個子節點，不需交換：

$$[1,8,4,53,12,7,35,103,56,14,63,29,20,72,38,18,22,16]$$

---

Step 3：處理索引 $i=7$

節點 $A[7]=35$，子節點為：

$$A[14]=72,\qquad A[15]=38$$

較大的子節點為 $72$，且：

$$72>35$$

交換：

$$[1,8,4,53,12,7,72,103,56,14,63,29,20,35,38,18,22,16]$$

---

Step 4：處理索引 $i=6$

節點 $A[6]=7$，子節點為：

$$A[12]=29,\qquad A[13]=20$$

較大的子節點為 $29$，且：

$$29>7$$

交換：

$$[1,8,4,53,12,29,72,103,56,14,63,7,20,35,38,18,22,16]$$

---

Step 5：處理索引 $i=5$

節點 $A[5]=12$，子節點為：

$$A[10]=14,\qquad A[11]=63$$

較大的子節點為 $63$，且：

$$63>12$$

交換：

$$[1,8,4,53,63,29,72,103,56,14,12,7,20,35,38,18,22,16]$$

---

Step 6：處理索引 $i=4$

節點 $A[4]=53$，子節點為：

$$A[8]=103,\qquad A[9]=56$$

較大的子節點為 $103$，且：

$$103>53$$

交換後，$53$ 移至索引 $8$。索引 $8$ 的子節點為 $18$ 與 $22$，而 $53$ 已大於兩者，因此停止調整：

$$[1,8,4,103,63,29,72,53,56,14,12,7,20,35,38,18,22,16]$$

---

Step 7：處理索引 $i=3$

節點 $A[3]=4$，子節點為：

$$A[6]=29,\qquad A[7]=72$$

先與較大的子節點 $72$ 交換：

$$[1,8,72,103,63,29,4,53,56,14,12,7,20,35,38,18,22,16]$$

此時 $4$ 位於索引 $7$，其子節點為：

核心觀念

本題考查「堆積排序法」（Heap Sort），核心工具是最大堆積（max-heap）。

對以陣列儲存、索引從 $1$ 開始的完全二元樹：

• 第 $i$ 個節點的左子節點為 $2i$。
• 第 $i$ 個節點的右子節點為 $2i+1$。
• 最大堆積滿足：

$$A[i]\geq A[2i],\qquad A[i]\geq A[2i+1]$$

因此根節點必定是目前堆積中的最大值。反覆取出根節點並放到陣列末端，即可由小到大完成排序。

---

解題方法：使用最大堆積進行遞增排序

堆積排序分成兩個階段：

1. 將所有鍵值建成最大堆積。
2. 重複將根節點（目前最大值）移到未排序區間的最後，再修復堆積。

一、建立最大堆積

原始陣列為：

$$[1,8,4,53,12,7,35,103,16,14,63,29,20,72,38,18,22,56]$$

採用自底向上的 Build-Max-Heap，從最後一個非葉節點開始調整。最後得到最大堆積：

$$[103,63,72,56,14,29,38,53,16,12,1,7,20,35,4,18,22,8]$$

其樹狀結構的主要關係例如：

• 根節點 $103$ 大於子節點 $63,72$。
• $63$ 大於 $56,14$。
• $72$ 大於 $29,38$。
• $56$ 大於 $53,16$。

每個父節點皆不小於其子節點，因此符合最大堆積定義。

二、反覆取出最大值

目前最大值位於根節點。每次執行下列操作：

1. 將根節點與未排序區間最後一個元素交換。
2. 將堆積大小減少 $1$。
3. 對新的根節點執行 Max-Heapify，使剩餘部分恢復最大堆積。

例如第一次操作：

$$[103,63,72,56,\ldots,22,8]$$

將 $103$ 與最後元素 $8$ 交換：

$$[8,63,72,56,\ldots,22,103]$$

接著在前 $17$ 個元素中向下調整，使其恢復最大堆積。此時 $103$ 已固定在排序結果的最後位置。

重複此程序後，較大的元素依序被放到陣列右側：

$$103,\ 72,\ 63,\ 56,\ 53,\ 38,\ 35,\ 29,\ 22,\ldots$$

全部完成後，陣列由小到大排列為：

$$[1,4,7,8,12,14,16,18,20,22,29,35,38,53,56,63,72,103]$$

---

演算法虛擬碼

AVL 插入與平衡步驟

1. 按序插入 1、8、4 → 4 成為根 (LR 旋轉)
2. 插入 53、12、7、35 → 12 成為根 (RR 旋轉)
3. 插入 103、16、14、63 → 12、53、103 均保持平衡
4. 插入 29、20、72、38、18、22、56 → 依序出現 RL、RR、LR、RR、RL、RR、LR 雙旋轉，最終樹形如下

最終 AVL 樹

AVL 樹排序算法

1. 建樹 (Insert)

   • 依序將鍵值 $k_1,k_2,\dots ,k_n$ 插入空 AVL 樹。
   • 每次插入利用 AVL 旋轉保證樹高 $h\le \lfloor\log_2 n\rfloor$，插入時間 $O(\log n)$。

2. 遍歷 (In‑order Traversal)

   • 以遞迴或迭代方式中序走訪 AVL 樹，輸出節點鍵即為遞增序列。
   • 中序遍歷時間 $O(n)$。

偽碼

核心觀念

本題考查分治法（Divide and Conquer）與 Merge Sort 的時間複雜度分析。

Merge Sort 的核心流程分為三步：

1. 分割（Divide）：將序列分成左右兩半。
2. 遞迴處理（Conquer）：分別對左右子序列排序。
3. 合併（Combine）：將兩個已排序的子序列合併成一個有序序列。

其關鍵性質是：兩個已排序序列可在線性時間內完成合併，因此每一層遞迴的總合併成本為 $\Theta(n)$。

---

Merge Sort 演算法定義

設待排序序列為 $A[\text{left} \ldots \text{right}]$。當序列長度為 $0$ 或 $1$ 時，本身即已排序；否則取中點，分別排序左右兩半，再合併結果。

演算法概念

MergeSort(A, left, right):
    if left >= right:
        return

    mid = floor((left + right) / 2)

    MergeSort(A, left, mid)
    MergeSort(A, mid + 1, right)

    Merge(A, left, mid, right)

其中 Merge 假設：

• $A[\text{left} \ldots \text{mid}]$ 已排序；
• $A[\text{mid}+1 \ldots \text{right}]$ 已排序。

合併時，分別以指標指向兩個子序列的最小尚未處理元素，每次取出較小者放入暫存陣列，直到全部元素處理完畢。

Merge(A, left, mid, right):
    建立暫存陣列 B

    i = left
    j = mid + 1
    k = 0

    while i <= mid and j <= right:
        if A[i] <= A[j]:
            B[k] = A[i]
            i = i + 1
        else:
            B[k] = A[j]
            j = j + 1
        k = k + 1

    將左半部剩餘元素複製到 B
    將右半部剩餘元素複製到 B

    將 B 複製回 A[left ... right]

使用 $A[i] \leq A[j]$ 時，若兩元素相等，優先取左側元素，因此可維持相等元素原本的相對順序，這種 Merge Sort 稱為穩定排序（stable sort）。

---

合併程序的時間複雜度

假設目前序列共有 $n$ 個元素。

在合併過程中：

• 每個元素最多被比較並放入暫存陣列一次；
• 每個元素最多再被複製回原陣列一次。

因此合併所需時間與元素數量成正比：

$$M(n)=\Theta(n)$$

---

遞迴式建立

Merge Sort 將大小為 $n$ 的問題分成兩個大小約為 $n/2$ 的子問題，並花費 $\Theta(n)$ 時間合併，因此其遞迴式為：

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

基本情況為：

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

若以較精確的形式表示，且假設 $n$ 是 $2$ 的冪次，則可寫成：

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

其中 $n-1$ 代表合併兩個已排序序列時最多需要的比較次數。

---

以遞迴樹求解

令每一層的合併成本如下：

題目資訊

題幹所稱的「above key set」未提供，因此無法列出這組實際鍵值的唯一排序結果。以下以鍵集合

$$K=(k_1,k_2,\ldots,k_n)$$

為一般表示，假設採用「由小到大」排序，完整示範 Merge Sort 的拆分與合併流程。

---

核心觀念

Merge Sort（合併排序）是一種 Divide and Conquer 演算法，包含三個步驟：

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

遞迴終止條件為子序列長度小於或等於 $1$，因為單一元素必定已排序。

其時間複雜度為：

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

依 Master Theorem：

$$T(n)=\Theta(n\log n)$$

Merge Sort 的額外空間複雜度為：

$$\Theta(n)$$

---

解題方法：遞迴拆分

以偶數個鍵值為例，若

$$K=(k_1,k_2,k_3,k_4,k_5,k_6,k_7,k_8)$$

則拆分過程如下：

$$(k_1,k_2,k_3,k_4,k_5,k_6,k_7,k_8)$$

拆成：

$$(k_1,k_2,k_3,k_4) \qquad (k_5,k_6,k_7,k_8)$$

繼續拆分：

$$(k_1,k_2)\quad (k_3,k_4) \qquad (k_5,k_6)\quad (k_7,k_8)$$

最後拆成單一元素：

$$(k_1)\ (k_2)\ (k_3)\ (k_4)\ (k_5)\ (k_6)\ (k_7)\ (k_8)$$

---

解題方法：逐層合併

假設每次合併時，將兩個子序列中目前最小的首元素取出，放入結果序列。

第一層合併：

$$(k_1)+(k_2) \longrightarrow \operatorname{merge}(k_1,k_2)$$

若 $k_1<k_2$，則：

$$(k_1)+(k_2)\longrightarrow(k_1,k_2)$$

若 $k_2<k_1$，則：

$$(k_1)+(k_2)\longrightarrow(k_2,k_1)$$

同理：

$$(k_3)+(k_4) \longrightarrow \text{依大小排列的兩元素序列}$$ $$(k_5)+(k_6) \longrightarrow \text{依大小排列的兩元素序列}$$ $$(k_7)+(k_8) \longrightarrow \text{依大小排列的兩元素序列}$$

令第一層合併結果分別為：

$$A=\operatorname{sort}(k_1,k_2)$$ $$B=\operatorname{sort}(k_3,k_4)$$ $$C=\operatorname{sort}(k_5,k_6)$$ $$D=\operatorname{sort}(k_7,k_8)$$

第二層合併為：

$$A+B\longrightarrow E=\operatorname{merge}(A,B)$$ $$C+D\longrightarrow F=\operatorname{merge}(C,D)$$

此時 $E$ 與 $F$ 都已由小到大排列。

最後一層合併為：

核心觀念

本題考查分治法（Divide and Conquer）中的快速排序（Quick Sort），並指定每次選取目前子陣列的第一個元素作為 pivot。

快速排序的基本流程是：

1. 選定 pivot。
2. 將資料重新排列，使得：
   • pivot 左側的元素不大於 pivot；
   • pivot 右側的元素不小於 pivot。
3. pivot 放到排序後的正確位置。
4. 對 pivot 左、右兩側的子陣列遞迴執行快速排序。

若陣列範圍為 $A[low \dots high]$，指定 pivot 為第一個元素，則：

$$pivot=A[low]$$

完成 partition 後，若 pivot 位於位置 $p$，則接下來排序：

$$A[low \dots p-1]$$

以及

$$A[p+1 \dots high]$$

---

解題方法：以第一個元素為 pivot

採用雙向掃描法進行 partition：

• 令 $i=low+1$，由左向右尋找大於 pivot 的元素。
• 令 $j=high$，由右向左尋找小於 pivot 的元素。
• 若 $i<j$，交換 $A[i]$ 與 $A[j]$。
• 當掃描交錯後，將 pivot 與 $A[j]$ 交換，使 pivot 放入正確位置。

partition 結束時，會得到：

$$A[low \dots j-1]\le pivot$$ $$A[j]=pivot$$ $$A[j+1 \dots high]\ge pivot$$

快速排序虛擬碼

QuickSort(A, low, high):
    if low >= high:
        return

    p = Partition(A, low, high)

    QuickSort(A, low, p - 1)
    QuickSort(A, p + 1, high)

Partition 虛擬碼

Partition(A, low, high):
    pivot = A[low]
    i = low + 1
    j = high

    while i <= j:

        while i <= high and A[i] <= pivot:
            i = i + 1

        while j >= low + 1 and A[j] >= pivot:
            j = j - 1

        if i < j:
            swap(A[i], A[j])

    swap(A[low], A[j])

    return j

呼叫整個陣列時：

QuickSort(A, 0, n - 1)

其中 $n$ 為陣列元素個數。

---

Partition 的正確性

設 pivot 為 $A[low]$。

在掃描過程中：

• $i$ 左側的元素都已確認為不大於 pivot；
• $j$ 右側的元素都已確認為不小於 pivot；
• 若 $A[i]>pivot$ 且 $A[j]<pivot$，交換兩者即可修正左右區域。

當 $i>j$ 時，代表左右掃描已經交錯，所有尚未處理的元素也已經落在正確區域。此時將 $A[low]$ 與 $A[j]$ 交換：

$$A[low]\leftrightarrow A[j]$$

核心觀念

本題考查以「分治法」設計的快速排序（Quicksort）。

快速排序每次選定一個基準值（pivot），將資料分成兩部分：

• 小於 pivot 的元素放在左側；
• 大於 pivot 的元素放在右側；
• pivot 放到排序後的正確位置。

接著對左右兩個子序列遞迴執行相同程序，直到子序列長度為 $0$ 或 $1$。

其遞迴形式為：

$$\text{QuickSort}(A,p,r)$$

若 $p<r$，先進行分割：

$$q=\text{Partition}(A,p,r)$$

再遞迴處理：

$$\text{QuickSort}(A,p,q-1)$$ $$\text{QuickSort}(A,q+1,r)$$

---

題目資訊與採用規則

題目文字提到「above key set」，但目前提供的題目內容未包含該組 key，因此無法列出該試卷實際數值的唯一排序過程。

以下採用一組示範 key：

$$A=[29,10,14,37,13,25,7]$$

並採用常見的 Lomuto 分割法：

1. 每次取子序列最後一個元素為 pivot。
2. 由左至右掃描。
3. 將小於或等於 pivot 的元素移至左側。
4. 掃描結束後，把 pivot 放到左右兩區之間。

若原考題指定其他 pivot 選取方式，分割過程會不同，但最後排序結果相同。

---

解題方法

第一次分割

目前序列為：

$$[29,10,14,37,13,25,7]$$

取最後一個元素：

$$\text{pivot}=7$$

所有其他元素均大於 $7$，因此 pivot 放到最左端：

$$[7,10,14,37,13,25,29]$$

分割結果為：

$$[\,7\,]\quad [10,14,37,13,25,29]$$

其中 $7$ 已位於最終正確位置。

---

處理右側子序列

處理：

$$[10,14,37,13,25,29]$$

取：

$$\text{pivot}=29$$

依序比較：

• $10\leq29$，留在左區；
• $14\leq29$，留在左區；
• $37>29$，留在右區；
• $13\leq29$，移入左區；
• $25\leq29$，移入左區。

最後將 pivot $29$ 放入兩區之間：

$$[10,14,13,25,29,37]$$

因此整體序列變為：

$$[7,10,14,13,25,29,37]$$

分割結果為：

$$[7]\quad [10,14,13,25]\quad [29]\quad [37]$$

$7$、$29$、$37$ 均已定位。

---

處理子序列 $[10,14,13,25]$

取最後一個元素：

$$\text{pivot}=25$$

因為：

$$10\leq25,\quad14\leq25,\quad13\leq25$$

所以 $25$ 已大於左側所有元素，分割後為：

$$[10,14,13,25]$$

整體序列不變：

$$[7,10,14,13,25,29,37]$$

分割結果為：

$$[10,14,13]\quad [25]$$

---

處理子序列 $[10,14,13]$

取：

$$\text{pivot}=13$$

逐一比較：

• $10\leq13$，留在左側；
• $14>13$，留在右側。

將 pivot $13$ 放入中間：

$$[10,13,14]$$

整體序列變為：

$$[7,10,13,14,25,29,37]$$

分割結果為：

$$[10]\quad [13]\quad [14]$$

所有子序列長度皆為 $1$，遞迴結束。

---