110 年 國立政治大學資訊管理學系碩士班科技組《資料結構》

1. Min‑Heap (array, 1 索引)

插入次序	插入鍵	失衡調整	最終陣列 (前 11 個)
1	2	–	[2]
2	4	–	[2,4]
3	26	–	[2,4,26]
4	25	–	[2,4,26,25]
5	13	–	[2,4,26,25,13]
6	14	14 與 26 交換 → 左旋於 2	[2,4,14,25,13,26]
7	51	–	[2,4,14,25,13,26,51]
8	9	9 與 25 交換 → 左旋於 2	[2,4,14,9,13,26,51,25]
9	17	–	[2,4,14,9,13,26,51,25,17]
10	43	–	[2,4,14,9,13,26,51,25,17,43]
11	68	–	[2,4,14,9,13,26,51,25,17,43,68]

最終最小堆：[2, 4, 14, 9, 13, 26, 51, 25, 17, 43, 68]

---

2. 雙重雜湊 (N = 17)

$$h(k)=k\bmod 17,\qquad d(k)=\bigl(13-k\bmod13\bigr)\pmod{13}\;(d=0\Rightarrow13)$$

鍵	h(k)	d(k)	探測序列 (index)	放置位置
2	2	11	2	2
4	4	9	4	4
26	9	13	9	9
25	8	1	8	8

使用已建好的 heap（第 I.1）排序

1. 若建的是 max‑heap，執行 Heap‑Sort：
   • 初始已完成 $O(n)$ 建堆。
   • 迭代 $i=n\ downto\ 2$：
     • 交換根節點與第 $i$ 個元素（取得目前最大值），
     • 對長度 $i-1$ 的子堆呼叫 heapify（下沉）$O(\log n)$。
   • 迴圈結束後，陣列由大到小有序；若欲升序，使用 min‑heap 同理。
2. 時間複雜度：建堆 $O(n)$ + $n-1$ 次下沉 $O(n\log n)$ ⇒ $O(n\log n)$。
3. 空間複雜度：原地 $O(1)$（若使用額外陣列則 $O(n)$）。

使用已建好的 AVL 樹（第 I.3）排序

1. 將所有鍵已插入 AVL 樹（已平衡），此步驟在題目中已完成。
2. 以 中序走訪（In‑order Traversal）取得鍵的遞增序列：

核心觀念

本題考查兩種算術運算式求值方法：

1. 二元運算式樹（binary expression tree）
2. 兩個堆疊（two stacks）：一個存運算子，一個存運算元

運算優先順序為：

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

同一優先順序的運算子採由左至右結合，因此原式等價於：

$$((((13+5)-(6\times3))+4)-6)+(9\div3)$$

---

一、使用二元樹遞迴求值

解題方法

二元運算式樹的規則如下：

• 葉節點是運算元，例如 $13、5、6$
• 內部節點是運算子，例如 $+、-、\times、/$
• 每個運算子節點的左子樹代表左運算式，右子樹代表右運算式

本題的運算式樹如下：

                         +
                      /     \
                     -       /
                   /   \    / \
                  +     6  9   3
                /   \
               -     4
             /   \
            +     *
           / \   / \
          13  5 6   3

其結構表示：

$$\left(\left(\left(13+5\right)-\left(6\times3\right)\right)+4-6\right)+\left(9\div3\right)$$

遞迴演算法

Evaluate(node):
    if node 是葉節點:
        return node.value

    leftValue  = Evaluate(node.left)
    rightValue = Evaluate(node.right)

    if node.operator == '+':
        return leftValue + rightValue
    if node.operator == '-':
        return leftValue - rightValue
    if node.operator == '*':
        return leftValue * rightValue
    if node.operator == '/':
        return leftValue / rightValue

此方法採用後序走訪（postorder traversal）：

$$\text{左子樹} \rightarrow \text{右子樹} \rightarrow \text{根節點}$$

計算過程

由最底層的運算開始：

$$13+5=18$$ $$6\times3=18$$ $$18-18=0$$ $$0+4=4$$ $$4-6=-2$$ $$9\div3=3$$

因此根節點的加法為：

$$-2+3=1$$

複雜度

若運算式樹共有 $n$ 個節點：

• 每個節點只走訪一次，時間複雜度為

$$O(n)$$

• 遞迴呼叫堆疊的空間複雜度為

$$O(h)$$

其中 $h$ 為樹高；若樹極度偏斜，最壞情況為 $O(n)$。

---

二、使用兩個堆疊求值

解題方法

使用：

• operators：儲存運算子
• operands：儲存數值

掃描運算式時遵守以下規則：

1. 讀到運算元，直接推入 operands
2. 讀到運算子時：
   • 若堆疊頂端運算子的優先順序較高或相同，先進行堆疊頂端運算
   • 再將目前運算子推入 operators
3. 掃描結束後，依序處理剩餘運算子

由於本題的運算子皆為左結合，因此判斷條件為：

$$\operatorname{precedence}(\text{stack top}) \geq \operatorname{precedence}(\text{current operator})$$

進行一次運算的程序

從 operands 取出兩個值時，先取出的是右運算元：