108 年國立中山大學電機工程學系碩士班丙組《資料結構》考古題與詳解

Question 1

Suppose we have a byte-addressable machine, i.e., each byte is accessed via an address.
Let the locations for an array be allocated in a row-major manner, and each element of an
array takes 4 bytes. Assume that the address of the first byte of the array is 500 in all the
following cases. Which of the following is true?
(A) The address of the element A[10][30] in an array declared as A[100][200] is 24586
(B) The address of the element A[10][20][30] in an array declared as A[100][200][300] is 177899
(C) The address of the element A[10] in an array declared as A[100] is 536
(D) The address of the element A[10][20][30][40] in an array declared as A[100][200][300][400] is 76457217

Accepted Answer

核心觀念與位址公式

在資料結構中，以列為主（Row-major order）的多維陣列記憶體位址計算，預設索引下界為 $1$ （1-based indexing）。設起始位址為 $\text{Base} = 500$ ，每個元素大小 $S = 4\text{ bytes}$ ：

一維陣列 $A[d_1]$ ：
$\text{Address}(A[i]) = \text{Base} + (i - 1) \times S$
二維陣列 $A[d_1][d_2]$ ：
$\text{Address}(A[i][j]) = \text{Base} + [(i - 1) \times d_2 + (j - 1)] \times S$
三維陣列 $A[d_1][d_2][d_3]$ ：
$\text{Address}(A[i][j][k]) = \text{Base} + [(i - 1) \times d_2 \times d_3 + (j - 1) \times d_3 + (k - 1)] \times S$
四維陣列 $A[d_1][d_2][d_3][d_4]$ ：
$\text{Address}(A[i][j][k][l]) = \text{Base} + [(i - 1) \times d_2 \times d_3 \times d_4 + (j - 1) \times d_3 \times d_4 + (k - 1) \times d_4 + (l - 1)] \times S$

選項推導與驗證

Question 2

Let a, b and c are variables. Which of the following is a postfix expression? (A) $a/(b + c)$ (B) $xabc/+$ (C) $abc + /$ (D) $/a + bc$

Accepted Answer

核心觀念 本題考查算術運算式（Arithmetic Expression）的表示法及其轉換規則： 1. 中序運算式（Infix Expression）：運算子置於兩運算元中間，例如 $a + b$。運算時需依賴「運算子優先權（Precedence）」與「括號（Parentheses）」來決定計算順序。 2. 前序運算式（Prefix Expression / Polish Notation）：運算子置於運算元之前，例如 $+ a b$。不需括號即可唯一決定計算順序。 3. 後序運算式（Postfix Expression / Reverse Polish Notation, RPN）：運算子置於運算元之後，例如 $a b +$。不需括號即可由左至右利用堆疊（Stack）進行線性時間的求值，是編譯器與虛擬機中最廣泛使用的表示法。 合法後序運算式的充要條件（針對二元運算子） 若運算式中皆為二元運算子（Binary Operators）： - 設運算元個數為 $N$、運算子個數為 $M$，則必須滿足： $$N = M + 1$$ - 前綴累積條件：由左至右掃描時，任何時刻已讀取的運算元個數，必須隨時大於已讀取的運算子個數。 --- 解題方法 將中序運算式轉換為後序運算式的標準括號法（Parenthesizing Method）如下： 1. 依優先順序完全加上括號： 以中序式 $a / (b + c)$ 為例，加法在括號內先做，除法後做： $$(a / (b + c))$$ 2. 將各運算子移至其對應括號的右外側： - 先處理內層括號：$(b + c) 	o (b c +)$ - 再處理外層括號：$(a / (b c +)) 	o (a (b c +) /)$ 3. 去除所有括號： 得到後序運算式為： $$a b c + /$$ 堆疊求值驗證流程 - 讀入 $a, b, c$ $	o$ 依序推入堆疊，堆疊內容為 $[a, b, c]$（頂端為 $c$）。

Question 3

Let $a = 3, b = 8, c = 6$ and $d = 5$. What is the value of the prefix expression $	imes ba + dc$? (A) 13 (B) 14 (C) 15 (D) 16

Accepted Answer

觀念說明 前綴運算式（Prefix Expression）求值演算法採用堆疊（Stack）處理，由右至左掃描運算式： 1. 遇到運算元（Operand）時，直接壓入堆疊。 2. 遇到二元運算子（Operator）時，從堆疊頂端依序彈出前兩個運算元 $op1$ 與 $op2$，進行 $op1 	ext{ [operator]} op2$ 運算，並將結果壓回堆疊。 本題前綴運算式為 $- 	imes b a + d c$（對應中綴式 $(b 	imes a) - (d + c)$）。 ---

Question 4

