108 年 國立臺灣大學工程科學及海洋工程學系碩士班丁組《資料結構（A）》

核心觀念

中序式（infix）將運算子放在兩個運算元之間，例如 $a+b$；後序式（postfix）則將運算子放在其運算元之後，例如 $ab+$。

轉換時遵守：

• 括號優先處理，括號本身不輸出。
• 乘法與除法優先於加法與減法。
• 同一優先權由左至右計算。
• 後序式中，每個運算子都接在其完整運算子之前。

運算子優先權如下：

$$*、/ \;>\; +、-$$

解題方法

採用「運算子堆疊法」：

1. 運算元直接輸出。
2. 左括號 $($ 推入堆疊。
3. 遇到右括號 $)$，持續彈出並輸出堆疊頂端運算子，直到遇到左括號；再將左括號移除。
4. 遇到運算子時，若堆疊頂端已有相同或更高優先權的運算子，先彈出輸出，再將目前運算子推入。
5. 掃描結束後，將堆疊中剩餘運算子依序彈出。

（a）$a * (b - c) / d$

原式的運算結構為：

$$\frac{a \times (b-c)}{d}$$

轉換步驟：

1. 讀到 $a$，直接輸出：$a$
2. 讀到 $*$，推入堆疊。
3. 讀到左括號，推入堆疊。
4. 讀到 $b$，輸出：$ab$
5. 讀到 $-$，推入堆疊。
6. 讀到 $c$，輸出：$abc$
7. 讀到右括號，彈出 $-$，輸出：$abc-$；移除左括號。
8. 讀到 $/$。堆疊頂端為 $*$，且 $*$ 與 $/$ 優先權相同，依左至右規則先輸出 $*$：$abc-*$
9. 將 $/$ 推入堆疊。
10. 讀到 $d$，輸出：$abc-*d$
11. 掃描結束，彈出 $/$。

因此：

$$\boxed{a\ (b\ c\ -)\ *\ d\ /}$$

不加空格時為：

$$\boxed{abc-*d/}$$

（b）$a + (b * c - d) * (e + f / g)$

原式的運算結構為：

$$a + \bigl((b \times c)-d\bigr)\times\left(e+\frac{f}{g}\right)$$

轉換步驟：

1. 讀到 $a$，輸出：$a$
2. 讀到 $+$，推入堆疊。
3. 讀到左括號，推入堆疊。
4. 讀到 $b$，輸出：$ab$
5. 讀到 $*$，推入堆疊。
6. 讀到 $c$，輸出：$abc$
7. 讀到 $-$。堆疊頂端為 $*$，優先權較高，先輸出 $*$：$abc*$
8. 將 $-$ 推入堆疊。
9. 讀到 $d$，輸出：$abc*d$

核心觀念

本題考查：

1. 單向鏈結串列（Singly Linked List）
2. 頭指標 head 與尾指標 tail 的維護
3. 尾端插入（append）
4. 鏈結串列節點數量 size 的更新

給定陣列 counts 後，對每個索引 $i$：

• 建立 counts[i] 個節點；
• 每個節點的資料值都設為 counts[i]。

因此，若：

counts = {1, 3, 2}

則建立：

1 → 3 → 3 → 3 → 2 → 2

最後：

• head 指向第一個節點；
• tail 指向最後一個節點；
• size = 1 + 3 + 2 = 6。

尾指標 tail 指向最後一個節點，而不是額外建立的虛擬節點；最後一個節點的 next 應為 null。

---

解題方法

建立節點時，分成兩種情況處理。

情況一：串列目前為空

若 head == null，代表這是建立的第一個節點，因此：

head = newNode
tail = newNode

此時頭尾指標都指向同一個節點。

情況二：串列已有節點

若串列已經有節點，將新節點接在尾端：

tail.next = newNode
tail = newNode

每建立一個節點，就將：

size++

如此即可同步維護節點數量。

---

完整類別與方法

以下以 Java 語法實作：

class SListNode {
    int data;
    SListNode next;

