115 年 國立中山大學電機工程學系碩士班丙組《資料結構》

核心觀念

在 open addressing 中，所有資料都直接放在 hash table 陣列內。發生碰撞時，必須依照 probe sequence 逐格尋找。例如 linear probing 使用：

$$p_i(x)=(h(x)+i)\bmod n,\qquad i=0,1,2,\ldots$$

搜尋時，遇到目標元素表示成功；遇到「從未使用過的空槽」才能判定元素不存在。

刪除資料時不能直接把槽位標成一般的 EMPTY，因為後續元素可能是經由碰撞探查到該位置之後才存放的。因此通常使用特殊標記 DELETED，也稱為 tombstone。搜尋遇到 DELETED 時必須繼續探查，插入時才可 reutilize 該槽位。

若目前有 $k$ 個有效元素、$t$ 個 tombstone，則：

$$\alpha_{\text{有效}}=\frac{k}{n}$$

但搜尋實際感受到的探查負載接近：

$$\alpha_{\text{探查}}=\frac{k+t}{n}$$

所以，$k$ 變小並不代表搜尋一定變快；碰撞形成的 cluster、tombstone 數量，以及被刪除的是哪一個元素，都會影響平均搜尋時間。

---

(a) 為什麼 $k$ 減少時平均搜尋時間未必減少

以容量 $n=10$、雜湊函數

$$h(x)=x\bmod 10$$

以及 linear probing 為例。依序插入 $0,10,20,30,40$，它們的初始雜湊位置全部是 $0$：

索引	0	1	2	3	4	5
內容	0	10	20	30	40	EMPTY

成功搜尋各元素所需探查次數如下：

元素	0	10	20	30	40
探查次數	1	2	3	4	5

因此平均搜尋次數為：

$$\frac{1+2+3+4+5}{5}=3$$

現在刪除元素 $10$。若直接把索引 $1$ 設為 EMPTY，搜尋 $20$ 時會從索引 $0$ 開始：

$$0\rightarrow 1$$

搜尋在索引 $1$ 遇到空槽後就會誤判不存在，即使 $20$ 實際位於索引 $2$。

因此索引 $1$ 必須標記為 DELETED：

索引	0	1	2	3	4	5
內容	0	DELETED	20	30	40	EMPTY

此時有效元素數量由 $5$ 降為 $4$，但搜尋剩餘元素的探查次數為：

• 搜尋 $0$：$1$ 次
• 搜尋 $20$：$0\rightarrow\text{DELETED}\rightarrow20$，共 $3$ 次
• 搜尋 $30$：$4$ 次
• 搜尋 $40$：$5$ 次

平均搜尋次數變成：

$$\frac{1+3+4+5}{4} =\frac{13}{4} =3.25$$

也就是：

$$k:5\rightarrow4,\qquad \text{平均搜尋次數}:3\rightarrow3.25$$

原因有兩層：

1. tombstone 仍會被搜尋穿越
   DELETED 雖然不再存放有效元素，卻不能作為搜尋終止條件。因此有效元素數量下降，探查路徑長度不一定縮短。

2. 平均值取決於剩餘哪些元素
   被刪除的 $10$ 原本只需探查 $2$ 格，刪除後這個較短的搜尋成本從平均值中消失；剩餘元素仍位於 cluster 尾端，平均值便會上升。

若將刪除後的資料重新雜湊，只有 $0,20,30,40$ 時可排列成：

核心觀念

Insertion sort 由左至右處理陣列。第 $i$ 次插入時，已排序的前綴中，所有大於目前元素的值都必須向右移動一格。

令 $I(A)$ 表示陣列中的 inversion 數量：

$$I(A)=\left|\{(p,q)\mid p<q,\ A[p]>A[q]\}\right|.$$

Insertion sort 的執行時間與 inversion 數量直接相關：

$$T(n)=\Theta\bigl(n+I(A)\bigr).$$

其中 $n$ 來自逐一掃描陣列，$I(A)$ 來自元素的移動與比較。

---

(a) $k$-亂序陣列

令元素原本位於索引 $p$，排序後位於索引 $r_p$。由 $k$-亂序定義：

$$|r_p-p|\le k.$$

