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

核心觀念

本題考查十進位整數轉換為二進位字串的方法。

二進位制的每一位只能是 $0$ 或 $1$。對非負整數 $N$ 反覆進行整數除法：

• $N \bmod 2$ 取得目前最低位元。
• $N \mathbin{//} 2$ 移除目前最低位元。
• 將每次取得的餘數由後往前排列，即得到二進位表示。

根據整數除法：

$$N = 2\left\lfloor\frac{N}{2}\right\rfloor + (N\bmod 2)$$

其中 $N\bmod 2$ 必為 $0$ 或 $1$。

解題方法

先處理負數：

$$N<0 \Rightarrow \text{return } \text{'NA'}$$

因為題目指定負數不進行二進位轉換。

對於 $N=0$，其二進位表示為 "0"，需特別處理，因為若直接進入 $N>0$ 的迴圈，迴圈不會執行。

對於 $N>0$：

1. 設定空字串 result。
2. 計算 $N\bmod 2$，取得最低位元。
3. 將該位元加到字串最前方。
4. 將 $N$ 更新為 $\lfloor N/2\rfloor$。
5. 重複直到 $N=0$。

虛擬碼

function ToBinary(N):
    if N < 0:
        return "NA"

    if N == 0:
        return "0"

    result = ""

    while N > 0:
        bit = N mod 2
        result = String(bit) + result
        N = N // 2

    return result

範例：$N=5$

依序計算：

$$5 \div 2 = 2\text{ 餘 }1$$ $$2 \div 2 = 1\text{ 餘 }0$$ $$1 \div 2 = 0\text{ 餘 }1$$

核心觀念

本題考查：

• Linked list 的節點與指標走訪。
• Recursive function 的基底情況與遞迴情況。
• 以分治方式求一串數值中的最大值。
• 時間與空間複雜度分析。

設節點結構如下：

Node:
    key       // 節點儲存的正整數
    next      // 指向下一個節點的指標

若串列為

$$k_1 \rightarrow k_2 \rightarrow \cdots \rightarrow k_n$$

則最大鍵值為

$$\max(k_1,k_2,\ldots,k_n)$$

題目保證所有 key 都是正整數，因此空串列回傳的 $0$ 可作為初始最大值，因為：

$$0 < k_i$$

解題方法

將問題拆成兩部分：

1. 目前節點的 key。
2. 從下一個節點開始的子串列最大值。

假設目前節點為 node，則：

$$\text{最大值} = \max\bigl(\text{node.key},\ \text{MaxKey(node.next)}\bigr)$$

當 node 為 NULL 時，代表已經走到串列尾端，直接回傳 $0$。

Recursive Pseudocode

function MaxKey(node):
    if node == NULL:
        return 0

    maxOfRest = MaxKey(node.next)

    if node.key > maxOfRest:
        return node.key
    else:
        return maxOfRest

亦可簡寫為：

function MaxKey(node):
    if node == NULL:
        return 0

    return max(node.key, MaxKey(node.next))

正確性說明

以遞迴結構證明。

基底情況

當 node == NULL 時，表示串列是空的。依題意，函式應回傳 $0$，程式正確。

遞迴情況

當 node 不為 NULL 時，函式先計算：

MaxKey(node.next)

依遞迴假設，此值正確代表剩餘子串列的最大 key。

接著比較：

• 目前節點的 node.key
• 剩餘子串列的最大值 MaxKey(node.next)

兩者較大者即為整個串列的最大值，因此函式回傳正確結果。

執行範例

核心觀念

本題考查兩個重點：

1. Max-oriented heap（最大堆積）

   • 完全二元樹。
   • 每個父節點的鍵值皆不小於其子節點。
   • 使用陣列儲存時，採用 1-based index：
     $\text{parent}(i)=\left\lfloor \frac{i}{2}\right\rfloor$

2. 最大堆積的插入與動態陣列擴充

   • 新元素先放在陣列最後，維持完全二元樹結構。
   • 再透過 上浮（swim／percolate up） 恢復堆積性質。
   • 陣列滿載時加倍容量，會產生攤銷成本。

---

解題方法：依序插入並上浮

依題意，依序插入：

$E,\ A,\ S,\ Y,\ Q,\ U,\ E,\ S,\ T,\ I,\ O,\ N$

每次插入至陣列尾端，再與父節點比較；若新元素較大，便與父節點交換，持續向上進行。

插入元素	插入後的最大堆積陣列
$E$	$[E]$
$A$	$[E,A]$
$S$	$[S,A,E]$
$Y$	$[Y,A,E,S]$
$Q$	$[Y,Q,E,S,A]$
$U$	$[Y,Q,U,S,A,E]$
$E$	$[Y,Q,U,S,A,E,E]$
$S$	$[Y,Q,U,S,A,E,E,S]$
$T$	$[Y,Q,U,T,A,E,E,S,S]$
$I$	$[Y,Q,U,T,A,E,E,S,S,I]$
$O$	$[Y,Q,U,T,O,E,E,S,S,I,A]$
$N$	$[Y,Q,U,T,O,N,E,S,S,I,A,E]$

以最後一次插入 $N$ 為例：

• $N$ 放入第 $12$ 格。
• 父節點位置為 $\lfloor 12/2\rfloor=6$，其值為 $E$。
• 因為 $N>E$，交換兩者。
• 交換後 $N$ 位於第 $6$ 格，其父節點為第 $3$ 格，值為 $U$。
• 因為 $N<U$，停止上浮。

因此最終陣列為：

$[Y,Q,U,T,O,N,E,S,S,I,A,E]$

其樹狀結構的父節點均大於或等於子節點，符合最大堆積性質。

---

插入一個元素的時間複雜度

新元素插入陣列尾端後，最壞情況必須一路上浮至根節點。

若堆積中有 $n$ 個元素，其高度為：

$h=\lfloor \log_2 n\rfloor$

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）的旋轉，以及「任意兩棵含有相同鍵值集合的 BST，都可以只靠旋轉互相轉換」的性質。

BST 的中序走訪結果必定是遞增鍵值序列：

$$1,2,\ldots,n$$

旋轉只會改變局部樹形，不會改變中序走訪順序，因此旋轉後仍然維持 BST 性質。

---

旋轉定義

設某一局部樹形如下，其中所有鍵值滿足：

$$A < x < B < y < C$$

右旋轉（right rotation）：

旋轉前：

        y
       / \
      x   C
     / \
    A   B

以 $y$ 為旋轉點、其左子節點 $x$ 上升，旋轉後：

        x
       / \
      A   y
         / \
        B   C

其中原本 $x$ 的右子樹 $B$ 會成為 $y$ 的左子樹。

左旋轉（left rotation）是右旋轉的反操作：

旋轉前：

      x
     / \
    A   y
       / \
      B   C

旋轉後：

        y
       / \
      x   C
     / \
    A   B

旋轉後，局部子樹的中序順序皆為：

$$A,x,B,y,C$$

所以 BST 的鍵值順序不會改變。

---

解題方法：先轉成右鏈，再反向還原

建立一棵所有節點都沿著右子指標排列的樹，稱為右鏈（right spine）：

1
 \
  2
   \
    3
     \
      ⋮
       \
        n

實際上右鏈的節點順序不一定從 $1$ 到 $n$ 以圖形直接表示，但其中序順序仍為 $1,2,\ldots,n$。

第一步：將 $T_1$ 轉成右鏈

從根節點開始，沿著樹往右處理：

1. 若目前節點有左子節點，對目前節點做右旋轉。
2. 右旋後，繼續檢查目前節點。
3. 若目前節點沒有左子節點，就沿著右子指標往下走。
4. 持續進行，直到所有節點都沒有左子節點。

概念上的程序如下：

current = root(T1)

while current != null:
    if current.left != null:
        rightRotate(current)
    else:
        current = current.right

每次右旋都會把某個左子節點提升，逐步消除樹中的左分支，最後得到右鏈。將這些右旋轉依序記錄為：

核心觀念

2-3 樹是一棵高度平衡的搜尋樹，每個節點具有以下形式：

• 2-節點：含有 $1$ 個鍵值與 $2$ 個子樹，例如 $[P]$。
• 3-節點：含有 $2$ 個鍵值與 $3$ 個子樹，例如 $[P\ X]$。
• 所有葉節點位於同一層。
• 節點內鍵值必須由小到大排列，子樹則依鍵值區間排列。

插入新鍵時，先依二元搜尋樹規則走到葉節點。若葉節點暫時形成 $3$ 個鍵值，便將其分裂：

$$[a\ b\ c]\longrightarrow [b] \quad\text{並將}\quad [a], [c] \text{分別作為左右子節點}$$

中間鍵值 $b$ 向上提升。若父節點也因此溢位，則繼續向上分裂。

---

解題方法與逐步插入

以下以方括號表示節點內的鍵值。

1. 插入 $Y$

$$[Y]$$

2. 插入 $L$

$$[L\ Y]$$

3. 插入 $P$

原葉節點形成 $[L\ P\ Y]$，分裂並將 $P$ 提升：

$$\begin{array}{c} [P]\\ /\quad \backslash\\ [L]\quad [Y] \end{array}$$

4. 插入 $M$

$M>P$，進入右側葉節點：

$$\begin{array}{c} [P]\\ /\quad \backslash\\ [L]\quad [M\ Y] \end{array}$$

5. 插入 $X$

右側葉節點形成 $[M\ X\ Y]$，提升 $X$：

$$\begin{array}{c} [P\ X]\\ /\quad|\quad\backslash\\ [L]\quad[M]\quad[Y] \end{array}$$

6. 插入 $H$

$H<P$，進入最左側葉節點：

$$\begin{array}{c} [P\ X]\\ /\quad|\quad\backslash\\ [H\ L]\quad[M]\quad[Y] \end{array}$$

7. 插入 $C$

最左側葉節點形成 $[C\ H\ L]$，提升 $H$：

$$\begin{array}{c} [H\ P\ X]\\ /\quad|\quad|\quad\backslash\\ [C]\quad[L]\quad[M]\quad[Y] \end{array}$$

此時根節點 $[H\ P\ X]$ 也溢位，提升中間鍵值 $P$，得到：

$$\begin{array}{c} [P]\\ /\quad\backslash\\ [H]\quad[X]\\ /\ \backslash\quad/\ \backslash\\ [C]\ [L]\quad[M]\ [Y] \end{array}$$

8. 插入 $R$

$R>P$ 且 $R<X$，進入 $[M]$ 與 $[Y]$ 之間的葉節點：

$$[M\ R\ Y]$$

核心觀念

本題考查兩個觀念：

1. 排序鏈結串列的搜尋

   • 由於串列已排序，可在目前節點值大於目標值時提前停止。
   • 但鏈結串列無法直接跳到中間節點，因此不能像陣列一樣使用二分搜尋。

2. 雙向鏈結串列的刪除

   • 已知待刪節點位置時，可透過其 prev 與 next 指標直接重新連結前後節點。
   • 不需要逐一搬移其他節點，因此刪除本身為常數時間。

解題方法

a. 判斷給定元素是否存在

從 head 開始，沿著 next 指標搜尋。

設目標值為 $e$，目前節點值為 $x$：

• 若 $x=e$，表示找到元素。
• 若 $x>e$，因串列已排序，後續節點值只會更大，因此可直接判定不存在。
• 若尚未回到 head，則繼續往下一個節點搜尋。
• 若完整繞行一圈仍未找到，表示不存在。

雖然排序可以讓搜尋提前結束，但最壞情況下仍須檢查接近全部 $n$ 個節點，例如：

• $e$ 為最大值；
• $e$ 不存在且大於大部分節點；
• $e$ 位於串列末端附近。

因此搜尋時間為：

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

最佳情況為一開始就找到，或第一個節點值已大於 $e$，此時為 $\Theta(1)$；但一般題目所問的複雜度採最壞情況，因此答案是：

$$\boxed{\Theta(n)}$$

b. 刪除元素 $e$，不包含尋找成本

核心觀念

本題考查二元樹的葉節點定義與遞迴分治法。

• 葉節點（leaf node）：同時滿足 left = null 與 right = null 的節點，也就是沒有任何子節點。
• 空樹不含葉節點，因此葉節點數為 $0$。
• 一般節點的葉節點數，等於其左子樹與右子樹葉節點數的總和。

設函數 LeafCount(T) 表示以節點 $T$ 為根的樹之葉節點數，則：

$$LeafCount(T)= \begin{cases} 0, & T=null\\ 1, & T.left=null \text{ 且 } T.right=null\\ LeafCount(T.left)+LeafCount(T.right), & \text{其他情況} \end{cases}$$

解題方法

使用遞迴由根節點向下處理：

1. 若輸入節點為 null，表示沒有樹，回傳 $0$。
2. 若輸入節點沒有左、右子節點，表示該節點是葉節點，回傳 $1$。
3. 若為一般節點，分別計算左子樹與右子樹的葉節點數，再將兩者相加。

Pseudocode

function CountLeaves(node):
    if node == null:
        return 0

    if node.left == null and node.right == null:
        return 1

    return CountLeaves(node.left) + CountLeaves(node.right)

正確性說明

對每個輸入節點分三種情況：

1. node == null：沒有任何節點，因此葉節點數為 $0$。