115 年 國立中央大學資訊管理學系碩士班甲組《資料結構》

一、核心觀念

• 雙向鏈結串列 (Doubly Linked List)：每個節點同時保存前驅指標 prev 與後繼指標 next，適合在兩端頻繁插入、刪除或在任意位置前後移動。
• 雜湊表 (Hash Table)：將關鍵字映射到陣列索引，可在平均 $O(1)$ 時間完成搜尋、插入與刪除。
• 資料結構的組合：將雜湊表的鍵指向雙向鏈結串列的節點，即可同時保有 快速搜尋 與 保序 的特性。

(a) 選擇 Singly Linked List 還是 Doubly Linked List？

答案： 使用 Doubly Linked List。

理由：

1. 瀏覽紀錄的「返回 (Back)」與「前進 (Forward)」功能，本質上是沿著「時間序列」向前或向後移動指標。
2. 若使用 單向鏈結串列，只能沿 next 方向前進，若要支援「返回」必須從頭遍歷至當前節點的前驅，時間複雜度為 $O(n)$，不符合即時操作的需求。
3. 雙向鏈結串列 同時保存 prev 與 next，在任意節點上，只需一次指標移動即可完成「返回」或「前進」——時間複雜度 $O(1)$，且插入、刪除操作同樣為 $O(1)$（只改變相鄰節點的指標）。

(b) Doubly Linked List 節點結構與插入實作

節點結構（以 C++ 為例）

struct DNode {
    std::string url;   // 瀏覽的 URL
    DNode* prev;       // 前驅節點
    DNode* next;       // 後繼節點

    DNode(const std::string& u) : url(u), prev(nullptr), next(nullptr) {}
};

在指定節點 p 後插入新節點 newNode 的程式碼

void insertAfter(DNode* p, DNode* newNode) {
    // 1. 先把 newNode 接到 p 的後面
    newNode->prev = p;
    newNode->next = p->next;

    // 2. 若 p 原先有後繼，調整其 prev 指標
    if (p->next != nullptr) {
        p->next->prev = newNode;
    }

    // 3. 最後把 p 的 next 指向 newNode
    p->next = newNode;
}

時間/空間分析

• 時間複雜度：僅改變固定數目的指標，$O(1)$。
• 空間複雜度：每插入一個節點額外使用 $O(1)$ 記憶體（節點本身）。

(c) 結合 Hash Table 與 Doubly Linked List 以實現 O(1) 搜尋

1. 資料結構設計

核心觀念

二元搜尋樹（BST）中，每個節點的左子樹鍵值皆小於該節點，右子樹鍵值皆大於該節點。

• 前序走訪（Pre-order）：根節點 → 左子樹 → 右子樹。
• 後序走訪（Post-order）：左子樹 → 右子樹 → 根節點。
• 刪除具有兩個子節點的節點：以其中序後繼，也就是右子樹的最小值，取代該節點，再刪除後繼原本所在的節點。

解題方法

依原圖，根節點為 $50$；左子節點 $30$ 的左右子節點為 $20、40$，且 $20$ 的左子節點為 $10$。右子節點 $70$ 的左右子節點為 $60、85$，其中 $60$ 的右子節點為 $65$，$85$ 的左子節點為 $80$。

(a) 前序與後序走訪

前序依「根 → 左 → 右」遞迴處理：

• 先列根節點 $50$。
• 左子樹依序為 $30、20、10、40$。
• 右子樹依序為 $70、60、65、85、80$。

因此，前序走訪為：

後序依「左 → 右 → 根」遞迴處理：

• 左子樹依序為 $10、20、40、30$。
• 右子樹中，先完成以 $60$ 為根的子樹，得到 $65、60$；再完成以 $85$ 為根的子樹，得到 $80、85$；最後列出 $70$。
• 全樹最後列出根節點 $50$。

因此，後序走訪為：

核心觀念

• Heap（堆）：完全二元樹，父節點與子節點滿足特定序關係。
  • Min‑Heap：父節點 ≤ 任何子節點。
  • Max‑Heap：父節點 ≥ 任何子節點。
• Bottom‑up 建堆：從最後一個非葉節點開始，對每個節點執行 sift‑down（下沉）操作，使子樹皆為堆，最後整棵樹即成堆。
• 兩堆求中位數：利用一個 Max‑Heap（存放較小的一半）與一個 Min‑Heap（存放較大的一半）交替平衡，使兩堆大小差不超過 1，根節點即為中位數（或兩根的平均）。

(a) Bottom‑up 建構 Min‑Heap

原始陣列 (0‑index)

$A = [12,\;35,\;8,\;25,\;40,\;15,\;5,\;30,\;20]$

步驟

1. 計算最後非葉節點索引：$\displaystyle \lfloor\frac{n}{2}\rfloor-1 = \lfloor\frac{9}{2}\rfloor-1 = 3$。
2. 從索引 3 依序向前執行 sift‑down。