考慮一組 inversion $(p,q)$，其中 $p<q$ 且 $A[p]>A[q]$。排序後，$A[p]$ 必須位於 $A[q]$ 的右側，因此：

$$r_p\ge r_q+1.$$

又因為每個元素最多偏離最終位置 $k$：

$$r_p\le p+k,\qquad r_q\ge q-k.$$

因此：

$$p+k\ge r_p\ge r_q+1\ge q-k+1,$$

整理得：

$$q-p\le 2k-1.$$

這表示 inversion 只能發生在相距 $O(k)$ 的元素之間。對每個元素而言，至多與 $O(k)$ 個附近元素形成 inversion，所以：

$$I(A)=O(nk).$$

因此：

$$T(n)=\Theta(n+I(A)) =O\bigl(n+nk\bigr) =O\bigl(n(k+1)\bigr).$$

題目已明確指出 $k$ 為常數，因此 $k+1$ 也是常數：

$$T(n)=O(n).$$

此外，即使陣列原本已排序，Insertion sort 仍須逐一掃描 $n$ 個元素，因此：

$$T(n)=\Omega(n).$$

所以實際上：

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

---

(b) 前三分之一大的元素全部位於前一個三分之一

令：

核心觀念

本題考查：

1. Max-Heap 定義：對每一個節點，其鍵值皆大於或等於子節點，即
   $A[\text{parent}] \geq A[\text{child}]$

2. 陣列表示完全二元樹：採用 1-based index 時，節點 $i$ 的子節點為：

   $\text{left}(i)=2i,\qquad \text{right}(i)=2i+1$

3. Bottom-Up Build-Max-Heap：葉節點本身已是合法 heap，因此從最後一個非葉節點開始，向前執行 max_heapify。

   $$$$

\left\lfloor \frac{n}{2} \right\rfloor
=\left\lfloor \frac{10}{2} \right\rfloor=5$$

所以處理順序為：

$$$$

max_heapify 每次都將目前節點與較大的子節點交換，直到符合 max-heap 性質。

解題方法與推導

原始陣列採 1-based index 表示：

$$A=\{3,2,1,6,5,7,9,11,14,18\}$$

第 1 步：處理節點 $i=5$

節點 $A[5]=5$，其左子節點為 $A[10]=18$。

因為 $18>5$，交換：

$$\{3,2,1,6,18,7,9,11,14,5\}$$

第 2 步：處理節點 $i=4$

節點 $A[4]=6$，子節點為：

$$A[8]=11,\qquad A[9]=14$$

較大的子節點為 $14$，交換 $6$ 與 $14$：

$$\{3,2,1,14,18,7,9,11,6,5\}$$

第 3 步：處理節點 $i=3$

節點 $A[3]=1$，子節點為：

$$A[6]=7,\qquad A[7]=9$$

較大的子節點為 $9$，交換：

小明的遞迴演算法 錯誤。

反例

設 $G$ 為 4 個頂點的簡單連通加權圖，分成兩個子集合

$V_{1}=\{u_{1},u_{2}\},\qquad V_{2}=\{v_{1},v_{2}\}$

• 只在 $V_{1}$ 內有邊 $(u_{1},u_{2})$，權重 $w=10$。
• 只在 $V_{2}$ 內有邊 $(v_{1},v_{2})$，權重 $w=10$。
• 所有跨集合的邊都有權重 $1$，即

$(u_{1},v_{1}),\;(u_{1},v_{2}),\;(u_{2},v_{1}),\;(u_{2},v_{2})\quad w=1$

依照小明的方法

• $T_{1}$ 為 $V_{1}$ 的 MST，只有邊 $(u_{1},u_{2})$，成本 $10$。
• $T_{2}$ 為 $V_{2}$ 的 MST，只有邊 $(v_{1},v_{2})$，成本 $10$。

判斷原則
搜尋 $350$ 時，每一步比較後的走向必須符合 BST 規則：

• 若目標 $<$ 目前節點，下一個節點必須 較小（左子樹）
• 若目標 $>$ 目前節點，下一個節點必須 較大（右子樹）
  且在同一條路徑上，從上層節點往下的值範圍隨走向持續縮小。

檢查各選項

選項	比較與走向	是否符合範圍
(A) 137→250→430→380→324→365→350	右、右、左、左、右、左	全部符合