111 年國立中央大學資訊管理學系碩士班甲組《資料結構》考古題與詳解

Question 1

Please describe the operations of "single linked list" and "doubly linked list." (4%) Please explain the pros and cons of the two data structures. (4%)

Accepted Answer

核心觀念 - 鏈結串列 (Linked List)：由一系列節點（Node）組成，每個節點保存資料欄位與指向下一個（或前後）節點的指標。 - 單向鏈結串列 (Singly Linked List, SLL)：每個節點僅有一個指向「下一個」節點的指標 next。 - 雙向鏈結串列 (Doubly Linked List, DLL)：每個節點同時保存指向「下一個」節點的指標 next 與指向「前一個」節點的指標 prev。 - 時間複雜度：插入、刪除、搜尋、遍歷等操作的漸進表示法。 - 空間複雜度：節點額外儲存指標的成本。 --- 單向鏈結串列（Singly Linked List）之操作 | 操作 | 目的 | 常用演算法步驟 | 時間複雜度 | 空間額外成本 | |------|------|----------------|------------|--------------| | 建立 | 初始化空鏈結串列 | head ← NULL | $O(1)$ | $O(1)$ | | 遍歷 (Traversal) | 從頭到尾依序訪問每個節點 | ptr ← head; while(ptr ≠ NULL){ visit(ptr-data); ptr ← ptr-next; } | $O(n)$ | $O(1)$ | | 搜尋 (Search) | 找出第一個值等於 key 的節點 | 同遍歷，途中檢查 ptr-data == key | $O(n)$ | $O(1)$ | | 插入於頭部 (Insert‑Head) | 在 head 前加入新節點 | new-next ← head; head ← new; | $O(1)$ | $O(1)$ | | 插入於尾部 (Insert‑Tail) | 在最後一個節點後加入新節點 | 若保有 tail 指標：tail-next ← new; tail ← new;

Question 2

Assume that the root of a tree structure is in Level 1. The level of a binary tree is 11.
a) How many nodes in total can be stored in the binary tree? (3%)
b) How many nodes can be stored in level 8? (3%)

Accepted Answer

核心觀念 - 二元樹（Binary Tree）：每個節點最多有兩個子節點（左、右）。 - 層（Level）：根節點所在層為第 1 層，子層遞增。第 k 層最多可容納 $2^{k-1}$ 個節點。 - 滿二元樹（Full / Complete Binary Tree）：若樹的高度為 h，且所有層均已填滿，則整棵樹的節點總數為 $$\sum{i=1}^{h} 2^{i-1}=2^{h}-1.$$ 本題假設「二元樹」為滿二元樹（即每層皆能存滿節點），因此可直接套用上述公式。 --- 解題方法 a) 計算第 11 層的二元樹可容納的總節點數 - 樹的高度（層數）$h = 11$。 - 依公式，總節點數 $$N{	ext{total}} = 2^{h} - 1 = 2^{11} - 1 = 2048 - 1 = 2047.$$ b) 計算第 8 層可容納的節點數 - 第 $k$ 層的節點上限為 $2^{k-1}$，此處 $k = 8$。 - 因此第 8 層的節點數 $$N{8}=2^{8-1}=2^{7}=128.$$ --- 選項分析（此題為填答題，分別對 a、b 兩小題說明）

Question 3

Given the following traversal of a binary search tree:
Preorder: 15, 7, 2, 4, 9, 8, 30, 22, 17, 28, 45, 40, 37, 44
Inorder: 2, 4, 7, 8, 9, 15, 17, 22, 28, 30, 37, 40, 44, 45
a) Please give the results of postorder traversal. (8%)
b) Please illustrate the corresponding binary tree. (5%)

Accepted Answer

核心觀念

前序走訪的順序是「根、左子樹、右子樹」，因此每個子樹的前序序列第一個節點就是該子樹的根。中序走訪的順序是「左子樹、根、右子樹」；找到根在中序序列中的位置後，即可將其餘節點分成左、右子樹。

