成大 114 年資管所資料結構參考答案

題號	考點主題	答案
A-1-1	Master Theorem 三種基本情形（Case 1／2／3）與 Strassen's 矩陣乘法範例	(d)
A-1-2	NP-Hard 與 NPC	(c)
A-1-3	K-way Merge：Pointers 法與 Selection Tree 加速	(b)
A-1-4	Queue 的實作方式比較（Array／Linked List，Linear／Circular）	(b)
A-1-5	Hash Function 與雜湊表（Hash Table）基本概念	(d)
A-1-6	LSD Radix Sort：Distribution／Merge 技巧與 Linear Time 分析	(c)
A-1-7	Orthogonal List（正交串列）稀疏矩陣表示法	(b)
A-1-8	Binary Heap 與 Fibonacci Heap 操作複雜度比較表	(a)
A-1-9	Merge Sort 與 Heap Sort 演算法邏輯	(d)
A-1-10	Trie（字典樹／前綴樹）與 Hash Table 比較	(c)

A-2證明 Partition Problem 為 NP-Complete（由 Subset Sum 歸約）

考點：NP-Hard 與 NPC

(1) Partition $\in$ NP：給定一組切分，加總兩邊比較是否相等， $O (n)$ 即可驗證。

(2) Subset Sum $\leq_{p}$ Partition：給定 Subset Sum 實例 $(A = {a_{1}, \dots, a_{n}}, t)$ ，令 $S = \sum a_{i}$ ，建構 $A^{'} = A \cup {2 S - t, S + t}$ ，總和 $4 S$ ，合法切分兩邊各為 $2 S$ ；建構為多項式時間。

(3) 若 $A$ 有子集合 $B$ 使 $\sum B = t$ ，則 ${2 S - t} \cup B$ 和為 $2 S$ ，為合法切分。反之， $(2 S - t) + (S + t) = 3 S > 2 S$ ，兩個新元素必分屬兩邊，含 $2 S - t$ 的一邊從 $A$ 中取出的元素和恰為 $t$ ，即 Subset Sum 的解。

故 Partition 為 NP-Complete。

題號	考點主題	答案
B-1-1	Heap 的建立與 heapify-up／heapify-down	(b)

題號	考點主題	答案
B-1-2	Heap 的建立與 heapify-up／heapify-down	(b)
B-1-3	Binary Heap 與 Fibonacci Heap 操作複雜度比較表	(d)

B-2-1列出兩組合法拓撲排序

考點：Topological Sort（拓撲排序）與 AOV Network

不存在合法的拓撲排序：圖中有有向環 $B \to C \to E \to B$ ，不是 DAG。

B-2-2Adjacency List 拓撲排序之 Worst-case Big-O

考點：Topological Sort（拓撲排序）與 AOV Network

$O (V + E)$

題號	考點主題	答案
B-2-3	Strongly Connected Component（SCC）定義與求解概念	(a)(b)

B-3-1有向圖最大 Arc 數公式

考點：Simple Graph 與 Multiple Edges 定義

$V (V - 1)$

B-3-2連通無向圖最小 Arc 數公式

考點：Spanning Tree 定義與性質

$V - 1$

B-3-3含 Self-loop 完全無向圖之最小 Degree

考點：Simple Graph 與 Multiple Edges 定義

$V + 1$

B-4-1BST Insert 之 Big-O

考點：Binary Search Tree 基礎應用場景：為何選擇 BST（O(log n) 搜尋、有序輸出）

$O (h)$ ：平均 $O (\log n)$ ，最壞（退化成鏈） $O (n)$ 。

B-4-2BST Preorder Traversal 之 Big-O

考點：BST 依序插入節點深度追蹤與 Inorder Traversal 列印複雜度

$O (n)$

B-5由 Postorder 重建 Complete AVL Tree

考點：由前序＋中序／中序＋後序決定唯一 Binary Tree（前序＋後序為何不行）

B-6BST 依序插入與刪除：僅能異動葉節點的鍵值下沉交換（禁止旋轉）

考點：BST 依序插入與刪除：僅能異動葉節點的鍵值下沉交換規則（禁止旋轉）

（如簡答圖）

成大其他年份

115 計算機概論 115 資料結構 114 計算機概論 114 資料結構 113 計算機概論 113 資料結構 112 計算機概論 112 資料結構 111 計算機概論 111 資料結構