最終 Min‑Heap 陣列表示

$\boxed{[5,\;20,\;8,\;35,\;40,\;15,\;12,\;30,\;25]}$

核心觀念

• 本題考查 佇列 (Queue) 的實作方式。
• 觀念重點在於 循環佇列 (Circular Queue / Ring Buffer)：利用固定長度陣列，同時以兩個指標 front、rear，當指標走到陣列尾端時可「環回」到開頭，避免因前端已被刪除而產生的「假滿」情形。
• 需要保證 插入 (Enqueue) 與刪除 (Dequeue) 的時間複雜度皆為 $O(1)$，且不必搬移資料。

解題方法

1. 把陣列視為環形：將 rear、front 的運算改為「模 N」(mod N)。
   • 插入時寫入 array[rear]，之後 rear = (rear + 1) mod N。
   • 刪除時讀取 array[front]，之後 front = (front + 1) mod N。
2. 判斷佇列滿與空的條件
   • 空佇列：front == rear。
   • 滿佇列：為避免 front == rear 產生歧義，常用 預留一格 的技巧，即當 (rear + 1) mod N == front 時視為滿。此時實際可容納的元素數目為 N‑1。
3. 插入、刪除皆僅改變指標，不搬移資料，故時間複雜度 $Θ(1)$，空間使用為固定 $O(N)$。

解題技巧

• 預留一格：最簡單的滿/空判斷方式；若一定要使用全部 N 個儲存格，可額外維護一個計數器 size，但會多一個變數的讀寫。
• 避免除零錯誤：在實作 mod N 時若使用語言提供的 %（取餘）需注意負數情況，建議先加上 N 再取餘：(index + 1) % N。
• 偵測錯誤：在實務程式中，插入前先檢查「滿」狀態、刪除前先檢查「空」狀態，若違反則拋出例外或回傳錯誤代碼。

偽碼

核心觀念

迴文的判斷條件是：字串左右對稱位置的字元必須相同。若字串長度為 $n$，最多只需比較前半部與後半部，總共至多比較 $\lfloor n/2 \rfloor$ 組字元。

遞迴解法每次比較 S[left] 與 S[right]：

• 若兩者不同，字串不是迴文，回傳 false。
• 若兩者相同，縮小範圍，遞迴檢查 left + 1 到 right - 1。
• 當 left >= right 時，所有必要的字元都已通過比較，回傳 true。這也涵蓋奇數長度字串中間剩下一個字元的情況。

解題方法與偽程式碼

假設 left 與 right 是字串中的有效索引，且 right 指向最後一個字元。每次遞迴都將待檢查區間向內縮小兩格，直到區間相遇或交錯。

bool isPalindrome(char* S, int left, int right) {
    if (left >= right) {
        return true;
    }

    if (S[left] != S[right]) {
        return false;
    }

    return isPalindrome(S, left + 1, right - 1);
}

初始呼叫方式為：

isPalindrome(S, 0, strlen(S) - 1);

空字串的右索引為 -1，因此 left >= right 成立，回傳 true；長度為 1 的字串也會直接回傳 true。

時間與空間複雜度比較

令字串長度為 $n$。

遞迴解法：

核心觀念

• 最小生成樹 (MST)：在加權無向圖 $G=(V,E)$ 中，連通且總權重最小的樹。
• MST 的唯一性：若所有邊的權重皆不同，MST 唯一；若相同則只要保證仍為最小權重即可。
• 更新 MST 的關鍵：在原 MST $T$ 中加入新邊 $e_{\text{new}}=(u,v,W_{\text{new}})$ 會在 $T$ 與 $e_{\text{new}}$ 之間形成唯一一個 環 (cycle)。若環中存在比 $e_{\text{new}}$ 重的邊，將該最重邊移除即可得到新的 MST；若 $W_{\text{new}}$ 大於等於環中所有邊的權重，則 $T$ 本身仍是最小生成樹。

定理（交換性質）：對於任一生成樹 $T$，若向 $T$ 加入一條不在 $T$ 中的邊 $e$，則唯一的環中最大權重的邊必定不屬於任何 MST，除非 $e$ 的權重恰好等於該最大權重。

(a) 最有效率的更新演算法

步驟概述

1. 預處理（一次性）

   • 以任意根 $r$ 為根，對 $T$ 進行 深度優先搜尋 (DFS)，記錄每個節點的深度 depth[x]、父節點 parent[x]。
   • 建立 二進位抬升表 (Binary Lifting)：對每個節點 $x$，保存 up[k][x]（第 $2^k$ 個祖先）以及 maxEdge[k][x]（從 $x$ 往上走 $2^k$ 步時經過的最大權重邊）。
   • 這一步的時間與空間皆為 $O(|V|\log|V|)$。

