113 高普考高考三級 資訊處理 資料結構 考古題詳解

核心觀念

每個人接到電話後，只會撥給兩位「尚未接到電話」的人，因此每通電話都讓一位新的人接到通知。最先打電話的人不計入接到電話的人數。

解題方法

把打電話的人視為二元樹的節點；最先打電話者為根，接到電話的人依接聽先後形成其餘節點。若共有 $200$ 人，則最多有 $200-1=199$ 人接到電話，因此總撥打通數為 $199$ 通。

若第一人先撥給兩人，之後每位接到電話的人都撥給兩位尚未接到電話者，傳播會持續到剩下的人都接到電話為止。每位接到電話的人都會打電話；最先打電話的人也會打電話。因此題目所述流程下，200 人都會打電話，無人不會打電話。

解題技巧

每通電話都新增一位接聽者，所以電話總數等於「接到電話的人數」，也就是總人數扣掉最先打電話的人。不要把最後一位接到電話的人誤認為不會打電話：依題意，他也會撥給兩位尚未接到電話的人；但此時已無符合條件的對象，因此不會增加通數。

**【答案】**共撥打 $199$ 通電話；不會打電話的人數為 $0$ 人。

（二）二元樹遍歷

核心觀念

前序追蹤順序為「根、左子樹、右子樹」；後序追蹤順序為「左子樹、右子樹、根」。已知前序與後序時，若某節點只有一個子節點，僅憑這兩種順序無法判定該子節點在左側或右側，因此一般不能唯一決定二元樹。

解題方法

由前序順序可知根為 $T$；由後序順序末項也可確認根為 $T$。移除根後，前序以 $S$ 開始，後序以 $F$ 開始，故 $S$ 是 $T$ 的子樹根。

核心觀念

快速排序（Quick Sort）的時間複雜度，取決於每次選出的樞紐（pivot）能否將資料分成大小接近的兩部分。每一層分割與處理的總成本為 $\Theta(n)$；若分割極度不平衡，遞迴深度便會增加，最壞情況下總成本達 $\Theta(n^2)$。

解題方法

（一）造成最壞情況的條件

當每次選出的樞紐都是目前子序列中的最小值或最大值時，分割結果會是：

• 一邊有 $0$ 個元素；
• 另一邊有 $n-1$ 個元素。

例如，若樞紐固定選第一個元素，而輸入資料已按遞增或遞減排列，每次分割都可能形成上述情形。每一層只排除樞紐本身，其餘 $n-1$ 個元素仍須繼續遞迴處理，因此遞迴深度約為 $n$。

（二）最壞時間複雜度推導

設 $T(n)$ 為排序 $n$ 個元素所需時間。每次分割需檢查目前子序列中的元素，成本為 $\Theta(n)$；最壞情形只剩一個大小為 $n-1$ 的子問題，因此：

反覆展開：

核心觀念

二元搜尋適用於已依遞增或遞減順序排列的資料。每次比較搜尋鍵與目前區間的中間元素，便能排除一半不可能包含目標值的資料，因此搜尋區間會逐步縮小。

以下以陣列 A[0..n-1] 遞增排列為例，搜尋鍵為 x。若找到，回傳其索引；若不存在，回傳 -1。

解題方法

遞迴程式

BinarySearchRecursive(A, low, high, x):
 if low > high:
 return -1

 mid = low + floor((high - low) / 2)

 if A[mid] == x:
 return mid
 else if x < A[mid]:
 return BinarySearchRecursive(A, low, mid - 1, x)
 else:
 return BinarySearchRecursive(A, mid + 1, high, x)

初始呼叫為：

BinarySearchRecursive(A, 0, n - 1, x)

low > high 表示搜尋區間已空，目標值不存在。若 x < A[mid]，只搜尋左半部；若 x > A[mid]，只搜尋右半部。每次遞迴都將區間縮小，因此最終會找到目標或遇到空區間。

非遞迴程式

BinarySearchIterative(A, n, x):
 low = 0
 high = n - 1

 while low <= high:
 mid = low + floor((high - low) / 2)

 if A[mid] == x:
 return mid
 else if x < A[mid]:
 high = mid - 1
 else:
 low = mid + 1

 return -1

核心觀念

• **雙向佇列（Deque）**允許從前端或後端加入、刪除元素。題目要判斷輸入順序固定為 $1,2,\ldots,7$ 時，能否透過兩端操作產生指定輸出。
• **堆疊（Stack）**遵循後進先出（LIFO）：每次 Pop 只能移除目前位於堆疊頂端的元素。輸入順序固定時，輸出排列須符合這項限制。

（一）以 Deque 產生 $5174236$

能夠產生。以下以「由左至右」表示 Deque 內容順序：

輸出依序為 $1,5,2,4,3,7,6$，因此確實得到 $5174236$。

（二）$1,2,3,4$ 依序 Push 的所有輸出組合