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

（一）程式是否必須滿足有限性

核心觀念

**有限性（finiteness）要求演算法在有限步驟內終止。**重點在於演算法對其所處理的每一筆合法輸入，都必須能在有限時間內完成並產生結果；若某筆合法輸入會讓程序永遠執行，該程序就不符合有限性。

程式是演算法的實作形式，但程式也可能設計成持續服務的系統，例如作業系統、伺服器或監控程式，預定在執行期間不停止。因此，不能單憑「程式會一直執行」就判定它違反演算法的有限性。

解題方法與理由

先區分「演算法的終止要求」與「程式的預定執行方式」：

• 若程式要完成一項可結束的計算，例如排序、搜尋或計算總和，則其實作應確保每筆合法輸入都能在有限步驟內結束，否則無法完成該演算法的工作。
• 若程式是作業系統、伺服器或即時監控程式等持續運作的系統，其整體執行期間可以不終止。它可反覆等待事件、接收請求並處理工作；每次個別工作仍可在有限時間內完成。

因此，**程式本身不必一律在有限時間內終止；有限性是對演算法的要求，而持續運作的程式可以包含或實作反覆執行的演算法步驟。**判斷時須看題目所指的是整個程式的執行期間，還是演算法對一筆輸入的處理是否能完成。

（二）有限性以外的四項演算法特性

1. 明確性（definiteness）

核心觀念

本題考「For 迴圈的起始值、遞增步幅、終止條件」及「等差數列求和」。依虛擬碼，$i$ 從 $1$ 開始，每次增加 $7$；凡是 $i\leq150$，就執行一次迴圈本體。迴圈本體將當次的 $i$ 加入 $s$。

解題方法

第 $k$ 次迴圈開始時，$i$ 的值為

要執行迴圈，必須符合

因此 $7(k-1)\leq149$，即 $k\leq22.28\ldots$，最多執行 $22$ 次。實際參與累加的數依序為

最後一項為 $1+7(21)=148$，下一項是 $155$，已超過上限 $150$。

（一）$s$ 是這 $22$ 個數的總和。使用等差數列求和公式：

核心觀念

前置式（prefix）又稱波蘭表示法，運算子寫在運算元之前。二元運算子後方必須依序接上兩個運算式，例如 $-AB$ 表示 $A-B$。

使用堆疊計算前置式時，從右向左掃描：

• 遇到運算元就推入堆疊。
• 遇到二元運算子，就依序彈出兩個值：第一個是左運算元，第二個是右運算元；計算後將結果推回堆疊。

解題方法

原式由左至右為：

$- \quad + \quad - \quad + \quad 1 \quad 2 \quad * \quad 3 \quad 4 \quad 5 \quad / \quad 6 \quad 3$

由右至左逐項處理：

核心觀念

本題考查兩種在資料集合中尋找指定關鍵值的搜尋方法：循序搜尋法（sequential search）與二元搜尋法（binary search）。比較時應掌握搜尋前提、比較方式、時間複雜度，以及資料是否需要排序。

令資料筆數為 $n$，搜尋目標為 $x$。若找到，回傳其位置；若未找到，回報搜尋失敗。

解題方法

循序搜尋法

循序搜尋不要求資料預先排序。從第一筆資料開始，依序將每筆資料與 $x$ 比較：

1. 若目前資料等於 $x$，停止並回傳該位置。
2. 若不相等，移至下一筆資料繼續比較。
3. 若檢查完所有資料仍未找到，則搜尋失敗。

例如，在 $[18, 7, 25, 13]$ 中搜尋 $25$，依序比較 $18$、$7$、$25$，第三次比較即找到目標。

若目標在第 $k$ 筆，需比較 $k$ 次；若目標不在資料中，需比較 $n$ 次。因此：

• 最佳情況：目標位於第一筆，時間複雜度為 $O(1)$。
• 最差情況：目標位於最後一筆或不存在，時間複雜度為 $O(n)$。
• 平均情況：若目標等機率出現在任一位置，成功搜尋平均比較次數為 $\frac{n+1}{2}$，時間複雜度為 $O(n)$。
• 空間複雜度：迭代實作只需固定額外空間，為 $O(1)$。

二元搜尋法

二元搜尋要求資料已依關鍵值排序，且能有效存取中間位置，例如使用陣列。每次檢查搜尋範圍的中間元素，再依比較結果保留可能包含目標的一半範圍：

1. 設定目前搜尋範圍的左、右界線。
2. 取中間位置 $m=\left\lfloor\frac{左界+右界}{2}\right\rfloor$，比較該位置的值與 $x$。
3. 若相等，搜尋成功。
4. 若 $x$ 小於中間值，保留左半部；若 $x$ 大於中間值，保留右半部。
5. 重複以上步驟，直到找到目標或搜尋範圍為空。

例如，在排序資料 $[3, 8, 12, 17, 24, 31, 40]$ 中搜尋 $24$：先比較中間值 $17$，因 $24>17$ 而保留右半部；再比較該範圍的中間值 $31$，因 $24<31$ 而保留左側；最後比較 $24$，找到目標。