The ADT stack can be defined by the following axioms:
$(aStack.createStack()).isEmpty() = \text{true}$
$(aStack.push(item)).isEmpty() = \text{false}$
$(aStack.createStack()).pop() = \text{error}$
$(aStack.createStack()).getTop() = \text{error}$
$(aStack.push(item)).pop() = aStack$
$(aStack.push(item)).getTop() = item$

For the following expression:
$(((((((aStack.createStack()).push(1)).push(2)).pop()).push(3)).pop()).pop()).isEmpty()$
what is the value returned?
(A) an item
(B) a stack
(C) true
(D) false

Accepted Answer

核心觀念 本題考查堆疊（stack）的兩項核心特性： - 後進先出（LIFO, Last In First Out）：最後放入的元素會最先被取出。 - push(item)：將元素放入堆疊頂端。 - pop()：移除並回傳堆疊頂端元素；依題目公理，運算結果表達為移除頂端元素後的堆疊。 - isEmpty()：判斷堆疊是否為空，回傳 true 或 false。 題目中的每個運算都會接在前一個運算結果後面，因此必須由內而外逐步追蹤堆疊內容。 解題方法 以堆疊底部到頂部表示目前內容： 1. 建立空堆疊： $$aStack.createStack() = [\ ]$$ 2. 執行 push(1)： $$[\ ] \xrightarrow{push(1)} [1]$$ 3. 執行 push(2)： $$[1] \xrightarrow{push(2)} [1,2]$$ 此時 $2$ 位於堆疊頂端。 4. 執行 pop()： 依後進先出原則移除頂端元素 $2$： $$[1,2] \xrightarrow{pop()} [1]$$ 5. 執行 push(3)： $$[1] \xrightarrow{push(3)} [1,3]$$ 6. 執行 pop()： 移除頂端元素 $3$： $$[1,3] \xrightarrow{pop()} [1]$$ 7. 再執行一次 pop()： 移除頂端元素 $1$：

Question 5

Suppose a stack is implemented by a variable top and an array B[4]. Note that top denotes the index of the last element pushed. Initially, the stack is empty. Then the following operations are performed in order:
push(1), push(2), pop(), push(3), push(4), pop(), getTop(), push(5), pop(), push(6).
Which of the following is true in the end?
(A) $B[0] = 3$
(B) $B$ contains 4 integers available
(C) An overflow occurred, so the operations could not be completely done
(D) top is 2

Accepted Answer

觀念說明 本題考察以 0-indexed 陣列 B[4] 實作堆疊（Stack）的動態操作。依題意，top 表示最後壓入（push）元素的索引位置，且初始時堆疊為空，故初始設定 $top = -1$。 - push(x)：$top$ 增加 1，並寫入 $B[top] = x$。 - pop()：取出頂端元素，$top$ 減少 1。 - getTop()：僅讀取 $B[top]$，$top$ 與陣列內容保持不變。 --- 操作追蹤 初始狀態：$top = -1$，堆疊為空。 1. push(1)：$top = 0$，$B[0] = 1$ 2. push(2)：$top = 1$，$B[1] = 2$ 3. pop()：$top = 0$ 4. push(3)：$top = 1$，$B[1] = 3$

Question 6

Let the height of a tree be the number of nodes along the longest path from the root node to the leaf nodes. Consider the integers 30, 41, 25, 29, 94, 37, 70, 23, 65, 75, 68, 67 in order to create a binary search tree. Which of the following is true?
(A) The node for 37 is a leaf node
(B) The root node is 41
(C) The node for 70 has only one child
(D) The height of the tree is 5

Accepted Answer

觀念說明

二元搜尋樹（Binary Search Tree, BST）插入新節點時，自根節點開始比對：小於當前節點走左子樹，大於當前節點走右子樹，直到找到空位置插入。題目定義樹高（Height）為根節點至葉節點最長路徑上的節點總數。

二元搜尋樹建構過程

依序插入數字：30, 41, 25, 29, 94, 37, 70, 23, 65, 75, 68, 67

插入 30：根節點 $30$ 。
插入 41： $41 > 30 \implies 30$ 的右子節點。
插入 25： $25 < 30 \implies 30$ 的左子節點。
插入 29： $29 < 30 \implies 29 > 25 \implies 25$ 的右子節點。
插入 94： $94 > 30 \implies 94 > 41 \implies 41$ 的右子節點。
插入 37： $37 > 30 \implies 37 < 41 \implies 41$ 的左子節點。
插入 70： $70 > 30 \implies 70 > 41 \implies 70 < 94 \implies 94$ 的左子節點。
插入 23： $23 < 30 \implies 23 < 25 \implies 25$ 的左子節點。
插入 65： $65 > 30 \implies 65 > 41 \implies 65 < 94 \implies 65 < 70 \implies 70$ 的左子節點。

