113 年 國立臺灣大學生物機電系碩士班丁組《資料結構》

核心觀念

堆疊（Stack）遵守 後進先出（Last In, First Out, LIFO）：

• push：將新元素加入堆疊頂端。
• pop：移除堆疊頂端元素。

若使用單向鏈結串列，最適合把串列的前端（head）直接當作堆疊頂端（top）。原因是：

• 在前端插入節點只需調整指標。
• 從前端刪除節點也只需調整指標。
• 不需要走訪整個串列尋找尾端或尾端的前一個節點。

解題方法

設堆疊頂端指標為 top：

$$top \rightarrow \text{第一個節點} \rightarrow \text{第二個節點} \rightarrow \cdots$$

Push：從前端加入

建立新節點 newNode，使其指向目前的頂端，再更新 top：

push(value):
    newNode = allocate Node
    newNode.data = value
    newNode.next = top
    top = newNode

若原本堆疊為：

top → A → B → C

執行 push(D) 後：

top → D → A → B → C

Pop：從前端移除

先檢查堆疊是否為空，再取出 top 的資料，將 top 往下一個節點移動：

pop():
    if top == null:
        report "Stack Underflow"

    value = top.data
    oldTop = top
    top = top.next
    deallocate oldTop
    return value

若原本堆疊為：

top → D → A → B → C

執行 pop() 後會移除 D：

top → A → B → C

核心觀念

本題考查圖形的兩種表示法轉換：

• 鄰接矩陣（adjacency matrix）：使用二維陣列 $A$ 表示圖。若頂點 $i$ 與頂點 $j$ 之間有邊，則 $A[i][j]$ 為非零值；沒有邊時通常為 $0$。
• 鄰接串列（adjacency list）：對每一個頂點建立一個串列，記錄所有與該頂點相鄰的頂點。

假設共有 $n$ 個頂點，採用 0-based indexing：

$$A[i][j] \neq 0$$

表示存在一條由頂點 $i$ 指向頂點 $j$ 的邊。

對於無向圖，鄰接矩陣通常滿足：

$$A[i][j] = A[j][i]$$

掃描矩陣時，無向邊會自然加入兩次，分別放入兩個端點的鄰接串列，這正是鄰接串列表示無向圖的標準形式。

解題方法

逐列掃描鄰接矩陣：

1. 建立包含 $n$ 個空串列的陣列 adjList。
2. 對每一個矩陣位置 $(i,j)$ 進行檢查。
3. 若 $A[i][j] \neq 0$，將頂點 $j$ 加入頂點 $i$ 的鄰接串列。
4. 掃描完成後，回傳 adjList。

矩陣的第 $i$ 列代表頂點 $i$ 的所有出邊，因此只要檢查該列中哪些位置為非零值，即可建立頂點 $i$ 的鄰接串列。

參考偽碼

以下偽碼適用於無權圖，並以 $0$ 表示沒有邊：

function MatrixToAdjacencyList(A):
    n ← number of rows in A

    adjList ← array of n empty lists

    for i ← 0 to n - 1:
        for j ← 0 to n - 1:
            if A[i][j] ≠ 0:
                append j to adjList[i]

    return adjList

回傳值說明

函式回傳一個陣列 adjList，其中：

• adjList[i] 是頂點 $i$ 的鄰接串列。
• 串列中的每一個元素 $j$ 表示圖中存在一條邊 $i \to j$。
• 若頂點 $i$ 沒有任何相鄰頂點，則 adjList[i] 為空串列。

例如，若：

核心觀念

本題考查兩個資料結構的結合：

1. 雙向循環鏈結串列
   • 每個節點有 next 與 prev。
   • 尾端節點的 next 指向頭節點，頭節點的 prev 指向尾端節點。
   • 刪除節點時，只需調整前後節點的指標：

$$\text{current.prev.next} \leftarrow \text{current.next}$$ $$\text{current.next.prev} \leftarrow \text{current.prev}$$

2. 搜尋樹儲存已出現元素
   • 若元素尚未出現，將其加入搜尋樹。
   • 若元素已出現，代表是重複元素，從鏈結串列中刪除。
   • 保留每個元素第一次出現的節點，因此能維持原本元素的出現順序。

設原鏈結串列共有 $n$ 個節點，最後有 $k$ 個不同元素，其中 $k \leq n$。

---

解題方法

從頭節點開始巡訪鏈結串列，並使用搜尋樹 S 記錄已看過的元素。

對每個節點：

• 若節點內容不在 S 中：
  • 將內容插入 S。
  • 保留此節點。
• 若節點內容已在 S 中：
  • 將此節點從雙向循環鏈結串列中移除。

由於必須在刪除目前節點前先儲存 current.next，否則刪除後可能失去後續巡訪位置。

為了避免刪除頭節點造成巡訪終止條件改變，第一次遇到的節點一定保留，因此原本的 head 不會被刪除。

---

a. 虛擬碼

以下虛擬碼使用二元搜尋樹或平衡搜尋樹皆可。Search(S, x) 用來搜尋元素，Insert(S, x) 用來插入元素。

RemoveDuplicates(head):

    if head == NIL:
        return

    S ← empty search tree
    current ← head

    repeat:

        nextNode ← current.next

        if Search(S, current.data) != NIL:
            // current 是重複節點，從雙向循環鏈結串列中刪除
            current.prev.next ← current.next
            current.next.prev ← current.prev

        else:
            // current 第一次出現，保留並記錄
            Insert(S, current.data)

        current ← nextNode

    until current == head

