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

核心觀念

本題考查位元運算中的 AND（位元且） 與遮罩（mask）。

AND 的規則為：

$$0\mathbin{\&}0=0,\quad 0\mathbin{\&}1=0,\quad 1\mathbin{\&}0=0,\quad 1\mathbin{\&}1=1$$

因此：

• 與 $1$ 做 AND：保留原位元。
• 與 $0$ 做 AND：將該位元清除為 $0$。

本題要將原數的第二個位元由 $1$ 清除為 $0，其餘位元保持不變，因此使用 AND，並在該位置放$0$，其他位置放$1$。

解題方法

原位元組為：

$$11101010_2$$

目標位元組為：

$$10101010_2$$

逐位比較可知，只有由左至右第二個位元需要由 $1$ 變成 $0$。因此遮罩為：

$$10111111_2$$

進行 AND 運算：

$$\begin{array}{c} 11101010\\ \mathbin{\&}\ 10111111\\ \hline 10101010 \end{array}$$

其中：

• 第一個位元：$1\mathbin{\&}1=1$
• 第二個位元：$1\mathbin{\&}0=0$
• 其餘位元皆與 $1

核心觀念

本題考查位元運算中的「位元 OR（或運算）」與遮罩（mask）。

OR 運算規則如下：

原位元	遮罩位元	OR 結果
0	0	0
0	1	1
1	0	1
1	1	1

若要將某一位由 $0$ 設為 $1$，同時保持其他位元不變，可在該位置使用 $1$ 作為 OR 遮罩，其餘位置使用 $0$。

---

解題方法

原位元組為：

$$01000101_2$$

目標位元組為：

$$01010101_2$$

逐位比較可知，只有由左至右第 4 個位元需要由 $0$ 改為 $1$：

$$\begin{array}{cccccccc} 0&1&0&0&0&1&0&1\\ 0&1&0&1&0&1&0&1 \end{array}$$

因此在該位置放入 $1$，其他位置放入 $0$，得到遮罩：

$$00010000_2$$

使用 OR 運算：

$$\begin{array}{cccccccc} 0&1&0&0&0&1&0&1\\ \lor\;&0&0&0&1&0&0&0&0\\ \hline 0&1&0&1&0&1&0&1 \end{array}$$

所以：

$$01000101_2 \;|\; 00010000_2 = 01010101_2$$

---

(A) 位元運算

應使用位元 OR 運算，以符號表示為：

核心觀念

稀疏矩陣以三元組表示：第 0 列記錄矩陣的列數、行數與非零項數，其餘每列記錄一個非零項的「列、行、值」。矩陣轉置時，每個非零項依下式轉換：

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

轉置後的三元組通常依新矩陣的列排序。

解題方法

題目程式有幾處語法或名稱錯誤，照原文無法編譯：currentb++ 後缺少分號；(B) 使用未宣告的 row_term，且 for 迴圈的分號位置錯誤。

以下依最小修正解讀：修正這些語法與名稱錯誤，保留 (A) 的 i < 4，以及 (B) 的 i <= 5。因此，(B) 的轉置迴圈只處理前 5 個非零項。若題目原意是處理全部非零項，(B) 的迴圈上限應為 num_terms。

原矩陣有 6 列、6 行、8 個非零項：

項目	原三元組
a[1]	(0,0,15)
a[2]	(0,3,22)
a[3]	(0,5,-15)
a[4]	(1,1,11)
a[5]	(1,2,3)
a[6]	(2,3,-6)
a[7]	(4,0,91)
a[8]	(5,2,28)

(A) 一般轉置

程式依序檢查原矩陣的第 0 至第 3 行，並掃描全部 8 個非零項，只輸出行索引 i 相符的項目。

• i = 0：(0,0,15)、(0,4,91) 轉為 (0,0,15)、(0,4,91)
• i = 1：(1,1,11) 轉為 (1,1,11)
• i = 2：(1,2,3)、(5,2,28) 轉為 (2,1,3)、(2,5,28)
• i = 3：(0,3,22)、(2,3,-6) 轉為 (3,0,22)、(3,2,-6)

由於迴圈只到 i = 3，原矩陣第 4、5 行的非零項不會被輸出。