Question 7

Consider a complete binary tree with exactly 5000 nodes, implemented with an array starting from index 0. Suppose that a node has its value stored at index 999 in the array. What index is the value stored at for this node's left child?
(A) 999
(B) 1999
(C) 998
(D) 2998

Accepted Answer

核心觀念

以陣列從索引 $0$ 開始儲存 complete binary tree 時，若某節點位於索引 $i$ ：

左子節點索引： $2i+1$
右子節點索引： $2i+2$
父節點索引： $\left\lfloor \dfrac{i-1}{2} \right\rfloor$

題目給定節點位於索引 $999$ ，因此直接套用左子節點公式。

解題方法

令目前節點索引為 $i=999$ ，其左子節點索引為：

2i+1=2(999)+1=1998+1=1999

因此，左子節點的值儲存在索引 $1999$ 。

題目雖然補充樹中共有 $5000$ 個節點，但此節點的左子節點索引為 $1999$ ，小於最大有效索引 $4999$ ，所以該左子節點確實存在。

選項分析

Question 8

Consider a tree with A as the root node. The left and right child of A are B and C, respectively. The left and right child of B are D and E, respectively. The left and right child of E are F and G, respectively. What is the order of the nodes processed in the pre-order traversal?
(A) A-B-E-D-F-G-C
(B) D-B-F-E-A-G-C
(C) A-B-D-G-F-E-C
(D) A-B-D-E-F-G-C

Accepted Answer

核心觀念

本題考查樹的「前序走訪」（pre-order traversal）。

前序走訪的處理順序為：

\text{根節點} \rightarrow \text{左子樹} \rightarrow \text{右子樹}

對二元樹而言，每個節點都遵循：

先處理目前節點。
再走訪左子樹。
最後走訪右子樹。

題目中的樹結構如下：

解題方法

依照「根、左、右」的順序走訪：

根節點為 $A$ ，先處理 $A$ 。
進入 $A$ 的左子樹，根節點為 $B$ ，處理 $B$ 。
進入 $B$ 的左子樹，處理 $D$ 。
$D$ 沒有子節點，回到 $B$ ，走訪 $B$ 的右子樹 $E$ 。
進入 $E$ 的左子樹，處理 $F$ 。
再走訪 $E$ 的右子樹，處理 $G$ 。
$B$ 的整個子樹完成後，回到 $A$ ，走訪 $A$ 的右子樹 $C$ 。

因此處理順序為：

A \rightarrow B \rightarrow D \rightarrow E \rightarrow F \rightarrow G \rightarrow C

選項分析

Question 9

Suppose we start with an empty max-heap of integers, and enter the numbers 20 through 30 into this heap in order. Let the resulting max-heap be stored in an array. What index is 28 stored at in the array?
(A) 2
(B) 3
(C) 4
(D) 5

Accepted Answer

核心觀念

本題考查「最大堆積（max-heap）」的插入與上浮（heapify-up）。

最大堆積必須同時滿足：

完全二元樹結構：新元素一律插入目前最底層最左邊的空位。
堆積順序性質：每個父節點的值都大於或等於其子節點。

若採用常見的 1-based 陣列索引，則：

父節點索引： $\left\lfloor i/2 \right\rfloor$
左子節點索引： $2i$
右子節點索引： $2i+1$

插入新元素後，若它大於父節點，就必須持續與父節點交換，直到恢復最大堆積性質。

解題方法

依序插入 $20$ 至 $30$ ，只列出與本題相關的最後幾步。

插入 $27$ 後，堆積陣列為：

[27,26,25,23,22,21,24,20]

插入 $28$

先放入下一個完全二元樹位置，即索引 $9$ ：

[27,26,25,23,22,21,24,20,28]

索引 $9$ 的父節點為：

\left\lfloor \frac{9}{2} \right\rfloor=4

由於 $28>23$ ，兩者交換：

[27,26,25,28,22,21,24,20,23]

此時 $28$ 位於索引 $4$ ，其父節點索引為：

\left\lfloor \frac{4}{2} \right\rfloor=2

因為 $28>26$ ，再次交換：

[27,28,25,26,22,21,24,20,23]

接著 $28$ 位於索引 $2$ ，其父節點是索引 $1$ 。因為 $28>27$ ，繼續交換：

Question 10

Suppose we start with an empty max-heap of integers, and enter the numbers 20 through 30 into this heap in order. Let the resulting max-heap be stored in an array. Then remove the root node from the heap. What index is 28 stored at in the array?
(A) 4
(B) 3
(C) 2
(D) 1

Accepted Answer