本題節點值皆相異，前序與中序序列足以唯一重建二元樹。由於這是一棵二元搜尋樹，其中序序列也必須由小到大排列；題目所給序列符合此性質。

解題方法

前序序列第一個值為根，因此整棵樹的根是 $15$ 。在中序序列中， $15$ 左側的值屬於左子樹，右側的值屬於右子樹：

左子樹的中序序列： $2,4,7,8,9$
右子樹的中序序列： $17,22,28,30,37,40,44,45$

依照兩邊節點數量，將前序序列切分：

左子樹的前序序列： $7,2,4,9,8$
右子樹的前序序列： $30,22,17,28,45,40,37,44$

對左子樹，前序第一個值 $7$ 是根。中序中 $7$ 左側為 $2,4$ ，右側為 $8,9$ ：

$7$ 的左子樹前序為 $2,4$ ，中序為 $2,4$ ，所以根為 $2$ ，其右子節點為 $4$ 。
$7$ 的右子樹前序為 $9,8$ ，中序為 $8,9$ ，所以根為 $9$ ，其左子節點為 $8$ 。

對右子樹，前序第一個值 $30$ 是根。中序中 $30$ 左側為 $17,22,28$ ，右側為 $37,40,44,45$ ：

$30$ 的左子樹前序為 $22,17,28$ ，中序為 $17,22,28$ ，所以根為 $22$ ，左子節點為 $17$ ，右子節點為 $28$ 。

Question 4

Give the data as: 15, 7, 22, 9, 63, 45, 17, 12 After the first pass (round) of quicksort, please give the order of the data. (6%)

Accepted Answer

快速排序第一輪分割 (以首元素為 pivot，Hoare 方式) 1. 初始序列：$[15,\;7,\;22,\;9,\;63,\;45,\;17,\;12]$。 2. 取 $pivot=15$，左指標 $i$ 從第 2 個元素起，右指標 $j$ 從最後一個元素起。 3. 迭代交換： - $i$ 移至 $22$ ($pivot$)，$j$ 停在 $12$ (<=$pivot$)，交換得到 $[15,7,12,9,63,45,17,22]$。

Question 5

A[5,2] address = 57, A[8,3] address = 93, element size = 1 byte, what is the address of A [7,7]? (10%)

Accepted Answer

已知元素大小 $s=1$，設基底位址為 $B$，採用 欄主序 (column‑major) 之二維陣列存放方式 $$	ext{addr}(A[i,j]) = B + \big((j-1)	imes R + (i-1)\big)s$$ 其中 $R$ 為陣列的列數。 1. 由 $A[5,2]$ 的位址 $$B + ( (2-1)R + (5-1) ) = 57 \;\Longrightarrow\; B = 53 - R$$ 2. 由 $A[8,3]$ 的位址

Question 6

Please use Prefix (8%) and Postfix (8%) to express following mathematical expression: 12x375117+21+3

Accepted Answer

核心觀念

Prefix（前置式）與 Postfix（後置式）是運算子位置不同的表示法：

中置式（Infix）：運算子放在兩個運算元中間，例如 $A+B$ 。
Prefix：運算子放在運算元之前，例如 $+AB$ 。
Postfix：運算子放在運算元之後，例如 $AB+$ 。

本題須依照原式的運算優先順序解析：

乘法 $\times$ 優先於加法 $+$ 。
加法採由左至右結合。

題目文字中的 x 視為乘法符號 $\times$ ，並將 375117 視為一個整數，因此原式為：

12\times375117+21+3

其運算結構為：

(12\times375117+21)+3

解題方法

第一步：建立運算樹

依照優先順序，先處理乘法：

12\times375117

再依由左至右的規則處理加法：

(12\times375117)+21

最後再加上 $3$ ：

((12\times375117)+21)+3

對應的運算樹如下：

第二步：轉換為 Prefix

Prefix 表示法採用「根節點、左子樹、右子樹」的順序，即前序走訪運算樹。

依序得到：

