114 中興資工所軟體考點分析

題型與配分

系所「資訊工程學系 甲組」，科目：資料結構與演算法，全卷 7 頁、26 題、100 分，不可以使用計算機。

這一年完全沒有倒扣（113 年前半還有倒扣 0.5 分）。單選題 20 題務必全部作答。

Part 1 單選題考點（1–20，各 3 分）

這一區幾乎全是觀念判斷，沒有需要長時間計算的題目：

• 第 1 題｜哪一種排序是非比較式（Counting Sort）
• 第 2 題｜哪一種排序的最壞複雜度最好（Merge Sort）
• 第 3 題｜資源受限下求最大價值該用什麼技巧（動態規劃）
• 第 4 題｜有負權邊的單源最短路徑（Bellman-Ford）
• 第 5 題｜NP-complete 的四個敘述何者為真 —— 包含「停機問題是否為 NP-complete」（否）
• 第 6 題｜哪個字串比對演算法用雜湊（Rabin-Karp）
• 第 7 題｜[38, 27, 43, 3, 9, 82, 10] 用 Merge Sort 排序的結果
• 第 8 題｜values = [10,4,3,7,6]、weights = [5,2,1,3,4]、容量 9 的 0-1 knapsack 最大價值
• 第 9 題｜DFS 如何偵測環（找出指向遞迴堆疊中祖先的 back edge）
• 第 10 題｜DAG 的拓撲排序性質（可以有多個合法順序）
• 第 11 題｜陣列實作的 stack 哪個操作是 O(1)（push）
• 第 12 題｜雙向串列相對單向串列的主要優勢（可雙向走訪）
• 第 13 題｜BST 存 1–100 時哪個元素搜尋最快（50，根節點）
• 第 14 題｜文字編輯器的 undo 適合用哪種結構（Stack）
• 第 15 題｜open addressing 的 load factor 接近 1 時會發生什麼（平均探測次數增加）
• 第 16 題｜插入已滿的 B-Tree 節點時先做什麼（分裂）
• 第 17 題｜紅黑樹的插入複雜度（O(log n)）
• 第 18 題｜紅黑樹插入後用什麼操作恢復性質（旋轉與重新著色）
• 第 19 題｜陣列實作的環狀佇列如何判斷已滿（(rear + 1) % size == front）
• 第 20 題｜BFS 常用哪種資料結構（Queue）

Part 2 計算題考點（1–6，共 40%）

• 第 1 題（5%）｜6 個活動的活動選擇問題，用貪婪法求最多能選幾個不重疊的活動
• 第 2 題（5%）｜陣列 [9, 3, 7, 1, 6, 5, 8] 做 Bubble Sort 兩趟後的結果
• 第 3 題（5%）｜依序插入 15, 10, 20, 8, 12, 17, 25, 19 到 BST，刪除 20 並用 in-order successor 取代，再求 post-order
• 第 4 題（5%）｜用 Kruskal 求給定圖的 MST 總成本
• 第 5 題（10%）｜binary min-heap [1, 3, 2, 10, 7, 6, 9] 插入 4，要逐步描述完整過程：新元素初始放哪、heapify-up 的每一次交換與中間狀態、最終陣列。題目明訂要「清楚說明每一步的比較與交換理由」
• 第 6 題（10%）｜設計一個動態陣列容器，說明四件事：
• 記憶體管理：如何配置與釋放、用什麼機制
• 容量擴張策略：滿了要如何增加、成長倍數的取捨（記憶體用量 vs 效能）
• 索引操作：如何保證 O(1) 隨機存取
• 插入刪除複雜度：任意位置的預期複雜度、攤銷複雜度為何與最壞情況不同

這份考卷的難點

1. 第 6 題（10 分）的動態陣列設計是全卷唯一的開放式申論，四個面向都要談到，尤其「攤銷複雜度為何與最壞情況不同」需要真的懂加倍策略的分析。
2. 第 5 題（10 分）要求逐步展示，只給最終陣列不夠 —— 要畫出每次交換後的中間狀態。
3. 選擇題整體偏易，20 題裡大部分是課本定義題 —— 這代表計算題的 40 分才是拉開差距的地方。
4. 第 8 題的 knapsack 要在紙上跑 DP 表（5 個物品 × 容量 9），是選擇題裡最花時間的一題。

準備建議

• 114 年沒有倒扣，選擇題 20 題全部要作答
• 動態陣列的攤銷分析（114 第 6 題）在台大 113/115、中正 115 也都考過，是跨校高頻主題
• 選擇題偏向課本定義（哪種結構適合什麼場景、哪個演算法用於什麼情況），把資料結構課本的每章重點整理一遍即可
• 計算題要求「描述過程」，練習時就要養成寫出中間狀態的習慣