108 年 國立政治大學資訊科學系碩士班《資料結構與演算法》

核心觀念

Kruskal 演算法將所有邊依權重由小到大排序，逐一選取不會形成環的邊，直到選出 $|V|-1$ 條邊。連通圖的最小生成樹會包含所有頂點，且恰有 $|V|-1$ 條邊。

解題方法

圖中共有 $5$ 個頂點，邊及權重依序為：

按權重由小到大檢查：

核心觀念
本題測試對雜湊表 (hash table) 與平衡二元搜尋樹 (balanced BST, 如 AVL、Red‑Black Tree) 之時間與空間特性的比較。需了解以下定義：

• 雜湊表：透過雜湊函式 $h(k)$ 把鍵 $k$ 映射至陣列的索引位置，理想情況下存取、插入、刪除皆為 $O(1)$。
• 平衡二元搜尋樹：在每個節點保持左子樹鍵值皆小於節點鍵、右子樹鍵值皆大於節點鍵，且樹高受平衡條件限制，使得基本操作的最差時間為 $O(\log n)$。

解題方法
直接列舉兩項雜湊表相較於平衡二元搜尋樹的優勢，並針對每項說明 為何在理論與實務上會較佳。

1. 平均時間常數級 $O(1)$ 的存取效率
   • 雜湊表在理想情況（雜湊函式均勻且衝突少）下，查找、插入與刪除皆只需一次陣列存取，即 $O(1)$。
   • 平衡二元搜尋樹即便保持 $O(\log n)$ 的最差複雜度，仍需在樹的深度上做 $\Theta(\log n)$ 次比較與指標跳躍，對於大規模資料 ($n\gg 10^6$) 會有明顯的常數因子差距。
   • 此優勢在 頻繁的隨機存取（例如資料庫快取、字典查詢）情境下尤為顯著，因為每次操作僅涉及一次記憶體取值，降低快取未命中率。

核心觀念

這題要在一棵樹中找出最小頂點覆蓋：對每條邊，至少選取其中一個端點。樹沒有環，因此可以任選根節點，從葉節點往上計算每個子樹的最佳解，再合併各子樹的結果。

對每個節點 $v$，分別計算：

• $dp_{\text{選}}[v]$：選取 $v$ 時，$v$ 子樹內最小頂點覆蓋的大小。
• $dp_{\text{不選}}[v]$：不選取 $v$ 時，$v$ 子樹內最小頂點覆蓋的大小。

解題方法

設 $v$ 的子節點集合為 $\mathrm{children}(v)$。若選取 $v$，每個子節點可選可不選，取成本較小者；若不選取 $v$，為了覆蓋連接 $v$ 與子節點的邊，每個子節點都必須選取。因此：

葉節點沒有子節點，所以：

根節點 $r$ 的最小頂點覆蓋大小為：

核心觀念

• 計數排序 (Counting Sort)：當待排序的元素值域已知且上界為 $O(n)$ 時，可利用額外的長度為值域大小的計數陣列，以 $O(n)$ 時間完成排序。
• 穩定性：本題僅要求非遞減序，穩定性不關鍵，只要正確計算每個值的出現次數即可。
• 時間與空間分析：遍歷原序列一次取得計數，遍歷計數陣列一次輸出結果，總共執行 $2n+O(n)=O(n)$ 步驟；額外使用長度 $n+1$ 的陣列，空間 $O(n)$。

解題方法

1. 建立計數陣列

   • 宣告長度為 $n+1$（索引 $0\sim n$）的整數陣列 cnt，全部初始化為 $0$。
   • 依序讀取輸入的 $a_1,\dots ,a_n$，對於每個 $a_i$ 執行 cnt[a_i]++。此步驟統計每個正整數出現的次數。

2. 輸出排序結果

   • 從 $value = 1$ 到 $n$ 逐一檢查 cnt[value]。
   • 若 cnt[value] = k > 0，則在輸出序列中寫入 $k$ 個 $value$（例如在陣列 out 中連續填入）。