(A) 寫入的結果：

b[0] 6 6 8
b[1] 0 0 15
b[2] 0 4 91
b[3] 1 1 11
b[4] 2 1 3
b[5] 2 5 28
b[6] 3 0 22
b[7] 3 2 -6

標頭仍記錄 8 個非零項，但程式只寫入 7 個；b[8] 未被設定。

(B) 快速轉置

核心觀念

後置表示式（postfix）中，運算子放在兩個運算元之後，例如：

$$ab+ \Rightarrow (a+b)$$

轉換為前置表示式（prefix）時，運算子放在運算元之前：

$$(a+b) \Rightarrow +ab$$

本題可使用堆疊（stack）由左至右掃描：

1. 讀到運算元：直接推入堆疊。
2. 讀到二元運算子：先取出右運算元，再取出左運算元。
3. 組合成「運算子＋左運算元＋右運算元」的前置表示式，再推回堆疊。
4. 掃描完畢後，堆疊中唯一的表示式即為答案。

取出順序必須是右、左，但組合順序必須是左、右。

---

解題方法與逐項解析

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

依序掃描各符號：

掃描符號	堆疊內容	說明
a	a	推入運算元
b	a, b	推入運算元
/	/ab	組合為 $\dfrac{a}{b}$
c	/ab, c	推入運算元
-	-/abc	組合為 $\left(\dfrac{a}{b}-c\right)$
d	-/abc, d	推入運算元
e	-/abc, d, e	推入運算元
*	-/abc, *de	組合為 $d \times e$
+	+-/abc*de	組合為 $\left(\dfrac{a}{b}-c\right)+de$
a	+-/abc*de, a	推入運算元
c	+-/abc*de, a, c	推入運算元
*	+-/abc*de, *ac	組合為 $a \times c$
-	-+-/abc*de*ac	完成最後的減法

其階層結構為：

關鍵概念

• 循環鏈結串列的唯一節點其 next 指向自身。
• 刪除節點後須把指標 *ptr 重新指向剩餘串列的下一個節點；若刪除後串列空了，則設為 NULL。
• 依題目暗示，使用全域的自由節點池 avail 回收被刪除的節點。

程式碼（時間複雜度 $O(n)$，空間 $O(1)$）

核心觀念

本題考查兩類觀念：

1. 算術運算式的三種表示法：infix、prefix、postfix。
2. 以 stack 進行迷宮的深度優先搜尋與回溯。

其中：

• infix：運算子位於兩個運算元之間，例如 $A+B$。
• prefix：運算子位於運算元之前，例如 $+AB$。
• postfix：運算子位於運算元之後，例如 $AB+$。

Prefix 與 postfix 的運算順序已由運算子位置決定，因此不需要依賴括號表示優先順序。

解題方法

逐一判斷各敘述是否符合上述定義。對迷宮部分，使用 stack 儲存目前尚未完成回溯的路徑位置；若目前路徑包含 $k$ 個格子，stack 深度就可能達到 $k$。

$7\times 5$ 的迷宮共有

$$7\times 5=35$$

個格子。最壞情況下，迷宮可設計成蛇形單一路徑，使搜尋過程必須同時保留至少 $21$ 個路徑位置，甚至可能接近 $35$ 個位置。因此容量至少為 $21$ 是合理的下界。

題目未提供特定迷宮的牆面、入口與出口配置，所以無法計算某一張迷宮的精確最大 stack 深度；以下依標準迷宮回溯題意，以最壞情況判斷。

選項分析

(A) 錯誤

Prefix 將運算子放在運算元之前，運算樹的結構已能決定運算順序。例如：

$$A+B\times C$$

其 prefix 表示為

$$+\,A\,\times\,B\,C$$

先計算乘法，再計算加法，不需要括號。

括號是 infix 表示法常用來處理優先順序與結合方向；prefix 本身不需要括號。因此 (A) 錯誤。

(B) 錯誤

一般電腦的處理器直接執行的是機器指令，不是人類書寫的 infix expression。編譯器或直譯器通常會先進行語法分析，再建立運算樹、轉換成 postfix 或產生相應的機器指令，最後才執行計算。