最外層加法： $+$
左子樹的加法： $+$
乘法： $\times$
運算元： $12$ 、 $375117$
運算元： $21$
最後的運算元： $3$

因此 Prefix 為：

+\ +\ \times\ 12\ 375117\ 21\ 3

Question 7

We try to use an adjacency matrix $M$ to describe the needed cost units of international trade between seven countries. Each country is represented by a vertex, which are $V_1$ , $V_2$ , $V_3$ , $V_4$ , $V_5$ , $V_6$ , and $V_7$ .

Please use Kruskal’s algorithm to draw the minimum cost spanning tree.

M= \begin{bmatrix} 0 & \infty & 11 & 1 & 3 & 4 & \infty \\ \infty & 0 & 3 & 11 & 7 & 20 & \infty \\ 11 & 3 & 0 & \infty & 15 & 7 & \infty \\ 1 & 11 & \infty & 0 & 3 & 2 & 9 \\ 3 & 7 & 15 & 3 & 0 & 8 & 6 \\ 4 & 20 & 7 & 2 & 8 & 0 & 1 \\ \infty & \infty & \infty & 9 & 6 & 1 & 0 \end{bmatrix}

Accepted Answer

核心觀念 本題考查以 Kruskal 演算法求無向加權圖的最小生成樹。 - 生成樹：連通所有頂點、沒有環的子圖。若有 $n$ 個頂點，生成樹恰有 $n-1$ 條邊。 - 最小生成樹：所有生成樹中，總權重最小者。 - Kruskal 演算法：將邊依權重由小到大排序，逐一考慮；若加入該邊不會形成環，就納入生成樹，直到選滿 $n-1$ 條邊。 - 由於此題的權重可能相同，等權邊的處理順序可以不同，因此可能得到不同形狀、但總成本相同的最小生成樹。 解題方法 矩陣是對稱的，因此代表無向圖。只需取矩陣上三角的非無限值作為邊，並依權重由小到大排列： | 權重 | 邊 | |---:|---| | 1 | $V1V4,\ V6V7$ | | 2 | $V4V6$ | | 3 | $V1V5,\ V2V3,\ V4V5$ | | 4 | $V1V6$ | | 6 | $V5V7$ | | 7 | $V2V5,\ V3V6$ | | 8 | $V5V6$ | | 9 | $V4V7$ | | 11 | $V1V3,\ V2V4$ | | 15 | $V3V5$ | | 20 | $V2V6$ | 依序套用 Kruskal 演算法： | 考慮的邊 | 判斷 | 處理結果 | |---|---|---| | $V1V4$，權重 1 | 兩端尚未連通 | 選入 | | $V6V7$，權重 1 | 兩端尚未連通 | 選入 | | $V4V6$，權重 2 | 連接兩個不同連通分量 | 選入 |

Question 8

Please use the data $\{40, 28, 56, 15, 63, 74, 98, 80\}$ to describe the sorting process in ascending order, with the result of each round using insertion sort (4%).

Please also use C code (ANSI C) to implement an insertion sort function (8%) with binary search (8%).

Accepted Answer

核心觀念

插入排序將資料分成「已排序前綴」與「尚未處理部分」。每一回合取出尚未處理部分的第一個元素，插入已排序前綴中適當的位置，並將較大的元素向右移一格。重複此步驟，直到所有元素都納入已排序前綴。

本題要求列出升冪排序的每一回合結果，並以二分搜尋尋找插入位置、用 ANSI C 實作插入排序。

解題方法與逐回合排序

初始資料為：

[40,\ 28,\ 56,\ 15,\ 63,\ 74,\ 98,\ 80]

每回合插入一個新元素；已排序前綴中的元素維持升冪。