刪除指標調整說明

假設鏈結串列局部為：

A ⇄ current ⇄ B

刪除 current 後，應改為：

A ⇄ B

因此需要執行：

current.prev.next ← current.next
current.next.prev ← current.prev

例如原串列為：

1 ⇄ 3 ⇄ 3 ⇄ 2 ⇄ 4 ⇄ 2

巡訪結果如下：

目前元素	搜尋樹狀態	動作
1	尚未出現	保留，插入 1
3	尚未出現	保留，插入 3
3	已出現	刪除
2	尚未出現	保留，插入 2
4	尚未出現	保留，插入 4
2	已出現	刪除

最後得到：

1 ⇄ 3 ⇄ 2 ⇄ 4

---

b. 使用一般二元搜尋樹時的複雜度

一般二元搜尋樹的搜尋與插入時間取決於樹高 $h$：

$$T_{\text{search}} = O(h)$$

核心觀念

二三樹的「二節點」含一個鍵值；「三節點」含兩個鍵值，並連接三個子樹。轉成二元搜尋樹時，三節點的兩個鍵值必須相鄰相連，且維持搜尋順序。

本解採用以下表示法：三節點中的較小鍵值作為該二元搜尋樹子樹的根，較大鍵值接在其右側；兩者之間的邊以 粗體 標示，表示這條邊屬於同一個三節點。

解題方法

原圖的二三樹結構如下：

• 根三節點為 $[E,J]$。
• 根的三個子樹依序為 $[A,C]$、$[H]$、$[L]$。
• $[A,C]$ 是三節點；$[H]$、$[L]$ 是二節點。

4(a) 轉成二元搜尋樹

將根三節點 $[E,J]$ 表示為 $E$ 與右子節點 $J$，並將 $E$、$J$ 之間的邊標示為三節點內的邊。$[A,C]$ 同理表示為 $A$ 與右子節點 $C$。

          E
         / \
        A   **J**
         \   / \
        **C** H   L

圖中的子樹位置對應原二三樹：

• $E$ 的左子樹是 $[A,C]$，所以接到 $A$。
• $J$ 的左、右子樹分別是 $[H]$、$[L]$。
• $A$、$C$ 下方未畫出鍵值的子樹皆為空。

4(b) 刪除根並以左子樹的鍵值取代

核心觀念

本題考查兩個重點：

1. 二元最小堆（binary min heap）
   • 完全二元樹。
   • 每個父節點的值皆小於或等於子節點：
     $A[\mathrm{parent}(i)] \le A[i]$
   • 採用 1-based array 時： $$$$

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

2. 由下而上的 Heapify
   • 將陣列轉成最大堆時，從最後一個非葉節點開始，依序向上執行 MaxHeapify。
   • 最後一個非葉節點的位置為：
     $\left\lfloor\frac{n}{2}\right\rfloor$

---

解題方法

a. 依序插入並維持最小堆

每次將新元素放在目前堆的最後位置，再向上比較；若新元素小於父節點，便交換，直到符合最小堆條件。

以下使用 1-based array 表示。

插入 11

插入後：

$$[11]$$

樹形：

11

---

插入 9

先放在最後，再與父節點 11 比較並交換：

$$[11,9]\rightarrow[9,11]$$

樹形：

    9
   /
 11

---

插入 12

12 大於父節點 9，不需交換：

$$[9,11,12]$$

樹形：

    9
   / \
 11  12

---

插入 14

14 大於父節點 11，不需交換：

$$[9,11,12,14]$$

樹形：

      9
    /   \
  11     12
 /
14

---

插入 3

先插入最後位置：

$$[9,11,12,14,3]$$

3 小於父節點 11，交換：

$$[9,3,12,14,11]$$

3 再與父節點 9 比較並交換：

$$[3,9,12,14,11]$$

樹形：

       3
     /   \
    9     12
   / \
 14  11

---

插入 15

15 大於父節點 12，不需交換：

$$[3,9,12,14,11,15]$$

樹形：

       3
     /   \
    9     12
   / \   /
 14  11 15

---

插入 7

先插入最後位置：

$$[3,9,12,14,11,15,7]$$

7 小於父節點 12，交換：

$$[3,9,7,14,11,15,12]$$

7 大於父節點 3，因此停止。

樹形：

       3
     /   \
    9      7
   / \    / \
 14  11 15  12

---

插入 8

先插入最後位置：

$$[3,9,7,14,11,15,12,8]$$

8 小於父節點 14，交換：

$$[3,9,7,8,11,15,12]$$

8 小於父節點 9，再交換：

$$[3,8,7,9,11,15,12]$$

8 大於父節點 3，停止。

樹形：

        3
      /   \
     8      7
    / \    / \
   9  11 15  12

---

插入 1

先插入最後位置：

$$[3,8,7,9,11,15,12,1]$$

1 小於父節點 9，交換：

$$[3,8,7,1,11,15,12,9]$$

1 小於父節點 8，交換：

$$[3,1,7,9,11,15,12,8]$$

1 小於父節點 3，交換：

$$[1,3,7,9,11,15,12,8]$$

因此最終最小堆為：