113 年 國立中正大學資訊管理學系碩士班乙組《資料結構》

核心觀念

空間需求可分為：

$S(P)=C+S_P(I)$

其中：

• $C$：固定空間，與輸入規模無關。
• $S_P(I)$：變動空間，會隨輸入規模增加而增加。

本題採用資料結構教材對「變動空間」的定義。float list[] 在 C 的函式參數中會被視為指標，函式只接收陣列首位址，不會複製整個陣列；經典教材對此迭代版本的 sum 也定義其變動空間為 $0$。教材範例

解題方法

逐一判斷程式中的變數是否會隨 $n$ 增加而配置更多空間：

• list[]：實際上是指標，只儲存陣列首位址，不會在函式內建立 $n$ 個 float。
• n：一個整數，固定大小。
• tempsum：一個 float，固定大小。
• i：一個整數，迴圈中反覆使用同一個變數，不會每次迭代新增空間。

核心觀念

本題考查遞迴函式的執行步驟與遞迴關係式。n 每次遞減 $1$，直到 $n=0$，因此所有遞迴呼叫形成一條長度為 $n+1$ 的鏈。

題目未明定「一步」的細部分解方式；以下採用資料結構教材常見的計數口徑：

• 基底情況 return list[0] 計 $1$ 步。
• 每個非基底呼叫除遞迴子呼叫外，還需執行一次陣列取值與一次加法，共 $2$ 步。
• 子呼叫的成本納入下一層遞迴，不重複計算。

關鍵程式碼為：

if (n)
    return rsum(list, n - 1) + list[n - 1];

return list[0];

解題方法

設 $T(n)$ 為執行 rsum(list, n) 所需的總步驟數。

當 $n=0$ 時，不再遞迴，直接執行：

return list[0];

所以：

$$T(0)=1$$

當 $n\ge 1$ 時，函式先執行一次 rsum(list, n-1)，其成本為 $T(n-1)$；遞迴返回後，再取出 list[n-1] 並進行加法，共增加 $2$ 步。因此：

$$T(n)=T(n-1)+2$$

展開遞迴關係式：

解題要點

1. 由右至左掃描前綴式。
2. 碰到運算元(變數)直接壓入堆疊。
3. 碰到二元運算子時，彈出兩個堆疊頂端項op1、op2，形成新的後綴子式 op1 op2 operator，再壓回堆疊。
4. 最後堆疊唯一項即為完整的後綴式。

---

(A) -+-/abc*de*ac

逆序掃描	堆疊變化
c	c
a	c , a
*	ac*
e	ac* , e
d	ac* , e , d
*	ac* , de*
c	ac* , de* , c
b	ac* , de* , c , b
a	ac* , de* , c , b , a
/	ac* , de* , c , ab/

(A) &a->val 依照 C 語言的結合性，-> 的優先度高於 &，因此被解析為 &(a->val)，而非 (&a)->val，故 錯誤。

(B) 迷宮的每格只會被訪問一次，最壞情況需遍歷全部 $m \times p$ 個格子，時間複雜度為 $O(mp)$，正確。

(C) % 與 * 同階且自左至右結合，a%b*c 等價於 $(a\%b)\times c$，不是 $a\% (b\times c)$，故 錯誤。

核心觀念

本題考查兩個重點：

1. 循環佇列的索引循環
2. 佇列刪除操作與空佇列判斷

採用常見的循環佇列表示法：

• front 指向「目前佇列第一個元素之前的位置」。
• rear 指向目前佇列最後一個元素的位置。
• 空佇列條件：

$$front = rear$$

• front 往前移動一格時，必須使用取餘數，使索引超過陣列尾端後回到陣列開頭：

$$front \leftarrow (front+1)\bmod MAX\_QUEUE\_SIZE$$

此表示法會保留一個空格，因此實際可存放的元素數量最多為 $MAX\_QUEUE\_SIZE-1$。

解題方法

刪除循環佇列的第一個元素時，正確順序如下：

