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

核心觀念

本題考遞迴函式的「變動空間需求」，重點是計算遞迴呼叫期間同時存在的啟動記錄（activation records）數量。

每次呼叫 rsum 需保存：

• list：陣列位址，計 1 個 word
• n：整數參數，計 1 個 word
• return address：遞迴返回位址，計 1 個 word

因此每個啟動記錄需要 $3$ 個 word。list[] 傳遞的是位址，不會在每次遞迴時複製整個陣列。

解題方法

當初始值為 $n=6$ 時，呼叫順序為：

$$rsum(6)\rightarrow rsum(5)\rightarrow rsum(4)\rightarrow rsum(3)\rightarrow rsum(2)\rightarrow rsum(1)\rightarrow rsum(0)$$

因此共有：

$$6-0+1=7$$

個啟動記錄。rsum(0) 尚未返回前，這 7 層都同時存在，形成最大堆疊空間。

核心觀念

此函式進行兩個 $n \times m$ 矩陣的逐元素相加：

$$c[i][j]=a[i][j]+b[i][j]$$

外層索引 $i$ 遍歷 $n$ 列，內層索引 $j$ 遍歷每列的 $m$ 個元素，因此：

$$i=0,1,\ldots,n-1$$

共有 $n$ 次；對每個 $i$，$j$ 共有 $m$ 次。因此核心敘述執行：

$$n \times m=mn$$

次。

解題方法與總步數

以下採常見的基本運算計數方式：初始化、條件判斷、遞增、加法與指定各計 1 步，陣列存取視為常數時間。

for (int i = 0; i < n; i++)
  for (int j = 0; j < m; j++)
    c[i][j] = a[i][j] + b[i][j];

操作	執行次數	說明
i = 0	$1$	外層迴圈初始化
i < n	$n+1$	包含最後一次失敗判斷
i++	$n$	外層迴圈遞增
j = 0	$n$	每次外層迴圈重新初始化
j < m	$n(m+1)$	每列包含最後一次失敗判斷
j++	$mn$	內層迴圈遞增
a[i][j] + b[i][j]	$mn$	每個元素進行一次加法
c[i][j] = \cdots	$mn$	每個元素進行一次指定

所以總步數為：

核心觀念

• Postfix（後序表示法）：運算子寫在兩個運算元之後，例如 ab+ 表示 $a+b$。
• Prefix（前序表示法）：運算子寫在兩個運算元之前，例如 $a+b$ 的 prefix 為 +ab。
• 本題所有運算子皆視為二元運算子。

由 postfix 轉 prefix 時，從左至右掃描：

1. 遇到運算元，推入堆疊。
2. 遇到運算子，先取出堆疊頂端作為右運算元 $R$，再取下一個作為左運算元 $L$。
3. 組合成「運算子＋左運算元＋右運算元」，再推回堆疊：

$$\theta LR$$

其中 $\theta$ 為目前的運算子。

---

（A）ab/c-de*+ac*-

逐步轉換

掃描符號	動作	堆疊內容（由底至頂）
a	推入 a	a
b	推入 b	a, b
/	組合 /ab	/ab
c	推入 c	/ab, c
-	組合 -/abc	-/abc
d	推入 d	-/abc, d
e	推入 e	-/abc, d, e
*	組合 *de	-/abc, *de
+	組合 +-/abc*de	+-/abc*de
a	推入 a	+-/abc*de, a
c	推入 c	+-/abc*de, a, c
*	組合 *ac	+-/abc*de, *ac
-	組合 -+-/abc*de*ac	-+-/abc*de*ac

關鍵組合如下：

$$ab/ \;\longrightarrow\; /ab$$ $$ab/c- \;\longrightarrow\; -(/ab)c$$ $$de* \;\longrightarrow\; *de$$ $$ab/c-de*+ \;\longrightarrow\; +(-(/ab)c)(*de)$$

核心觀念

題目未明示 $m,n$ 的定義及零係數項的處理方式；以下採資料結構教材的標準設定：$m,n$ 分別為兩個稀疏多項式的非零項數，節點依 exponent 排序，結果不儲存係數為 $0$ 的項。

多項式相加本質上是兩條排序串列的合併：

• exponent 相同：進行一次 coefficient addition。
• exponent 不同：直接複製 exponent 較大的項。
• 其中一條串列結束後：直接接上另一條串列剩餘項目，不再比較 exponent。

設共有 $c$ 組 exponent 相同，其中有 $z$ 組相加後係數為 $0$，則

$$0\le c\le \min\{m,n\},\qquad 0\le z\le c$$

coefficient additions 的次數為 $c$；新節點數為

$$N=(m-c)+(n-c)+(c-z)=m+n-c-z.$$

選項分析

• (A) 錯誤。
  兩個多項式可能沒有任何相同的 exponent。例如

  $$P(x)=x^4,\qquad Q(x)=x^2.$$

  此時沒有 coefficient addition，次數為 $0$，並非至少 $1$。

• (B) 錯誤。
  當兩個多項式沒有相同 exponent 時，每一個輸入項都會成為結果中的一個節點，因此最多可建立 $m+n$ 個新節點，而不是 $m+n-1$ 個。

  例如 $m=n=1$：

  $$P(x)=x^4,\qquad Q(x)=x^2.$$

  結果有 $2$ 個節點，但

  $$m+n-1=1.$$