3. 完整流程

核心觀念

• 主定理（Master Theorem）：對形如 $T(n)=a\,T\!\left(\frac{n}{b}\right)+f(n)$ 的遞迴式，若 $a\ge 1,\;b>1$，則根據 $f(n)$ 與 $n^{\log_b a}$ 的比較可得漸近上界。
• 對數基底：$a=2,\;b=2$ ⇒ $\log_b a=\log_2 2 = 1$，故 $n^{\log_b a}=n^1=n$。
• 漸進緊界（tight bound）：若 $f(n)$ 與 $n^{\log_b a}$ 同階（即 $f(n)=\Theta\!\bigl(n^{\log_b a}\bigr)$），則根據主定理第 2 條，$T(n)=\Theta\!\bigl(n^{\log_b a}\log n\bigr)$。

解題方法

1. 寫出遞迴式的參數
   $T(n)=2\,T\!\left(\frac{n}{2}\right)+n$
   其中 $a=2,\;b=2,\;f(n)=n$。

2. 比較 $f(n)$ 與 $n^{\log_b a}$
   $n^{\log_b a}=n^{\log_2 2}=n$
   因而 $f(n)=\Theta\!\bigl(n^{\log_b a}\bigr)$。

3. 套用主定理第 2 條

   • 條件：若 $f(n)=\Theta\!\bigl(n^{\log_b a}\log^k n\bigr)$，其中 $k=0$（此處 $f(n)=\Theta(n)$），則
     $T(n)=\Theta\!\bigl(n^{\log_b a}\log^{k+1} n\bigr)=\Theta\!\bigl(n\log n\bigr)$

4. 驗證（可選）
   用遞迴樹或迭代展開亦可得到相同結果：

核心觀念

• Heap：一種滿二元樹（complete binary tree），滿足 heap property：
  • Min‑heap：任一節點的鍵值 $\le$ 其子節點的鍵值。
  • Max‑heap：任一節點的鍵值 $\ge$ 其子節點的鍵值。
• Priority Queue：以 Heap 實作的抽象資料型別，支援
  • Insert(key) $\mathcal{O}(\log n)$
  • Extract‑Min/Max $\mathcal{O}(\log n)$
  • Decrease‑Key（或 Increase‑Key） $\mathcal{O}(\log n)$

解題方法
題目要求「Give an application of the heap data structure」——即找出一個在演算法或系統中必須頻繁執行 插入、抽取最小（或最大）、鍵值更新，且欲在 $\log n$ 時間內完成的情境。典型應用：使用最小堆作為 Dijkstra 最短路徑演算法的優先佇列。

1. 於圖 $G=(V,E)$ 中，維持一個最小堆 $H$，鍵值為目前已知的最短路徑估計 $d[v]$（$v\in V$）。
2. 初始將源點 $s$ 的距離 $d[s]=0$ 插入堆，其餘 $d[v]=\infty$。
3. 每次執行 Extract‑Min 取得距離最小的未確定頂點 $u$，此步驟即 $\mathcal{O}(\log |V|)$。

核心觀念

1. 二元搜尋樹（Binary Search Tree, BST）性質：
   對於樹中任意節點 $x$：

   • 其左子樹中的所有鍵值（Key）皆嚴格小於 $x$ 的鍵值。
   • 其右子樹中的所有鍵值皆嚴格大於 $x$ 的鍵值。
   • 其左、右子樹亦各自為二元搜尋樹。