1. 先判斷佇列是否為空。
2. 將 front 往前移動一格，並處理循環。
3. 取出新的 front 位置上的元素。
4. 回傳該元素。

若先執行 front = front + 1，當佇列原本為空時，front 與 rear 會被錯誤地分開，導致空佇列判斷失效。因此，空佇列必須在移動索引前判斷。

原程式的錯誤

1. front = front+1 未處理循環

原程式：

front = front+1;

當 front 已經位於陣列最後一格時，再加一會變成 MAX_QUEUE_SIZE，超出合法索引範圍 $0$ 至 $MAX\_QUEUE\_SIZE-1$。

正確寫法：

front = (front + 1) % MAX_QUEUE_SIZE;

2. if (front = rear) 使用指定運算子

原程式：

if (front = rear)

= 是指定運算子，會把 rear 的值指定給 front，而不是比較兩者是否相等。指定後，條件式的結果還會依 rear 的值判斷，造成程式邏輯錯誤。

比較相等必須使用 ==：

if (front == rear)

3. 空佇列判斷位置錯誤

原程式先移動 front，再判斷 front == rear：

front = front+1;
if (front == rear)

核心觀念

本題考查單向鏈結串列的「就地反轉」。每個節點只有一個 link 指標，原本方向為：

$$A \rightarrow B \rightarrow C \rightarrow NULL$$

反轉後必須變成：

$$C \rightarrow B \rightarrow A \rightarrow NULL$$

不建立新節點，只重新設定各節點的 link。

三個指標的角色如下：

• lead：目前尚未處理的節點。
• middle：已經完成反轉的部分串列首節點。
• trail：暫存 lead 原本的下一個節點。

解題方法

每次處理 lead 時，必須依照下列順序操作：

1. 先保存下一個節點：

   trail = lead->link;
   

2. 將目前節點指向已反轉的部分：

   lead->link = middle;
   

3. 將目前節點設為反轉串列的新首節點：

   middle = lead;
   

4. 移至尚未處理的部分：

   lead = trail;
   

因此迴圈條件必須是 lead != NULL。當 lead 變成 NULL 時，代表所有節點都已處理完畢，middle 即為反轉後的首節點。

完整程式碼

list_pointer invert(list_pointer lead)
{
  list_pointer middle, trail;
  middle = NULL;

  while (lead != NULL) {
    trail = lead->link;
    lead->link = middle;
    middle = lead;
    lead = trail;
  }

  return middle;
}

指標變化示例

假設原串列為：

A -> B -> C -> NULL

初始狀態：

middle = NULL
lead   = A

第一次迴圈：

核心觀念

本題考查迷宮的深度優先搜尋與回溯。由目前位置依指定方向順序逐一嘗試；遇到牆壁、邊界或已走過的格子就略過，走進無路可走的位置時便回溯，改試下一個方向。

解題方法

左圖的移動順序為：$0$ 向東、$1$ 東北、$2$ 北、$3$ 西北、$4$ 西、$5$ 西南、$6$ 南、$7$ 東南。右圖是 $5\times5$ 迷宮，入口接在第 $1$ 列第 $1$ 欄，出口接在第 $5$ 列第 $5$ 欄；以 $(列,欄)$ 表示格子座標。

從 $(1,1)$ 沿東方前進至 $(1,2)$、$(1,3)$。頂列右側的通路會走到死路，因此搜尋回溯至 $(1,3)$，再走西南方向進入 $(2,2)$。

在 $(2,2)$，東、東北、北、西北方向分別遇到牆或已走過的格子；依順序接著檢查西方，發現 $(2,1)$ 是尚未走過的通路，因此先走到 $(2,1)$，再向南到 $(3,1)$。從此沿第 $3$ 列向東走至 $(3,5)$，再向南到 $(4,5)$。在 $(4,5)$，西南方向的 $(5,4)$ 可通行，接著向東到 $(5,5)$，抵達出口。

路徑格以 P 標示；0 是未列入最終路徑的通路，1 是阻塞格：