核心觀念 本題考查最大堆積（max-heap）的兩個操作： 1. 插入元素：新元素先放在陣列末端，再向上調整（sift-up），直到符合父節點值大於等於子節點值。 2. 刪除根節點：移除最大值後，將最後一個元素移到根節點，再向下調整（sift-down）。 採用常見的 $1$-based heap 陣列表示法： - 父節點索引：$\left\lfloor i/2ightfloor$ - 左子節點索引：$2i$ - 右子節點索引：$2i+1$ --- 解題方法 依序插入 $20$ 至 $30$，每次插入後向上調整，得到： $$ \begin{array}{c|ccccccccccc} 	ext{索引} & 1&2&3&4&5&6&7&8&9&10&11\ \hline 	ext{值} &30&29&25&23&28&21&24&20&22&26&27 \end{array} $$ 因此，刪除根節點 $30$ 時： 1. 將最後一個元素 $27$ 移到根節點： $$ [27,29,25,23,28,21,24,20,22,26] $$

Question 11

An empty hash table has a capacity of 13, and you insert six entries with keys 21, 16, 8, 10, 22, 34, and 49. Using linear probing and the hash function $h(key) = key \pmod{13}$ , what index 49 is stored at in the table? Note that % is the remainder operator, e.g., $(100)\%(13)=9$ .
(A) 0
(B) 5
(C) 11
(D) 8

Accepted Answer

核心觀念

本題考查雜湊表的「線性探測法（linear probing）」。

雜湊函數為：

h(key)=key\bmod 13

若計算出的索引已被占用，就依序往下一格尋找；到索引 $12$ 後，下一格回到索引 $0$ ，形成循環探測。

題目文字寫「六筆資料」，但實際列出 $21,16,8,10,22,34,49$ 共七個鍵值。因為題目要求查詢 $49$ 的位置，以下依照列出的七個鍵值，按照題目順序插入。

解題方法

依序計算雜湊位置，發生碰撞時採用線性探測。

插入鍵值	原始雜湊位置	線性探測結果	最終索引
$21$	$21\bmod13=8$	索引 $8$ 空	$8$
$16$	$16\bmod13=3$	索引 $3$ 空	$3$
$8$	$8\bmod13=8$	$8$ 已占用，探測 $9$	$9$
$10$	$10\bmod13=10$	索引 $10$ 空	$10$
$22$	$22\bmod13=9$	$9$ 、 $10$ 已占用，探測 $11$	$11$
$34$	$34\bmod13=8$	$8$ 、 $9$ 、 $10$ 、 $11$ 已占用，探測 $12$	$12$

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

Question 12

Consider the integers 30, 41, 25, 29, 94, 37, 70, 23, 65, 75, 68, 67 in order to create an AVL tree. Which of the following about the tree is false?
(A) The node for 37 is a leaf node
(B) The root node is 41
(C) The node for 70 has only one child
(D) The height of the tree is 4

Accepted Answer

依次插入數值建構 AVL 樹，各階段關鍵旋轉與平衡調整如下： 1. 插入 30、41、25、29、94、37 均保持平衡。 2. 插入 70、23 後，插入 65：節點 $94$ 失去平衡（LL 型），對 $94$ 做右旋轉，由 $70$ 替代其位置。 3. 插入 75：節點 $41$ 失去平衡（RR 型），對 $41$ 做左旋轉，由 $70$ 提升為該子樹根節點。 4. 插入 68：根節點 $30$ 失去平衡（RL 型），對 $30$ 做雙重旋轉（RL Rotation），最終由 $41$ 成為全樹根節點。 5. 插入 67：節點 $65$ 失去平衡（RL 型），對 $65$ 做雙重旋轉，由 $67$ 提升為該子樹根節點。 --- 最終 AVL 樹結構

108 年 國立中山大學電機工程學系碩士班丙組《資料結構》

第 1 題

核心觀念與位址公式

選項推導與驗證

第 2 題

核心觀念

合法後序運算式的充要條件（針對二元運算子）

解題方法

堆疊求值驗證流程

第 3 題

第 4 題

核心觀念

解題方法

第 5 題

觀念說明

操作追蹤

第 6 題

觀念說明

二元搜尋樹建構過程

第 7 題

核心觀念

解題方法

選項分析

第 8 題

核心觀念

解題方法

選項分析

第 9 題

核心觀念

解題方法

插入 282828

第 10 題

第 11 題

核心觀念

解題方法

第 12 題

最終 AVL 樹結構

第 13 題

第 14 題

第 15 題

第 16 題

第 17 題

第 18 題

第 19 題

其他考古題

108 年中山大學的其他科目

中山大學《資料結構》其他年度

其他學校的電機系考古題

108 年國立中山大學電機工程學系碩士班丙組《資料結構》

插入 $28$