    SListNode(int data) {
        this.data = data;
        this.next = null;
    }
}

class SList {
    SListNode head;
    SListNode tail;
    int size;

    public SList() {
        head = null;
        tail = null;
        size = 0;
    }

    public void makeList(int[] counts) {
        // 重新建立串列前，先初始化串列狀態
        head = null;
        tail = null;
        size = 0;

        for (int i = 0; i < counts.length; i++) {
            int value = counts[i];

            if (value < 0) {
                throw new IllegalArgumentException(
                    "counts 中的元素不可為負數"
                );
            }

            // 建立 value 個資料值為 value 的節點
            for (int j = 0; j < value; j++) {
                SListNode newNode = new SListNode(value);

                if (head == null) {
                    // 建立第一個節點
                    head = newNode;
                    tail = newNode;
                } else {
                    // 接到尾端
                    tail.next = newNode;
                    tail = newNode;
                }

                size++;
            }
        }
    }
}

---

核心觀念

本題考查漸進符號的定義：

• $f(n)\in O(g(n))$：存在常數 $c>0$ 與 $n_0$，使得對所有 $n\ge n_0$，
  $0\le f(n)\le c\,g(n)。$

• $f(n)\in \Theta(g(n))$：存在常數 $c_1,c_2>0$ 與 $n_0$，使得對所有 $n\ge n_0$，
  $0\le c_1g(n)\le f(n)\le c_2g(n)。$

判斷時只需考慮 $n$ 足夠大時的成長率，有限個小 $n$ 值不影響 $O$ 或 $\Theta$ 的判定。

解題方法與選項分析

（a）$\displaystyle \frac{1}{n-50}\in O(n)$

此敘述正確。

當 $n\ge 100$ 時，

$$n-50\ge \frac{n}{2}。$$

因此，

$$\frac{1}{n-50} \le \frac{2}{n} \le 2n \qquad (n\ge 100)。$$

取 $c=2$、$n_0=100$，即可符合 $O(n)$ 的定義：

$$0\le \frac{1}{n-50}\le 2n。$$

所以，

$$\boxed{\frac{1}{n-50}\in O(n)}。$$

事實上，當 $n$ 足夠大時，

$$\frac{1}{n-50}=\Theta\left(\frac{1}{n}\right)，$$

而 $\frac{1}{n}=O(n)$，故原敘述成立。

（b）$\displaystyle \frac{n^2}{n+\log n}\in\Theta(n^2)$

此敘述錯誤。

對足夠大的 $n$，有 $\log n\le n$，因此

$$n\le n+\log n\le 2n。$$

取倒數後得

核心觀念

本題考查以 bottom-up heap construction 建立最小堆積（min heap）。

採用 1-based indexing 時：

• 節點 $i$ 的左子節點為 $2i$
• 右子節點為 $2i+1$
• 節點 $i$ 的父節點為 $\lfloor i/2\rfloor$
• 最後一個非葉節點為 $\lfloor n/2\rfloor$

建立最小堆積時，從最後一個非葉節點開始，依序對

$$i=\left\lfloor\frac n2\right\rfloor,\left\lfloor\frac n2\right\rfloor-1,\ldots,1$$

執行向下調整（sift-down）。每次將目前節點與其值最小的子節點比較；若目前節點較大，就交換，並繼續向下調整。

---

解題方法

原始陣列共有 $n=8$ 個元素，因此最後一個非葉節點為

$$\left\lfloor\frac 82\right\rfloor=4$$

處理順序為 $4,3,2,1$。

原始陣列：

$$[7,\ 2,\ 6,\ 9,\ 3,\ 5,\ 1,\ 8]$$

1. 處理索引 4

索引 4 的值為 $9$，其子節點為索引 8，值為 $8$。

因為 $9>8$，交換索引 4 與索引 8：

$$[7,\ 2,\ 6,\ 8,\ 3,\ 5,\ 1,\ 9]$$

索引 8 已是葉節點，調整結束。

---

2. 處理索引 3

