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

題號	考點主題	答案
A-I-1	圖形的儲存表示法：Adjacency Matrix／Adjacency List／Incidence Matrix	(a)
A-I-2	Hash Function 與雜湊表（Hash Table）基本概念	(c)
A-I-3	Merge Sort 與 Heap Sort 演算法邏輯	(b)
A-I-4	Binary Heap 與 Fibonacci Heap 操作複雜度比較表	(b)

A-II-5(1)高度 8 之 Binary Tree 最多節點數

考點：一般Binary Tree高度與節點數關係（最多／最少）

511

A-II-5(2)高度 9 之 Binary Tree 最少節點數

考點：一般Binary Tree高度與節點數關係（最多／最少）

A-II-6BST 依序插入求最深節點

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

A-II-7(1)多重有向圖的 Arc 總數計算

考點：圖形的儲存表示法：Adjacency Matrix／Adjacency List／Incidence Matrix

$n (n - 1) K$

A-II-7(2)Multigraph 儲存方式：Adjacency Matrix 或 Adjacency List

考點：圖形的儲存表示法：Adjacency Matrix／Adjacency List／Incidence Matrix

選 Adjacency List。本圖是 multigraph，任兩點間有 $K$ 條各帶 cost、time 的平行邊；Adjacency Matrix 每格只能存一個值，存不下 $K$ 筆；Adjacency List 可讓同一鄰居重複出現多個節點，各自存自己的 cost、time。

A-II-7(3)最小成本走訪所有節點：Shortest Path 或 MST 皆不適用

考點：Traveling Salesman Problem（TSP）與 NP-hard

兩者皆不能，此問題為 TSP（NP-hard）。

1-ALL shortest path 求的是起點到各點各自的最短路徑，彼此不接續，拼不成一條走訪所有節點的路線。
MST 只求以最小總邊權連通所有節點，結果是有分岔的樹，不是走訪路線。

A-II-7(4)固定常數 L 之走訪問題多項式時間可解性

考點：Traveling Salesman Problem（TSP）與 NP-hard

可以。 $L$ 是固定常數：從 $n$ 國中選 $L$ 國（ $(\binom{n}{L})$ 種），再枚舉走訪順序（ $L!$ 種），逐一檢查總成本 $\leq Q$ 且總時間 $\leq P$ 。複雜度 $O (n^{L} \cdot L!) = O (n^{6} \cdot 720)$ ，為多項式時間。

III-8(a)均勻分布資料排序下界之 True／False 判斷

考點：MSD Radix Sort（Bucket Sort）：適用情境與複雜度

False。 $Ω (n \log n)$ 是比較式排序的下界；資料均勻分布於已知範圍 $[0, 1000]$ ，可用 Bucket Sort，期望時間 $O (n)$ 。

III-8(b)BST 列印與建立 Min-Heap 之時間複雜度判斷

考點：BST 依序插入節點深度追蹤與 Inorder Traversal 列印複雜度、Binary Heap 與 Fibonacci Heap 操作複雜度比較表

False。Inorder 走訪 BST 印出 $n$ 個整數為 $O (n)$ ；以 bottom-up Build-Heap 建 min-heap 為 $O (n)$ ；合計 $O (n)$ ，不是 $ω (n \log n)$ 。

III-8(c)DAG 負權重取負後能否使用 Dijkstra's 求最長路徑

考點：Dijkstra's 演算法為何不能處理負邊

False。取負後原本為正的邊變成負邊，圖仍含負權重，不符合 Dijkstra's 要求邊權非負的前提。

III-8(d)判斷 Cycle 存在性是否受限於 Cycle 數量指數級增長

考點：Dijkstra's 演算法為何不能處理負邊

False。經過 $(s, t)$ 且長度 $\leq Q$ 的 cycle 存在，若且唯若 $t$ 到 $s$ 的最短路徑長 $\leq Q - w (s, t)$ ；權重皆為正，用 Dijkstra's 求 $t$ 到 $s$ 的最短路徑即可在多項式時間判斷，不必列舉 cycle。

III-8(e)Red-Black Tree 與 Array 求中位數之時間複雜度比較

考點：Red-Black Tree 未 Augmented 時不具備 O(log n) 排名／中位數查詢能力、Select 演算法（找第 i 小）：樸素方法、Partition-based 與 Median-of-Medians 達成 Worst-case Linear Time

True。Mary 對未排序陣列用 Median-of-Medians（worst-case $O (n)$ ）或 Quickselect（期望 $O (n)$ ）；Tom 的 RB-tree 未存 subtree size，只能 inorder 數到第 $n / 2$ 個， $O (n)$ 。

IV-9(a)工廠機台佈局邊界檢查與安全距離檢查演算法

考點：矩形碰撞偵測：暴力配對 O(n²) 與掃描線（Sweep Line）優化至 O(n log n)

(i) 邊界檢查：每台機台檢查 $x_{i} - \frac{u_{i}}{2} \geq 0$ 、 $x_{i} + \frac{u_{i}}{2} \leq U$ 、 $y_{i} - \frac{v_{i}}{2} \geq 0$ 、 $y_{i} + \frac{v_{i}}{2} \leq V$ ，任一不成立即越界。每台 $O (1)$ ，共 $O (n)$ 。

(ii) 安全距離檢查：任兩台 $i, j$ 須滿足 $| x_{i} - x_{j} | \geq \frac{u_{i} + u_{j}}{2} + d$ 或 $| y_{i} - y_{j} | \geq \frac{v_{i} + v_{j}}{2} + d$ ，兩者皆不成立即違反。逐一檢查 $(\binom{n}{2})$ 對，共 $O (n^{2})$ 。

IV-9(b)機台佈線最小成本連接：MST 與 Hamiltonian Cycle 可解性比較

考點：Traveling Salesman Problem（TSP）與 NP-hard

(i) 可以。機台為頂點、 $c_{i j}$ 為邊權重，即求 Minimum Spanning Tree，用 Kruskal's 或 Prim's 在多項式時間求得。

(ii) 不行。最終圖須為 cycle 即最小成本 Hamiltonian Cycle（TSP），為 NP-hard，除非 $P = N P$ ，否則無多項式時間解法。

成大其他年份

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