108 年 國立中山大學資訊管理學系碩士班甲組《資料結構》
第 1 題
(10%) The complexity and stability of sorting algorithms. (2% for each sorting algorithm)
| Algorithm | Best Case | Average Case | Worst Case | Stable |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | yes |
| Insertion Sort | ||||
| Selection Sort | ||||
| Quick Sort | ||||
| Merge Sort | ||||
| Heap Sort |
登入後即可作答並保存紀錄。
核心觀念
本題比較各種排序法的三項時間複雜度：
- Best Case：所有大小為 的輸入中，執行時間最少的情況。
- Average Case：在平均輸入分布下的期望執行時間。
- Worst Case：所有大小為 的輸入中，執行時間最多的情況。
- Stable：若兩筆資料的排序鍵值相同，排序後仍維持原本的相對順序。
以下採用標準教材中的實作版本；Bubble Sort 採用「若一輪沒有交換便提前結束」的最佳化。
完整答案
| Algorithm | Best Case | Average Case | Worst Case | Stable |
|---|---|---|---|---|
| Bubble Sort | Yes | |||
| Insertion Sort | Yes | |||
| Selection Sort | No | |||
| Quick Sort | No | |||
| Merge Sort | Yes | |||
| Heap Sort | No |
各排序法分析
1. Bubble Sort
每一輪比較相鄰元素，將較大的元素逐步往右推。
- 最佳情況：資料已排序完成。第一輪掃描後沒有任何交換，立即停止，因此為 。
- 平均與最差情況：需要多輪比較與交換：
- 穩定性：只交換「嚴格逆序」的相鄰元素，不交換鍵值相等的元素，因此穩定。
2. Insertion Sort
逐一取出尚未排序的元素，插入左側已排序區域的正確位置。
- 最佳情況：資料已排序。每個元素只需與前一個元素比較一次：
- 最差情況：資料逆序。第 個元素必須向左移動約 次：
- 平均情況：平均需要移動約一半的已排序元素，總成本仍為 。
- 穩定性：插入時將新元素放在相等元素之後，不會改變相等鍵值的原始順序，因此穩定。
3. Selection Sort
每一輪從未排序區域找出最小值，再與該區域的第一個元素交換。
無論原始資料是否已排序，都必須完整掃描未排序區域：
因此最佳、平均、最差情況皆為 。
標準 Selection Sort 不穩定。例如：
第 2 題
Consider a binary tree T whose preorder and inorder traversal sequences are as follows.
Preorder: F,B,A,D,C,E,G,I,H.
Inorder: A,B,C,D,E,F,G,H,I.
A. Please show the postorder traversal sequence of T. (5%)
B. Please show the level-order traversal sequence of T. (5%)
登入後即可作答並保存紀錄。
核心觀念
本題考查由 Preorder（前序） 與 Inorder（中序） 唯一還原二元樹，再求其 Postorder（後序） 與 Level-order（層序）。
三種走訪定義如下：
- 前序：根 → 左子樹 → 右子樹
- 中序：左子樹 → 根 → 右子樹
- 後序：左子樹 → 右子樹 → 根
- 層序：依樹的深度，由上到下、同一層由左到右
關鍵定理是：
- 前序的第一個節點必為目前子樹的根。
- 在中序序列中找到根後，根左側是左子樹，根右側是右子樹。
- 根在前序中確定後，可依左、右子樹節點數切分後續序列。
解題方法：由前序與中序還原二元樹
1. 還原根節點 F
前序第一個節點為 ，因此 是整棵樹的根。
中序序列為：
因此：
- 左子樹的中序：
- 右子樹的中序：
左子樹共有 個節點，所以前序中 後面的前 個節點屬於左子樹：
- 左子樹前序：
- 右子樹前序：
2. 還原 F 的左子樹
左子樹前序為：
第一個節點 為左子樹的根。
左子樹中序為：
所以：
- 的左子樹中序：
- 的右子樹中序：
因此：
- 的左子節點為
- 的右子樹前序為
右子樹以前序第一個節點 為根。其對應中序為：
因此：
- 的左子節點為
- 的右子節點為
左子樹結構如下：
3. 還原 F 的右子樹
右子樹前序為：
右子樹中序為：
第 3 題
Consider a sequence of keys: 9,4,8,7,12,15,3,5,14,18 for inserting into a heap.
A. Please draw the result after inserting all these keys into an empty min heap. (5%)
B. Following A, please draw the result after deleting the root. (5%)
登入後即可作答並保存紀錄。
核心觀念
最小堆（min heap）必須同時滿足：
- 完全二元樹：除最底層外，其餘層皆填滿；最底層由左至右填入。
- 最小堆序性質：每個父節點的鍵值都不大於其子節點：
以陣列表示時，若根節點位置為 ：
插入元素時，先放入完全二元樹的下一個空位置，再執行上濾（percolate up）；刪除根節點時，先以最後一個節點補到根，再執行下濾（percolate down）。
A. 插入所有鍵值後的最小堆
插入順序為：
以下以陣列表示每次插入並完成上濾後的結果。
| 插入值 | 插入並上濾後的堆陣列 | 關鍵調整 |
|---|---|---|
| 成為根 | ||
| ，與 交換 | ||
| ，不需交換 | ||
| 先與 交換 | ||
| 先與 交換，再與 交換 | ||
| 先與 交換，再與 交換 | ||
因此，完成所有插入後的最小堆陣列為：
對應的完全二元樹如下：
3
/ \
5 4
/ \ / \
7 12 15 8
/ \ /
9 14 18
每一個父節點均不大於其子節點，例如：
符合最小堆性質。
B. 刪除根節點後的最小堆
原堆為：
第 4 題
Consider a sequence of keys 5,19,23,13,7,17,3,2,11. Please draw the result after inserting all these keys into an empty AVL tree. (8%)
登入後即可作答並保存紀錄。
關鍵步驟總結
- 插入 5、19、23 後在節點 5 發生 RR，左旋 → 根 19。
- 插入 13、7、17，保持平衡。
- 插入 3 時於節點 5 發生 LL，右旋 → 子樹根變為 5。
- 插入 2、11 僅更新高度，最後整體仍平衡。
最終 AVL 樹結構
第 5 題
A complete binary tree B containing 100 nodes (with indices 1, 2, ..., 100) is stored in an array. Let node i be in position i of the array (array[0] is empty).
A. What is the height of tree B? (4%)
B. What is the index of the parent of array[71]? (4%)
C. How many nodes are leaf nodes? (4%)
登入後即可作答並保存紀錄。
核心觀念
完全二元樹（complete binary tree）具有以下特性：
- 除最後一層外，其餘各層皆已填滿。
- 最後一層的節點由左至右連續排列。
- 使用從 開始的陣列表示時：
- 節點 的左子節點索引為 。
- 節點 的右子節點索引為 。
- 節點 的父節點索引為 。
- 深度為 的節點，其索引範圍為 至 。
以下採用資料結構常見定義：樹高是根到最深葉節點的最長路徑所包含的「邊」數，根的深度為 。
解題方法
A. 樹 的高度
先找出 所在的層次：
因此，索引 至 的節點位於深度 的最後一層。最深葉節點的深度為 ，所以樹高為：
補充：深度 到深度 共 層。若教材將高度定義為「層數」，則會寫成 ；本題依常見的「邊數」定義，答案為 。
B. array[71] 的父節點索引
使用父節點公式：
代入 ：
第 6 題
(12%) Consider the following recursive program:
Public int fact(int a, int b)
{
If (a%b == 0) return b;
else return fact(b, a%b);
}
(1) What is the output given by fact(17, 3)? (4%)
(2) What is the output given by fact(3, 9)? (4%)
(3) Explain briefly the purpose of the fact function. (4%)
登入後即可作答並保存紀錄。
核心觀念
本題考查「歐幾里得演算法」求最大公因數（Greatest Common Divisor, GCD）。
關鍵性質為：
當 時，表示 整除 ，因此：
程式的關鍵部分是：
if (a % b == 0) return b; else return fact(b, a % b);
其中 % 表示取餘數。函式名稱雖然是 fact，但它不是計算階乘，而是計算最大公因數。
解題方法
每次呼叫函式時，先計算 ：
- 若餘數為 ，直接回傳 。
- 若餘數不為 ，遞迴呼叫
fact(b, a % b)。 - 新的第二個參數是更小的餘數，因此最後必定會遇到餘數為 的情況。
第（1）小題：fact(17, 3)
依序展開：
因此：
接著：
所以：
最後：
符合停止條件，回傳 ：
因此：
第（2）小題：fact(3, 9)
第一次計算：
第 7 題
For a given graph G = (V, E), arbitrarily partition the nodes V into two disjoint sets, V₁ and V₂. Let E₁ be all the edges such that both nodes in the edge are in V₁, E₂ be all edges such that both nodes are in V₂, and E₃ be all edges (u, v) such that u∈ V₁ and v∈ V₂. If we construct a minimum spanning tree T₁ on graph (V₁, E₁) and a minimum spanning tree T₂ on (V₂, E₂), then connect T₁ and T₂ on the lowest-weighted edge connecting T₁ and T₂. Will the connected result be a minimum spanning tree of G? Proof the above method if it is correct, or give a counterexample. (15%)
登入後即可作答並保存紀錄。
反例構造
考慮圖 ，，邊權重如下
| 边 | 重量 |
|---|---|
任意把 分為 、。
- ， 必為唯一邊，重量 。
- ， 必為唯一邊，重量 。
第 8 題
(a) For a directed graph G = (V, E), V = {1, 2, 3, 4, 5, 6, 7, 8, 9}, E = {(1, 2), (1, 4), (1, 5), (2, 3), (2, 4), (2, 6), (3, 5), (3, 6), (4, 7), (4, 8), (5, 4), (5, 7), (5, 8), (6, 5), (6, 8), (6, 9), (8, 7), (9, 5), (9, 8)}, and each (u, v) indicates an arc from vertex u to vertex v. Assume the adjacency lists are in sorted order: for example, when iterating through the arcs pointing from 1, consider the arc 1→2 before 1→4, 1→5. Run Depth-First Search, starting at vertex 1. Complete the list of vertices in the order they are first discovered by DFS: 123______. (5%)
(b) For the same graph G, run Breadth-First Search, starting at vertex 1. Complete the list of vertices in the order in which they are enqueued: 1245____. (5%)
(c) Consider two vertices m and n that are simultaneously on the function-call stack at some point during the execution of depth-first search from vertex s in a digraph. Which of the following must be true? (5%)
(I) There is both a directed path from s to m and a directed path from s to n.
(II) If there is no directed path from m to n, then there is a directed path from n to m.
(III) There is both a directed path from m to n and a directed path from n to m.
登入後即可作答並保存紀錄。
(a) 123547869
(b) 124536789
第 9 題
For each of the following scenarios, give the "best" data structure or a combination of data structures, for example, an unsorted array, linked list, doubly linked list, circular linked list, stack, or queue. In each case, justify your answer briefly.
(a) Suppose that a shop decided that customers who come first will be served first. (2%)
(b) A list must be maintained so that any element can be accessed randomly. (2%)
(c) A program needs to remember operations it performed in opposite order. (2%)
(d) The size of a file is unknown. The entries need to be entered as they come in. Entries must be deleted when they are no longer needed. It is important that structure has flexible memory management. (2%)
登入後即可作答並保存紀錄。
核心觀念
本題考查資料結構的「資料存取順序」與「記憶體配置方式」：
- Queue（佇列）：FIFO，先進先出。
- Stack（堆疊）：LIFO，後進先出。
- Array（陣列）：元素連續儲存，可依索引直接隨機存取，時間複雜度為 。
- Linked list（鏈結串列）：節點以指標連接，大小可動態調整；插入與刪除不必搬移大量元素。
- Doubly linked list（雙向鏈結串列）：每個節點同時具有前、後指標，適合需要雙向移動或快速刪除已知節點的情況。
- Circular linked list（循環鏈結串列）：尾端連回首端，適合循環處理。
解題時應先判斷題目要求的核心操作，再選擇最符合該操作特性的資料結構。
解題方法與各小題分析
(a) 先到先服務
題意要求「先到的顧客先接受服務」，這是典型的 FIFO：
- 新顧客從佇列尾端加入，稱為 enqueue。
- 服務時從佇列前端取出，稱為 dequeue。
- 因此最早進入的顧客會最早離開。
最適合的資料結構是 queue（佇列）。
若以陣列實作，通常可使用循環佇列，避免每次刪除首元素都搬移其他元素；若以鏈結串列實作，則維護 front 與 rear 指標即可使加入與刪除皆為 。
(b) 任一元素皆須能隨機存取
「隨機存取」表示可以直接依索引取得任意位置的元素，例如：
陣列的元素連續儲存，因此可透過起始位址與索引計算位址：
所以存取任意元素的時間複雜度為 。
最適合的是 unsorted array（未排序陣列）。題目只要求隨機存取，沒有要求維持排序，因此不需要額外排序。
鏈結串列則必須從頭節點逐一走訪至第 個節點，隨機存取時間為 ，不符合題目重點。