回合	插入元素	插入後的完整序列
初始	—	$[40,\ 28,\ 56,\ 15,\ 63,\ 74,\ 98,\ 80]$
1	$28$	$[28,\ 40,\ 56,\ 15,\ 63,\ 74,\ 98,\ 80]$
2	$56$	$[28,\ 40,\ 56,\ 15,\ 63,\ 74,\ 98,\ 80]$
3	$15$	$[15,\ 28,\ 40,\ 56,\ 63,\ 74,\ 98,\ 80]$
4	$63$	$[15,\ 28,\ 40,\ 56,\ 63,\ 74,\ 98,\ 80]$
5	$74$	$[15,\ 28,\ 40,\ 56,\ 63,\ 74,\ 98,\ 80]$
6	$98$	$[15,\ 28,\ 40,\ 56,\ 63,\ 74,\ 98,\ 80]$
7	$80$	$[15,\ 28,\ 40,\ 56,\ 63,\ 74,\ 80,\ 98]$

例如第 3 回合插入 $15$ 時，已排序前綴為 $[28,\ 40,\ 56]$ 。 $15$ 小於前綴內所有元素，因此將 $28、40、56$ 各右移一格，再把 $15$ 放在前綴最前面。最後一回合插入 $80$ 時， $98$ 大於 $80$ ，因此將 $98$ 右移，並將 $80$ 放在它原本的位置之前。

ANSI C 程式碼：二分搜尋插入排序

🔒

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

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

免費註冊

Question 9

Please draw a figure to explain the key(s), hash function, and bucket(s) when using a hash table, and illustrate their relationship (6%).

Furthermore, please explain the difference between MD5 and SHA-1 hash function outputs (4%).

Accepted Answer

核心觀念

解題方法先依原頁確認：第 9 題要求畫出雜湊表中「鍵值、雜湊函數、桶」的關係，並比較 MD5 與 SHA-1 的輸出；題目沒有提供指定鍵值或表格大小，因此以下用一般雜湊表示意。

雜湊表以鍵值 $k$ 作為輸入，透過雜湊函數 $h(k)$ 算出桶的索引，再將資料存入對應的桶。常見的索引計算方式之一是取模，例如 $h(k)=k\bmod m$ ，其中 $m$ 是桶的數量。不同鍵值可能算出相同索引，稱為碰撞；可用鏈結串列等方式在同一桶中保存多筆資料。

解題方法

圖中以兩個不同鍵值 $k_1$ 、 $k_2$ 示範碰撞：雜湊函數將兩者都映射到索引 $j$ ，因此兩筆資料都存入桶 $j$ 。

鍵值 k₁ ──┐
          ├──> 雜湊函數 h(k) ──> 索引 j ──> 桶 j：[資料(k₁), 資料(k₂)]
鍵值 k₂ ──┘
                 因 h(k₁) = h(k₂)，產生碰撞

查詢時，先對欲查找的鍵值計算雜湊索引，再到對應桶中比對鍵值，確認是否找到目標資料。雜湊函數負責把鍵值轉成索引；桶則是存放資料的位置。

Question 10

Please briefly explain the average (2%) and worst-case (2%) time complexity, in Big O notation, of a hash table data structure when processing a search action.

Accepted Answer

核心觀念 原頁圖第 10 題詢問雜湊表執行「搜尋」時，平均情況與最壞情況的時間複雜度，並要求以 Big O 表示。 雜湊函數會把鍵值映射到表中的位置；若不同鍵值映射到同一位置，就會發生碰撞。搜尋時間主要取決於碰撞的多寡，以及碰撞處理方式。 解題方法 分析搜尋時，先看雜湊函數能否直接定位鍵值，再看目標位置是否因碰撞而需要額外比對。 - 平均情況：$O(1)$ 假設雜湊函數能均勻分布鍵值，且表的負載因子維持在適當範圍，碰撞數量平均受控。雜湊函數定位後，只需比對少數元素，因此平均搜尋時間為 $O(1)$。若使用鏈結法，平均時間可寫成 $O(1+\alpha)$，其中 $\alpha=n/m$ 是負載因子；

權重	邊
1	$V_1V_4,\ V_6V_7$
2	$V_4V_6$
3	$V_1V_5,\ V_2V_3,\ V_4V_5$
4	$V_1V_6$
6	$V_5V_7$
7	$V_2V_5,\ V_3V_6$
8	$V_5V_6$
9	$V_4V_7$
11	$V_1V_3,\ V_2V_4$
15	$V_3V_5$
20	$V_2V_6$

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