2. 查詢（每一次新增邊）

   • 找出 $u$ 與 $v$ 在 $T$ 中的最近公共祖先 (LCA)，同時在上升過程中記錄 $u\;$→;$\text{LCA}$ 路徑與 $v\;$→;$\text{LCA}$ 路徑上最大的邊權重 $W_{\max}$。這可透過二進位抬升在 $O(\log|V|)$ 完成。
   • 比較：
     • 若 $W_{\text{new}} < W_{\max}$，則 $e_{\text{new}}$ 應加入 MST，且把環中權重為 $W_{\max}$ 的那條邊（唯一）從 $T$ 中刪除。
     • 若 $W_{\text{new}} \ge W_{\max}$，則 $T$ 已經是新的 MST，保持不變。

3. 更新資料結構（若發生置換）

   • 刪除的邊與新增的邊僅影響包含它們的兩條路徑；利用 Link‑Cut Tree（或 Euler Tour Tree + Segment Tree）可在 $O(\log|V|)$ 內完成樹的連接/切斷與最大邊權重的維護。此步驟在「僅需要一次更新」的情況下，可省去；若需多次動態變更，則必須使用上述動態樹結構。

完整演算法（單次更新，使用二進位抬升）

核心觀念

• 紅黑樹 (Red‑Black Tree, RBT)：滿足以下五條性質
  1. 每個節點為紅或黑。
  2. 根節點為黑。
  3. 所有葉子 NIL（外部 NIL）為黑。
  4. 任何紅節點的兩個子節點皆為黑（沒有相鄰的紅節點）。
  5. 任一節點到其各子孫葉子 NIL 的所有簡單路徑上，黑節點數目相同（稱為 黑高）。
• CLRS 插入：先作為普通二元搜尋樹的紅節點插入，然後依照「插入修正」(insert‑fixup) 透過重新著色與旋轉恢復上述五條性質。
• size 屬性：每個節點額外保存 size = 1 + size(left) + size(right)，在插入、刪除、旋轉時必須同步更新。
• 第 k 小 (order‑statistics)：若只利用 size，可在 $O(\log n)$ 時間找到第 $k$ 小鍵值：
  • 設 $r = \text{size}(x.\text{left}) + 1$ 為當前節點 $x$ 在排序中的秩。
  • 若 $k = r$，則 $x$ 即為答案；若 $k < r$，遞迴左子樹；若 $k > r$，遞迴右子樹且改為 $k-r$。

解題方法

1. 依序插入 30, 15, 40, 10, 20, 35, 50, 5，每次執行 CLRS 插入與修正。
2. 每次旋轉或重新著色後，自底向上更新受影響節點的 size：
   • 插入新節點時，其 size = 1。
   • 旋轉時，交換兩個節點的子樹結構，需重新計算被旋轉節點與其父節點的 size。
3. 最終樹形：畫出每個節點的 鍵值、顏色、size。
4. 利用 size 求第 5 小：從根節點開始，以上述 order‑statistics 步驟逐層比較，直至定位第 5 小鍵。

(a) 最終紅黑樹

          30B (size=8)
        /          \
   15R (5)        40B (3)
   /   \          /   \
10B(3) 20B(1) 35R(1) 50R(1)
 /
5R(1)

說明

• 各節點後的括號為 size。
• 顏色依 R/B 表示。
• 旋轉與重新著色的詳細過程略（符合 CLRS 第 13 章），最終滿足紅黑性質。

核心觀念

• 作用域 (scope)：程式區塊形成的層次，變數的可見性僅限於宣告所在的區塊與其內部。
• 符號表 (symbol table)：編譯器在每個作用域維護一張表，記錄 identifier → (scope level, value)。
• 遮蔽 (shadowing)：內層作用域若再次宣告同名變數，會暫時遮蔽外層的同名變數，查找時先從最近的（innermost）作用域往外找。

解題方法

1. 依照程式的執行順序，逐步模擬 宣告、指派 與 區塊結束。
2. 每當進入新區塊時 新增 一張符號表；每當離開區塊時 銷毀 該層的符號表。
3. 指派語句 var = expr 中，左值與右值的每一次出現都必須 查找 符號表，以確定其作用域與目前值。

(a) 符號表於生命週期結束時的內容

• Level 2（最內層）在 } 結束時銷毀，表中保留的最後值為 5。
• Level 1（外層）在外層 } 結束時銷毀，表中保留的最後值為 7 (由 y = x + 2 更新)。
• Level 0（全域）在程式結束時仍存，最終值為 3 (由 x = y + 1 更新)。

(b) y = x + 2 時參照的 x

(a) Phase 1 – 排序結果

$\boxed{(a,1),\;(ee,2),\;(cc,2),\;(ccd,3),\;(cca,3),\;(abc,3),\;(dddd,4),\;(fffff,5)}$

(b) Phase 2 – 雜湊表 (m = 4, h(name)=|name| mod 4)

(c) Phase 3 – AVL 樹

• 計算 $B_i$：
  $B_0=1,\;B_1=2,\;B_2=2,\;B_3=3$