高考申論題
114年
[資訊處理] 資料結構
第 四 題
📖 題組：
請回答下列問題：（每小題 4 分，共 20 分）
請回答下列問題：（每小題 4 分，共 20 分）
📝 此題為申論題，共 5 小題
小題 (四)
請說明若一個圖 G（V, E）的頂點數|V|為 n，而邊數|E|接近 n²，則相鄰串列（adjacency list）、相鄰矩陣（adjacency matrix）、或邊列表（edge list）中，那一種資料結構最適合用來儲存該圖？
思路引導 VIP
看到題目給定邊數 |E| 接近 n²，應立即聯想到這是「稠密圖（Dense Graph）」。接著比較相鄰串列、相鄰矩陣與邊列表在空間複雜度（特別是指標的額外開銷）與時間複雜度（查詢邊的效率）上的優劣，即可得出最佳選擇。
小題 (一)
請說明堆疊（Stack）及佇列（Queue）那一種資料結構較適合用來進行後序（Postfix）運算式的計算？
思路引導 VIP
看到後序運算式計算，應立刻回想其運算規則：由左至右掃描，遇到運算子時，需取『最近出現的兩個運算元』進行運算。這種『最近存入、最先取出』的需求，直接對應到後進先出（LIFO）的特性，進而推導出應使用何種資料結構。
小題 (二)
請說明在二元搜尋樹中，前序（Preorder）走訪、中序（Inorder）走訪、後序（Postorder）走訪、層序（Level-order）走訪那一種走訪順序可得到遞增的鍵值？
思路引導 VIP
首先回憶「二元搜尋樹（BST）」的核心定義：左子樹節點值 < 父節點值 < 右子樹節點值。接著對應四種走訪的遍歷順序（前序VLR、中序LVR、後序LRV、層序逐層），尋找符合「小 → 中 → 大」的走訪方式即可迅速得出答案。
小題 (三)
請說明在使用雜湊表時，若使用鏈結串列（chaining）處理碰撞（collision）問題，則搜尋的平均時間複雜度為下列何者？O(1)、O(log n)、O(n)或 O(sqrt{n})。
思路引導 VIP
考生看到此題應先回想「雜湊表 (Hash Table)」的設計初衷是為了達成 O(1) 的搜尋時間。接著思考「Chaining（鏈結法）」的機制，並透過計算載入因子（Load Factor, α = n/m）來推導「平均情況」下的搜尋時間複雜度。
小題 (五)
下列那幾項演算法可用於找出圖的最小生成樹（Minimum Spanning Tree）：Dijkstra 演算法、Floyd-Warshall 演算法、Prim 演算法、Bellman-Ford 演算法？
思路引導 VIP
考生看到此題應首先釐清圖論中「最小生成樹 (MST)」與「最短路徑 (Shortest Path)」兩大核心問題的差異。接著快速回想選項中各個經典演算法的適用情境與設計目的，即可精準選出正確答案並排除干擾選項。