109 身心障礙特考三等 資訊處理 資料結構 考古題詳解

核心觀念

本題考「已排序陣列中的兩數和」問題。利用陣列遞增的性質，從兩端同時搜尋，稱為雙指標法（two-pointer technique）。

設左指標 $i=1$、右指標 $j=n$，比較 $A[i]+A[j]$ 與目標值 $s$：

• 若總和等於 $s$，即找到一組符合條件的索引。
• 若總和小於 $s$，固定右端時，左端往右移會使總和增加，因此令 $i$ 加一。
• 若總和大於 $s$，固定左端時，右端往左移會使總和減少，因此令 $j$ 減一。

解題方法

TwoSum(A[1:n], s):
 i ← 1
 j ← n

 while i < j:
 total ← A[i] + A[j]

 if total = s:
 印出 i, j
 return

 else if total < s:
 i ← i + 1

 else:
 j ← j - 1

 印出 0

迴圈條件採用 $i<j$，確保選取的是兩個相異位置。題目保證陣列元素互不相同；即使元素不互異，此條件仍可避免同一個位置被使用兩次。

正確性證明

**迴圈不變量：**每次進入迴圈時，若存在符合條件的索引組 $(p,q)$，其中 $p<q$，則至少有一組解仍位於目前尚未排除的範圍 $i\le p<q\le j$。

• **初始化：**開始時 $i=1$、$j=n$，所有可能的索引組都在範圍 $[i,j]$ 內，因此不變量成立。
• 維持：
• 若 $A[i]+A[j]<s$，對任何 $q\le j$，都有 $A[i]+A[q]\le A[i]+A[j]<s$。

核心觀念

本題考查最小權重擴張樹（Minimum Spanning Tree, MST）的環圈性質與割集性質。

• 環圈性質：在一個環圈中，若某條邊的權重嚴格大於環圈內其他邊，則該邊不會出現在任何最小權重擴張樹中。否則，刪除該邊並加入環圈上的另一條邊，就能得到權重較小的擴張樹。
• 橋接邊（bridge）：刪除後會使圖不連通的邊。每條橋接邊都必須出現在任何擴張樹中，否則無法連接橋接邊兩側的頂點。

題目規定所有邊權重互不相同，因此圖的最小權重擴張樹唯一。

解題方法

對最大權重邊 $e=(u,v)$，檢查它是否一定位於某個環圈中。

若 $e$ 位於環圈中，因為 $e$ 是全圖權重最大的邊，且權重互不相同，它就是該環圈中唯一最重的邊。依環圈性質，$e$ 不會被選入最小權重擴張樹。

若 $e$ 是橋接邊，則它不屬於任何環圈，且必須出現在每一棵擴張樹中。因此，題目（一）不能只憑「全圖最重」就判定 $e$ 一定不在最小權重擴張樹內。

選項分析

（一）錯誤

反例：令 $G$ 為三個頂點 $a,b,c$ 組成的路徑，邊為 $ab$ 與 $bc$，權重分別為 $1$ 與 $2$。

核心觀念

本題考查遞迴程式的時間複雜度，以及用數學歸納法證明時間複雜度下界。對遞迴程式，先依程式結構列出時間成本遞迴式，再與斐波那契數的定義比較。

題目指定「$==$」、「$=$」、「$+$」和 return 各花一單位時間。每次呼叫 Fib(n) 都會執行兩次條件比較；若 $n>1$，還會執行一次加法及一次 return。

解題方法

令 $T(n)$ 表示執行 Fib(n) 所需的時間。當 $n=0$ 時，執行一次比較及一次 return，因此 $T(0)=2$。當 $n=1$ 時，執行兩次比較及一次 return，因此 $T(1)=3$。

當 $n>1$ 時，程式執行兩次比較，接著遞迴呼叫 Fib(n-1) 與 Fib(n-2)，並將兩個結果相加後 return。因此：

接著以數學歸納法證明 $T(n)>F_n$。

證明

基礎情形：

核心觀念

本題考查二元堆積（binary heap）的陣列表示法、由下而上的堆積建構，以及堆積建構的線性時間證明。

將 $A[1:n]$ 視為完全二元樹的層序儲存時，索引 $i$ 的左子節點為 $2i$，右子節點為 $2i+1$；索引不大於 $\lfloor n/2\rfloor$ 的節點才有子節點。sift 利用子樹已是堆積的條件，沿著一條根至葉的路徑向下調整。

（一）Max-heap 的定義

$A[1:n]$ 是 max-heap，須符合：

1. 其對應的二元樹為完全二元樹。
2. 每個非葉節點的鍵值都不小於其子節點；以索引表示，對所有 $1\leq i\leq\lfloor n/2\rfloor$：

因此，根節點 $A[1]$ 是整個堆積中的最大值。

（二）副程式 sift(A,r,n)

解題方法

呼叫前，$A[r]$ 的左右子樹都已是 max-heap。若 $A[r]$ 已不小於兩個子節點，就已符合堆積條件；否則將它與較大的子節點交換。交換後，可能違反堆積條件的只有交換後的子節點位置，因此只需在該子樹繼續向下調整。

演算法

sift(A, r, n):
 while 2r <= n:
 c = 2r // 左子節點
 if c + 1 <= n and A[c + 1] > A[c]:
 c = c + 1 // 選較大的子節點
 if A[r] >= A[c]:
 return
 swap(A[r], A[c])
 r = c

若節點只有左子節點，c 仍指向左子節點；若沒有子節點，迴圈結束。每次交換都把原根鍵值往下一層移動，且較大的子節點升到父節點位置，故此位置的堆積條件成立。繼續處理被交換下去的鍵值，最後整棵以原 $A[r]$ 為根的子樹成為 max-heap。

時間複雜度

每一層只做常數次比較與至多一次交換，並且每次交換後都往下一層。因此最多走過子樹高度 $h(r)$ 層：

此界也符合最壞情況：若原根鍵值一路小於沿途較大的子節點，就會走到葉節點，花費 $\Theta(h(r))$ 時間。

（三）線性時間建構 max-heap