• (C) 錯誤。
  若相同 exponent 的兩個係數相加後為 $0$，該項不建立節點。例如

  $$P(x)=x^2+x,\qquad Q(x)=-x^2.$$

  相加後為

  $$P(x)+Q(x)=x.$$

  結果只有 $1$ 個節點，而

  $$\max\{m,n\}=\max\{2,1\}=2.$$

核心觀念

題目未提供 front、rear 的初始值與佇列表示法；以下採用標準的「保留一格」環狀佇列，並以 front == rear 表示空佇列。

設陣列大小為 $N=MAX\_QUEUE\_SIZE$，索引前進一格必須使用：

$$nextRear=(rear+1)\bmod N$$

此表示法中：

• front 指向隊首元素前一格。
• rear 指向目前隊尾元素。
• front == rear 表示空佇列。
• 當下一個 rear 位置等於 front 時，表示佇列已滿。

保留一格的原因是避免空佇列與滿佇列都呈現 front == rear，使兩種狀態無法區分。

解題方法

加入元素時依序進行：

1. 計算 rear 的下一個環狀位置。
2. 若下一個位置等於 front，呼叫 queueFull()。
3. 佇列未滿時，將 rear 後移並把元素存入該位置。

完整程式碼

核心觀念

本題考查單向鏈結串列的「就地反轉」（in-place reversal）。

原本的鏈結串列如下：

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

反轉後必須變成：

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

每個節點的 data 不需修改，只需逐一改變節點的 link 指標。為避免遺失尚未處理的節點，需要使用三個指標：

• lead：目前尚未反轉部分的第一個節點。
• middle：已完成反轉部分的第一個節點。
• trail：暫存 lead 原本指向的下一個節點。

解題方法

初始時尚未反轉任何節點，因此：

middle = NULL;

每次迴圈處理 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[0].row：矩陣列數
• a[0].col：矩陣欄數
• a[0].value：非零項數
• a[i]（$i\ge 1$）：第 $i$ 個非零項，格式為 (row, col, value)

本題：

$$a[0]=(6,6,8)$$

表示矩陣為 $6\times 6$，共有 $8$ 個非零項。

轉置的規則是：

$$(r,c,v)\longmapsto(c,r,v)$$

也就是交換 row 與 col，value 保持不變。

---

7(A) transpose

關鍵程式判讀

n = a[0].value;

因此 $n=8$，內層迴圈會處理 a[1] 到 a[8]。

if (a[j].col)

在 C 語言中，這等價於：

if (a[j].col != 0)

所以欄索引為 $0$ 的項目會被跳過。

各項判斷如下：

j	a[j] (row,col,value)	條件結果	每輪寫入的項目
1	(0,0,15)	否	跳過
2	(0,3,22)	是	(3,0,22)
3	(0,5,-15)	是	(5,0,-15)
4	(1,1,11)	是	(1,1,11)
5	(1,2,3)	是	(2,1,3)
6	(2,3,-6)	是	(3,2,-6)
7	(4,0,91)	否	跳過
8	(5,2,28)	是	(2,5,28)

外層迴圈：

for (i = 0; i < 4; i++)

會執行 $4$ 次，但變數 i 沒有參與條件判斷或資料寫入。因此上述六個項目會被完整寫入 $4$ 次。

currentb 的變化為：

$$1\rightarrow 7\rightarrow 13\rightarrow 19\rightarrow 25$$

實際寫入結果

以下以 b 至少能容納 b[0] 到 b[24] 為前提：

b 索引	寫入的 (row,col,value)
b[1], b[7], b[13], b[19]	(3,0,22)
b[2], b[8], b[14], b[20]	(5,0,-15)
b[3], b[9], b[15], b[21]	(1,1,11)
b[4], b[10], b[16], b[22]	(2,1,3)
b[5], b[11], b[17], b[23]	(3,2,-6)
b[6], b[12], b[18], b[24]	(2,5,28)

b[0] 在此函式中完全沒有被設定，因此其內容保留為呼叫函式前的值，無法由本題資料決定。

此程式與標準轉置程式不同之處是：

for (i = 0; i < 4; i++)

以及：

if (a[j].col)

標準寫法通常須依欄索引判斷，例如 a[j].col == i，並且先設定 b[0]。依題面程式原樣執行時，會產生重複項目；若 b 只配置一般所需的 $n+1=9$ 個位置，寫入 b[9] 以後會發生陣列越界，C 語言結果屬未定義行為。

複雜度

令非零項數為 $t$：

• 時間複雜度：$4t$，故為 $O(t)$
• 區域變數額外空間：$O(1)$
• 輸出陣列需容納本程式寫出的項目，大小為 $O(t)$

---

7(B) fast_transpose

初始化標頭

int num_cols = a[0].col;
int num_terms = a[0].value;

因此：

$$\text{num\_cols}=6,\qquad \text{num\_terms}=8$$

b[0].row = 6;
b[0].col = 6;
b[0].value = 8;

所以：

$$b[0]=(6,6,8)$$

計算各原始欄的非零項數