2. 平衡二元搜尋樹（Balanced Binary Search Tree, BBST）：

   • 廣義定義：樹的高度維持在 $O(\log n)$，使得搜尋、插入、刪除等操作的時間複雜度均為 $O(\log n)$。
   • AVL 樹嚴格平衡條件：對樹中任一節點，其左子樹與右子樹的高度差（平衡因子 Balance Factor, $BF$）滿足 $|BF| \le 1$。
   • 當資料為已排序的連續序列 $1, 2, \dots, n$ 且 $n = 2^k - 1$（此題 $n=7 = 2^3 - 1$）時，可構建出高度為最小理論值 $\lfloor \log_2 n \rfloor + 1 = 3$ 的完全二元樹（Complete Binary Tree），此結構同時也是完美二元樹（Perfect Binary Tree），平衡因子在每個節點皆為 $0$，為最理想的平衡狀態。

解題方法

本題給定一組已排序序列：$\{1, 2, 3, 4, 5, 6, 7\}$。

欲構建高度最小且完全平衡的二元搜尋樹，採用分治法（Divide and Conquer）：

1. 選取根節點：取已排序序列的正中間元素作為樹根（Root），以保證左右子樹的節點數完全均等。
   • 序列長度為 $7$，中間位置（第 4 個元素）為 4。
2. 劃分左右子樹：
   • 左子樹包含鍵值：$\{1, 2, 3\}$
   • 右子樹包含鍵值：$\{5, 6, 7\}$
3. 遞迴構建子樹：
   • 對左子序列 $\{1, 2, 3\}$ 取中間元素 2 作為左子節點；其左小孩為 1、右小孩為 3。
   • 對右子序列 $\{5, 6, 7\}$ 取中間元素 6 作為右子節點；其左小孩為 5、右小孩為 7。

核心觀念

• 二元堆（Binary Heap）：完全二元樹（所有層都滿，最後一層靠左填滿）之上滿足堆序性（Heap Property）。
  • 最小堆（Min‑Heap）：每個節點的鍵值 ≤ 其子節點的鍵值。
  • 最大堆（Max‑Heap）：每個節點的鍵值 ≥ 其子節點的鍵值。
• 陣列表示：對於根位於索引 $1$（或 $0$）的陣列，左子節點位於 $2i$（或 $2i+1$），右子節點位於 $2i+1$（或 $2i+2$），父節點位於 $\lfloor i/2 \rfloor$（或 $\lfloor (i-1)/2 \rfloor$）。
• 建堆（Build‑Heap）：自下而上對每個非葉節點呼叫 heapify（下沉），時間複雜度 $O(n)$。

解題方法
本題給定七個鍵值 $1,2,3,4,5,6,7$，要求「給出一個二元堆」即可。
因為鍵值已經是遞增序列，直接以最小堆的陣列表示即可滿足堆序性，同時保持完全二元樹結構。

1. 陣列建構
   $A = [1,2,3,4,5,6,7]$
   （若根從索引 $1$ 開始，則 $A[1]=1,\;A[2]=2,\;A[3]=3,\;A[4]=4,\;A[5]=5,\;A[6]=6,\;A[7]=7$）

2. 檢查堆序性

   • $i=1$: 左子 $A[2]=2$, 右子 $A[3]=3$, $1 \le 2,3$ ✔
   • $i=2$: 左子 $A[4]=4$, 右子 $A[5]=5$, $2 \le 4,5$ ✔
   • $i=3$: 左子 $A[6]=6$, 右子 $A[7]=7$, $3 \le 6,7$ ✔

   所有父節點均 ≤ 子節點，滿足最小堆條件。

3. 樹形圖（可選）

核心觀念

判斷單向鏈結串列是否有環，可使用 Floyd 快慢指標法：慢指標每次走一步，快指標每次走兩步。若串列無環，快指標會先到達 null；若有環，兩個指標進入環後，快指標每次相對慢指標多走一步，必定會追上慢指標。

圖中的箭頭由尾端節點指回前面的節點，形成環。

解題方法

從串列頭節點開始，令 slow 與 fast 都指向頭節點。每輪先確認 fast 與 fast.next 都不是 null，再令 slow 前進一步、fast 前進兩步：