索引 3 的值為 $6$，其子節點為：

• 索引 6：$5$
• 索引 7：$1$

兩個子節點中較小者為 $1$。因為 $6>1$，交換索引 3 與索引 7：

$$[7,\ 2,\ 1,\ 8,\ 3,\ 5,\ 6,\ 9]$$

索引 7 為葉節點，調整結束。

---

3. 處理索引 2

索引 2 的值為 $2$，其子節點為：

• 索引 4：$8$
• 索引 5：$3$

最小子節點為 $3$。因為 $2<3$，已符合最小堆積條件，不需交換：

$$[7,\ 2,\ 1,\ 8,\ 3,\ 5,\ 6,\ 9]$$

---

4. 處理索引 1

索引 1 的值為 $7$，其子節點為：

• 索引 2：$2$
• 索引 3：$1$

最小子節點為 $1$。因為 $7>1$，交換索引 1 與索引 3：

解題關鍵

• 前序遍歷順序：根 → 左子樹 → 右子樹。
• 若每個節點保存其整個子樹的節點數 subtreeSize，則可在 $O(d)$（$d$ 為子樹深度）內定位第 $k$ 個節點：
  $\text{若 }k=1\Rightarrow\text{回傳根元素}$
  $\text{若 }k-1\le\text{左子樹大小}\Rightarrow\text{在左子樹遞迴 }preorderElementAt(k-1)$
  $\text{否則}\Rightarrow\text{在右子樹遞迴 }preorderElementAt\big(k-1-\text{左子樹大小}\big)$

類別與欄位

public class TreeNode<E> {
    E element;                 // 節點儲存的資料
    TreeNode<E> left, right;   // 左、右子節點
    int subtreeSize;           // 以此節點為根的子樹節點總數（含自身）

    public TreeNode(E e) {
        element = e;
        left = right = null;
        subtreeSize = 1;       // 初始只有自己
    }

    // 更新 subtreeSize，通常在插入/刪除時呼叫
    void updateSize() {
        int l = (left  != null) ? left.subtreeSize  : 0;
        int r = (right != null) ? right.subtreeSize : 0;
        subtreeSize = 1 + l + r;
    }
}

遞迴方法

核心觀念

二分圖（bipartite graph）的定義是：可以將所有頂點分成兩個互斥集合 $X$ 與 $Y$，使每條邊的兩端分別位於 $X$ 與 $Y$。

等價地，二分圖可以使用兩種顏色為頂點著色，使得每條邊連接不同顏色的頂點。因為若將兩種顏色的頂點分別放入 $X$ 與 $Y$，即可得到二分圖的兩個集合。

判定的關鍵原則為：

• 與某頂點距離為偶數的頂點使用同色。
• 與某頂點距離為奇數的頂點使用異色。
• 若發現某條邊的兩端已被分配相同顏色，則圖形不是二分圖。

此方法也等價於判斷圖中是否含有奇數長度的環：

$$G\text{ 為二分圖}\iff G\text{ 不含奇數長度的環}$$

解題方法

採用 BFS 或 DFS 進行圖形走訪，並在走訪過程中進行二色著色。

令每個頂點的顏色為：

• 未著色
• 顏色 $0$
• 顏色 $1$

演算法步驟如下：

1. 將所有頂點設為未著色。
2. 逐一檢查每個頂點。若某頂點尚未著色，將它指定為顏色 $0$，並從該頂點開始 BFS 或 DFS。
3. 走訪目前頂點 $u$ 的每一條邊 $(u,v)$：
   • 若 $v$ 尚未著色，將 $v$ 設為與 $u$ 不同的顏色，即 $$color[v]=1-color[u]$$ 然後繼續走訪 $v$。
   • 若 $v$ 已著色，檢查是否滿足 $$color[v]\neq color[u]$$
   • 若 $color[v]=color[u]$，表示存在衝突，立即判定 $G$ 不是二分圖。