第 1 題

單向鏈結串列（Singly Linked List）之操作

雙向鏈結串列（Doubly Linked List）之操作

第 2 題

第 3 題

核心觀念

解題方法

第 4 題

第 5 題

第 6 題

核心觀念

解題方法

第一步：建立運算樹

第二步：轉換為 Prefix

第 7 題7 分

核心觀念

解題方法

第 8 題20 分

核心觀念

解題方法與逐回合排序

ANSI C 程式碼：二分搜尋插入排序

第 9 題10 分

核心觀念

解題方法

第 10 題4 分

其他考古題

111 年中央大學的其他科目

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

其他學校的資管系考古題

操作	目的	常用演算法步驟	時間複雜度	空間額外成本
建立	初始化空鏈結串列	`head ← NULL`	$O(1)$	$O(1)$
遍歷 (Traversal)	從頭到尾依序訪問每個節點	`ptr ← head; while(ptr ≠ NULL){ visit(ptr->data); ptr ← ptr->next; }`	$O(n)$	$O(1)$
搜尋 (Search)	找出第一個值等於 `key` 的節點	同遍歷，途中檢查 `ptr->data == key`	$O(n)$	$O(1)$
插入於頭部 (Insert‑Head)	在 `head` 前加入新節點	`new->next ← head; head ← new;`	$O(1)$	$O(1)$
插入於尾部 (Insert‑Tail)	在最後一個節點後加入新節點	若保有 `tail` 指標：`tail->next ← new; tail ← new;`<br>若無 `tail`：需遍歷至最後節點	$O(1)$ （有 `tail`）或 $O(n)$ （無 `tail`）	$O(1)$
插入於中間 (Insert‑After(p))	在已知節點 `p` 後插入	`new->next ← p->next; p->next ← new;`	$O(1)$	$O(1)$
刪除頭節點 (Delete‑Head)	移除 `head`	`temp ← head; head ← head->next; free(temp);`	$O(1)$	$O(1)$
刪除尾節點 (Delete‑Tail)	移除最後一個節點	需遍歷至倒數第二節點 `prev`，然後 `prev->next ← NULL`（若有 `tail` 可直接）	$O(n)$ （無 `tail`）或 $O(1)$ （有 `tail`）	$O(1)$
刪除中間節點 (Delete‑After(p))	刪除位於 `p` 之後的節點	`temp ← p->next; p->next ← temp->next; free(temp);`	$O(1)$	$O(1)$

操作	目的	常用演算法步驟	時間複雜度	空間額外成本
建立	初始化空雙向串列	`head ← tail ← NULL`	$O(1)$	$O(1)$
遍歷	前向或後向遍歷	前向：`ptr←head; while(ptr) { …; ptr←ptr->next; }`<br>後向：`ptr←tail; while(ptr) { …; ptr←ptr->prev; }`	$O(n)$	$O(1)$
搜尋	同遍歷，檢查 `ptr->data`	$O(n)$	$O(1)$
插入於頭部	新節點成為新 `head`	`new->next ← head; new->prev ← NULL; if(head) head->prev←new; head←new; if(tail==NULL) tail←new;`	$O(1)$	$O(1)$

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

第 1 題

單向鏈結串列（Singly Linked List）之操作

雙向鏈結串列（Doubly Linked List）之操作

第 2 題

第 3 題

核心觀念

解題方法

第 4 題

第 5 題

第 6 題

核心觀念

解題方法

第一步：建立運算樹

第二步：轉換為 Prefix

第 7 題7 分

核心觀念

解題方法

第 8 題20 分

核心觀念

解題方法與逐回合排序

ANSI C 程式碼：二分搜尋插入排序

第 9 題10 分

核心觀念

解題方法

第 10 題4 分

其他考古題

111 年中央大學的其他科目

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

其他學校的資管系考古題

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