成大 113 年資管所 資料結構 參考答案

插入後（index:key，僅列非空）：0:0　4:23　6:6　7:7　8:45　9:28　10:29　11:11　12:12　13:30　14:33　15:34　16:49

刪除 12 後（須將後續受影響的 key 前移）：0:0　4:23　6:6　7:7　8:45　9:28　10:29　11:11　12:30　13:49　14:33　15:34

平均成功搜尋次數：$\alpha =12/19$，$\frac{1}{2}(1+\frac{1}{1-\frac{12}{19}})=\frac{13}{7}\approx 1.86$ 次。

甲：component 是圖中的極大連通子圖：其中任兩頂點皆有路徑相通，再加入任何其他頂點就不再連通。

乙：每個頂點先各自為一個 component；每輪同時為每個 component 選出最小對外邊，一次加入（重複的邊只加一次）並合併，直到只剩一個 component。

第 1 輪：加入 $1\text{-}3(2)$、$1\text{-}2(3)$、$7\text{-}8(3)$、$5\text{-}6(6)$、$3\text{-}4(7)$，得 $\{1,2,3,4\}$、$\{5,6\}$、$\{7,8\}$。

第 2 輪：加入 $4\text{-}6(9)$、$5\text{-}7(11)$，合成一個 component。

MST：$1\text{-}3(2)$、$1\text{-}2(3)$、$7\text{-}8(3)$、$5\text{-}6(6)$、$3\text{-}4(7)$、$4\text{-}6(9)$、$5\text{-}7(11)$，總權重 41。

(1) Heap Sort：bottom-up 建 Min-Heap，得 [1, 3, 2, 5, 9, 6, 4, 14, 15, 13, 10, 8, 7, 12, 10]；重複 $n-1$ 次「堆頂與未排序區末端交換、heap size 減 1、對新堆頂 heapify-down」。結果：15, 14, 13, 12, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

(2) Natural Merge Sort：

初始 run：[10] [15, 8, 3] [13, 6, 2] [14, 5] [9] [10, 1] [7] [12, 4]

第 1 輪：[15, 10, 8, 3] [14, 13, 6, 5, 2] [10, 9, 1] [12, 7, 4]

第 2 輪：[15, 14, 13, 10, 8, 6, 5, 3, 2] [12, 10, 9, 7, 4, 1]

第 3 輪：15, 14, 13, 12, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

AVL search tree 是每個節點的 Balance Factor（左子樹高 $-$ 右子樹高）皆屬於 $\{-1,0,1\}$ 的 BST。題目的樹每個節點 BF 皆在 $\{-1,0,1\}$ 且滿足 BST 排序，是 AVL tree。

插入 5：成為 6 的左子，7 的 BF 變成 2（LL 型），對 7 做單一右旋，6 取代 7 的位置，左子 5、右子 7。

（如簡答圖）

(a) $f(n)=O(g(n))$ 若且唯若存在正常數 $c$ 與 $n_0$，使所有 $n\ge n_0$ 皆有 $0\le f(n)\le c·g(n)$。

(b) ${\displaystyle {\sum }_{i=0}^n{i}^3={\left[\frac{n(n+1)}{2}\right]}^2=\frac{n^4+2n^3+n^2}{4}}$。

取 $c=1$、$n_0=1$：$\frac{n^4+2n^3+n^2}{4}\le n^4⟺n^2(3n+1)(n-1)\ge 0$，$n\ge 1$ 時恆成立，故為 $O(n^4)$。

設存在 $c,n_0$ 使 $\frac{n^4+2n^3+n^2}{4}\le c{n}^3$ 對所有 $n\ge n_0$ 成立，兩邊除以 $n^3$ 得 $\frac{n}{4}+\frac{1}{2}+\frac{1}{4n}\le c$，取 $n>4c$ 即矛盾，故不為 $O(n^3)$。

(a) $3n-2$

(b) 依 row-major 順序把 $|i-j|\le 1$ 的元素依序存入 $B$（$k$ 由 1 起算），$a_{ij}$ 存在 $B[k]$，$k=2i+j-2$。

(a) Stack 是後進先出（LIFO）的線性資料結構，插入（push）與刪除（pop）都只在同一端（top）進行。

(b) b b × 4 a × c × − 2 a × /

(c) 由左至右掃描 postfix，使用 operand stack：

• 遇運算元：push。
• 遇運算子：pop 兩次，先 pop 者為 op2、後 pop 者為 op1，組成 (op1 運算子 op2) 後 push 回 stack。

掃描完畢後，stack 中唯一的字串即為 infix 運算式。

(a) BST 是一棵二元樹，每個節點 $v$ 的左子樹所有 key $<v.key<$ 右子樹所有 key，且左右子樹也都是 BST。

(b) （如簡答圖）

(c) 每個節點多存 leftSize（左子樹節點數）：

struct Node { int key; int leftSize; Node *left, *right; };

Node* findKthSmallest(Node* root, int k) {
    if (root == nullptr) return nullptr;
    int rank = root->leftSize + 1;                 // 目前節點在其子樹中的名次
    if (k == rank) return root;
    if (k <  rank) return findKthSmallest(root->left,  k);
    return             findKthSmallest(root->right, k - rank);
}