4. 若所有連通元件都完成走訪且沒有發生衝突，則判定 $G$ 是二分圖。此時可將顏色 $0$ 的頂點放入 $X$，顏色 $1$ 的頂點放入 $Y$。

必須逐一處理所有尚未著色的頂點，因為無向圖可能不是連通圖。每個連通元件都必須分別進行二色著色。

正確性說明

核心觀念

本題考查兩種排序法：

• Bubble sort：反覆比較相鄰元素，若左值大於右值便交換，使較大的元素逐步往陣列右側移動。
• Bucket sort：先將資料依值域分配至多個桶子，再分別排序各桶並串接；判斷是否為 in-place 的重點，在於是否需要與輸入陣列大小無關的額外儲存空間。

---

(a) Bubble sort 排序過程

初始陣列為：

$$15\quad 4\quad 2\quad 27\quad 10$$

採用由左至右掃描的標準 Bubble sort，每一輪結束後，當輪最大的未排序元素會固定在最右側。

第 1 輪

依序比較相鄰元素：

1. 比較 $15$ 與 $4$：

$$15>4\Rightarrow 交換$$ $$4\quad 15\quad 2\quad 27\quad 10$$

2. 比較 $15$ 與 $2$：

$$15>2\Rightarrow 交換$$ $$4\quad 2\quad 15\quad 27\quad 10$$

3. 比較 $15$ 與 $27$：

$$15<27\Rightarrow 不交換$$ $$4\quad 2\quad 15\quad 27\quad 10$$

4. 比較 $27$ 與 $10$：

$$27>10\Rightarrow 交換$$ $$4\quad 2\quad 15\quad 10\quad 27$$

第 1 輪結束：

$$\boxed{4\quad 2\quad 15\quad 10\quad 27}$$

此時最大值 $27$ 已固定在最後位置。

第 2 輪

只需處理前四個元素：

1. 比較 $4$ 與 $2$：

$$4>2\Rightarrow 交換$$ $$2\quad 4\quad 15\quad 10\quad 27$$

2. 比較 $4$ 與 $15$：

$$4<15\Rightarrow 不交換$$

3. 比較 $15$ 與 $10$：

$$15>10\Rightarrow 交換$$ $$2\quad 4\quad 10\quad 15\quad 27$$

第 2 輪結束：

$$\boxed{2\quad 4\quad 10\quad 15\quad 27}$$

此時 $15$ 已固定在倒數第二個位置。

第 3 輪

處理前面三個元素：

核心觀念

2-3-4 樹是階數為 $4$ 的 B-tree，具有以下性質：

• 每個節點最多含 $3$ 個鍵值。

• 節點內鍵值皆由小到大排列。

• 除根節點外，每個內部節點至少含 $1$ 個鍵值。

• 所有葉節點位於同一層。

• 插入時，若即將進入的節點已含 $3$ 個鍵值，必須先分裂：

  $[a,b,c]\longrightarrow [a]\quad \uparrow b\quad [c]$

也就是將中間鍵值 $b$ 提升至父節點。

本題考查「插入順序是否必然造成不同的 2-3-4 樹結構」。答案取決於每次分裂時被提升的鍵值與最後各子樹的分布。

---

解題方法：第一種插入順序

插入順序為：

$4,6,12,15,3,5$

1. 插入 $4,6,12$：

$[4,6,12]$

2. 插入 $15$ 前，根節點已滿，先分裂：

$[4,6,12]\longrightarrow [4]\quad \uparrow 6\quad [12]$

再將 $15$ 插入右子節點：

$$\begin{array}{c} [6]\\ /\quad \backslash\\ [4]\quad [12,15] \end{array}$$

3. 插入 $3$：

$[4]\longrightarrow [3,4]$

4. 插入 $5$：

$[3,4]\longrightarrow [3,4,5]$

因此第一棵樹為：

          [6]
         /   \
 [3, 4, 5]  [12, 15]

---

解題方法：第二種插入順序

插入順序為：

$12,3,6,4,5,15$

1. 插入 $12,3,6$：

$[3,6,12]$