108 年 國立中正大學資訊管理學系碩士班乙組《資料結構》
第 1 題6 分
For array "int list[100]", list[i]=i-1, for i=0...99. And &(list[99]) is 0x123456.
What is (list+1)?
登入後即可作答並保存紀錄。
核心觀念
本題考查 C 語言的陣列與指標運算：
- 在一般運算式中，陣列名稱
list會轉換成指向第一個元素的指標，即&list[0]。 - 指標加法以「元素」為單位，不是以位元組為單位。
- 因此：
注意，list+1 是位址；若寫成 *(list+1)，才是取出 list[1] 的內容。
解題方法
已知：
list+1 指向 list[1]。從第 99 個元素往前到第 1 個元素，相差：
因此，若每個 int 占用 個位元組：
題目未明確指定 int 的大小，因此嚴格而言，數值位址無法唯一決定。若依一般考題慣例假設：
則：
第 2 題12 分
Please transform the expressions from prefix to postfix. (12 pt)
(A) -+-/abcdeac (6 pt)
(B) -/*a+bcdg (6 pt)
登入後即可作答並保存紀錄。
轉換方法：自右至左掃描前綴式，遇 operand 推入堆疊；遇 operator 取出兩個堆疊頂端，組成 左 operand + 右 operand + operator 的後綴子式，重新推入堆疊。最後堆疊唯一元素即為整式的後綴式。
(A) -+-/abcdeac
右至左掃描過程
| 讀取 | 堆疊內容 (自左至右) |
|---|---|
| c | c |
| a | c , a |
| * | ac* |
| e | ac* , e |
| d | ac* , e , d |
| * | ac* , de* |
| b | ac* , de* , b |
| c | ac* , de* , b , c |
| a | ac* , de* , b , c , a |
| / | ac* , de* , ac/ |
| - | ac* , de* , b ac/- |
第 3 題12 分
If moves are defined as: E be 0, SE be 1, S be 2, and NE be 7 in clockwise direction. Please draw out the path that the maze algorithm works. (12 pt)
🖼️【此處有附圖，請對照原卷】
登入後即可作答並保存紀錄。
核心觀念
本題考八方向迷宮的深度優先搜尋（DFS）與回溯。把每個可通行格視為節點，搜尋時依方向編號逐一檢查相鄰格；走進死路便退回上一格，直到抵達出口。
若搜尋時記錄已走過的格子，避免重複繞行，最多檢查 個格子，每格至多查看 8 個方向，時間複雜度為 ；搜尋路徑與標記所需空間為 。
解題方法
圖中迷宮有 11 列、15 欄，入口在左上角 ，出口在右下角 ；將值為 0 的格視為可通行、值為 1 的格視為障礙。座標以列、欄表示，列往下增加、欄往右增加，並可沿八個方向移動。
| 方向編號 | 方向 | 座標變化 |
|---|---|---|
| 0 | 東 | |
| 1 | 東南 | |
| 2 | 南 | |
| 3 | 西南 | |
| 4 | 西 | |
| 5 | 西北 | |
| 6 | 北 | |
| 7 | 東北 |
第 4 題6 分
How much is the maximum path length for a maze if the maze size is m by n, where m>n? (6 pt)
登入後即可作答並保存紀錄。
核心觀念
將迷宮視為 的格狀圖，每個格子是一個頂點，相鄰且可通行的格子之間有一條邊。
迷宮路徑通常不重複走訪同一格子，因此它是簡單路徑。迷宮共有
個格子，所以路徑最多只能經過 個格子。
題目未明示「路徑長度」是以經過格子數或移動步數計算；本題依資料結構迷宮題的常見約定，以經過的格子數計算。
解題方法
路徑中每個格子最多使用一次，因此：
此上限可以達到。例如採蛇行方式行走：
- 第 1 列由左至右；
- 第 2 列由右至左；
- 第 3 列再由左至右；
- 依此交替進行。
第 5 題20 分
Write out binary tree's (20 pt)
(A) Preorder traversal (5 pt)
(B) Inorder traversal (5 pt)
(C) Postorder traversal (5 pt)
(D) Level order traversal (5 pt)
🖼️【此處有附圖，請對照原卷】
登入後即可作答並保存紀錄。
核心觀念
二元樹走訪是依照指定次序，將每個節點恰好拜訪一次：
- 前序走訪：根節點 → 左子樹 → 右子樹。
- 中序走訪：左子樹 → 根節點 → 右子樹。
- 後序走訪：左子樹 → 右子樹 → 根節點。
- 層序走訪：由上而下、同一層由左而右；通常用佇列實作。
依圖，樹的結構為：根節點 +；左子節點 *、右子節點 E。左側的 * 有左子節點 * 和右子節點 D；下一個 * 有左子節點 / 和右子節點 C；/ 的左右子節點分別是 A、B。
解題方法
由根節點開始，按各走訪規則逐層展開子樹：
- 前序：先列
+，再走左子樹*，最後走右子樹E。左子樹內同樣先根、再左、再右，得到*、*、/、A、B、C、D。 - 中序：先走根的左子樹，再列根
+，最後列右子樹E。左子樹依「左、根、右」排列，得到A、/、B、*、C、*、D。 - 後序：先完成左右子樹，最後才列根。左子樹得到
A、B、/、C、*、D、*，再接上E、+。
第 6 題12 分
Write out the results of the following two sparse matrix multiplication in the sparse-matrix form. (12 pt)
左表：
| 2 | 3 | 5 |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 2 | 2 |
| 1 | 0 | -1 |
| 1 | 1 | 4 |
| 1 | 2 | 6 |
右表：
| 3 | 3 | 4 |
|---|---|---|
| 0 | 0 | 3 |
| 0 | 2 | 2 |
| 1 | 0 | -1 |
| 2 | 2 | 5 |
登入後即可作答並保存紀錄。
核心觀念
稀疏矩陣的三元組表示法，第一列記錄「列數、行數、非零元素個數」，後續每列記錄「列索引、行索引、元素值」。本題的左矩陣 為 ，右矩陣 為 ，因此乘積 為 。
矩陣乘法的元素公式為：
也就是 第 列與 第 行對應元素相乘後加總。題目索引從 開始。
解題方法
依三元組資料還原矩陣：
逐列與逐行計算乘積：
第 7 題20 分
Which(s) is/are true in the following descriptions? (20 pt)
(A) The complexity of the maze in the worst case is O(mp), where m and p are the row and column in the maze, respectively.
(B) In postfix, it needs to use parentheses to indicate the order of priority for operands.
(C) &a->val means (&a)->val
(D) a%bc == 3 means (a%(bc)) == 3
(E) a==3 || b==4 && c==5 means ((a == 3) || (b == 4)) && (c == 5)
登入後即可作答並保存紀錄。
解析
- (A) 迷宮最壞情況需遍歷全部格子，格子總數為 ，故時間複雜度 。 正確。
- (B) 後序表示法 (postfix) 以運算子順序自然決定計算次序，不使用括號。 錯誤。
- (C) 程式語言 C 中運算子優先順序使
&a->val等價於&(a->val)，而非(&a)->val。 錯誤。
第 8 題12 分
Please complete the code of "Erase a circular list". (12 pt)
void cerase(poly_pointer *ptr)
{
poly_pointer temp; /* hint: avail */
if (*ptr) {
……
……
……
*ptr = NULL;
}
}
登入後即可作答並保存紀錄。
核心觀念
循環鏈結串列的最後一個節點會指回第一個節點。本題的 *ptr 指向最後一個節點，因此 (*ptr)->link 是第一個節點。
avail 是可重複利用節點的空閒串列。刪除整個循環串列時，不必逐節點釋放記憶體；只要把串列接到 avail 前端，再將 *ptr 設為 NULL。
解題方法
先保存第一個節點，避免改寫最後節點的 link 後失去串列入口。接著將最後節點接到原本的 avail，再讓 avail 指向原串列的第一個節點。原串列因而成為空閒串列的前段。