114 中興資工所考古題詳解｜軟體考點分析

題型與配分

全卷 7 頁、26 題、100 分，簡章規定不可使用計算機。單選題畫在答案卡，計算題寫在答案卷，卷面註明未依規定作答不予計分。

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

• 第 1 題｜哪個排序演算法是 non-comparison-based sort：Heap、Quick、Counting、Merge
• 第 2 題｜哪個排序演算法的最壞時間複雜度最好
• 第 3 題｜在資源受限的條件下求最大價值，用哪種技巧最有效率：greedy、圖 traversal、divide and conquer、DP
• 第 4 題｜可能有負邊權的加權 directed graph，求單一來源到其他所有頂點的 shortest path，用哪個演算法
• 第 5 題｜關於 NP-complete 的四個敘述哪些為真，其中一個涉及 Halting Problem
• 第 6 題｜T = "abcdefg"、P = "bcd"，哪個 string matching 演算法用 hash 來有效率地找出第一個符合的位置
• 第 7 題｜[38, 27, 43, 3, 9, 82, 10] 用 Merge Sort 遞增排序的結果
• 第 8 題｜values = [10, 4, 3, 7, 6]、weights = [5, 2, 1, 3, 4]、容量 9 的背包，用 DP 求最大總價值
• 第 9 題｜DFS 如何偵測 directed graph 中的 cycle
• 第 10 題｜關於 DAGtopological sort 的敘述哪個為真
• 第 11 題｜以 array 實作的 stack，哪個操作通常是 O(1)
• 第 12 題｜doubly linked list 相對於 singly linked list 的主要優點
• 第 13 題｜BST 存有 1 到 100，假設分布平衡，哪個元素的搜尋時間最短
• 第 14 題｜文字編輯器的 undo 操作最適合用哪種資料結構
• 第 15 題｜open addressing（linear probing）hash table 的 load factor 接近 1 時最可能發生什麼
• 第 16 題｜把鍵插入已滿的 B-Tree 節點時，為了維持性質，最先做什麼操作
• 第 17 題｜Red-Black Tree 插入的時間複雜度
• 第 18 題｜Red-Black Tree 插入新節點後，可能用哪些操作恢復性質
• 第 19 題｜以 array 實作的 circular queue，如何判斷 queue 已滿
• 第 20 題｜BFS 通常用哪種資料結構實作

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

• 第 1 題（5%）｜6 個活動 A–F 各有開始與結束時間，用 greedy 演算法選出最多個互不重疊的活動
• 第 2 題（5%）｜array [9, 3, 7, 1, 6, 5, 8] 做兩趟 Bubble Sort 遞增排序後的結果
• 第 3 題（5%）｜依序把 15、10、20、8、12、17、25、19 插入空的 BST，刪除值為 20 的節點並以 in-order successor 取代，求更新後 BST 的 postorder traversal
• 第 4 題（5%）｜用 Kruskal's algorithm 求給定圖的 minimum spanning tree 總成本
• 第 5 題（10%）｜binary min-heap [1, 3, 2, 10, 7, 6, 9] 插入元素 4，要求說明完整的插入過程：新元素最初放在哪裡、逐步說明 heapify-up 並列出每次交換後的中間狀態、最後的 min-heap array，並說明每次比較與交換的理由
• 第 6 題（10%）｜設計並描述一個可隨元素加入而成長的 dynamic array 容器，說明四個面向：記憶體管理（如何配置與釋放底層儲存）、容量擴張策略（成長倍數與取捨）、索引操作（如何保證 O(1) 隨機存取）、任意位置插入與刪除的時間複雜度（含 amortized complexity 與最壞情況的差別）

作答時要注意的地方

1. 單選題未答 0 分、答錯不倒扣，卷首另附考生注意事項。
2. 單選題畫在答案卡，計算題寫在答案卷，未依規定作答不予計分。
3. 第 3 題要先刪除節點 20 並以 in-order successor 取代，再求 postorder traversal。
4. 第 5 題要求列出每次交換後的中間狀態並說明理由。
5. 第 6 題要談到記憶體管理、容量擴張策略、索引操作、插入刪除複雜度四個面向。

準備方向

• 排序的性質與複雜度：114 第 1、2、7 題與計算題第 2 題，109 第 9 題、110 第 8-B 題、111 第 1-I、1-II 題、113 第 12、16、19 題也有。
• DP 與背包：114 第 3、8 題，110 第 9-A 題、113 第 17、18、20 題也有。
• shortest path：114 第 4 題，109 第 8 題、110 第 9-D 題、111 第 3-V 題、113 第 14 題也有。
• NP 理論：114 第 5 題，110 第 9-E 題、111 第 1-IV、1-V 題、112 D-V 題、113 B-2 第 2 題也有。
• string matching：114 第 6 題，112 D-I 考 KMP 的 failure function。
• DFS、topological sort 與 BFS：114 第 9、10、20 題，110 第 7-A 題也有演算法與資料結構的搭配。
• balanced tree：114 第 16–18 題，110 第 6-C 題、113 第 2 題也有。
• 活動選擇與 greedy 法：114 計算題第 1 題，113 第 17 題也有。
• BST 的刪除與 traversal：114 計算題第 3 題，111 第 3-VI 題、113 第 5–9 題與 B-2 第 1 題也有。
• Kruskal 與 MST：114 計算題第 4 題，110 第 7-A、9-C 題、111 第 2-III、3-IV 題、113 B-1 第 6 題也有。
• min-heap 的插入：114 計算題第 5 題，110 第 7-C 題、111 第 1-III 題也有。
• dynamic array 與 amortized 複雜度：114 計算題第 6 題。