111 交大資工所考古題詳解｜軟體考點分析

題型與配分

全卷 12 頁、40 題、100 分，不可使用計算機，用答案卡作答。

計分規則：全卷 40 題為多選題，每題有一個以上的正確選項。填答必須完全符合正確選項，答錯沒有倒扣，若有任一選項不符則該題 0 分。每題 2.5 分。

逐題考點

balanced tree（1–3、9、28–30）

• 第 1 題｜給一棵 AVL tree 插入 61，判斷插入後的祖先、葉節點、兄弟關係
• 第 2 題｜承第 1 題的結果再刪除 7，判斷結果樹的節點關係
• 第 3 題｜AVL 的性質：最壞搜尋、traversal 的複雜度、插入的複雜度、是否比 red-black tree 查詢快
• 第 9 題｜空 red-black tree 依序插入 5, 2, 7, 3, 4 後的外部節點數、紅節點數、節點 3 的顏色、旋轉次數
• 第 28 題｜BST 的插入與刪除是否 O(h)、找最大值是否 O(1)、空間是否 O(n)、樹形是否由 key 集合唯一決定
• 第 29 題｜給五棵 BST，對根節點做一次旋轉後樹高可能變高的是哪些
• 第 30 題｜給一棵 AVL tree，哪些插入或刪除操作會使它失衡

圖論（4、5、8、10、33–35）

• 第 4 題｜用 Kruskal 求 MST，判斷總權重、節點 0 到 7 的路徑、節點 3 的 incident edge 權重總和、MST 的邊數
• 第 5 題｜給一段 pseudo-code，判斷它的功能、複雜度、能否處理 negative cycle、能否處理 weighted graph
• 第 8 題｜有向 weighted graph 從 b 出發跑 Dijkstra，判斷各條 shortest path 的邊數與總權重
• 第 10 題｜BFS 的處理順序、strongly connected 的定義、BFS 用的資料結構、complete graph 的定義
• 第 33 題｜MST 的 light edge 與 cut property：「在某棵 MST 中」與「是某個割的 light edge」的關係、唯一 MST 與唯一 light edge 的雙向關係，以及 cycle 上最大權邊的性質
• 第 34 題｜給一張 flow network（流量與容量相同），推出 x、y、z、a、b、c 的關係與流值，並判斷是否為 max flow
• 第 35 題｜undirected graph 的 adjacency matrix 性質：是否 symmetric、列和與 degree 的關係、邊數的計算式、奇數度頂點個數

hash（7、26、27）

• 第 7 題｜h(key)=key mod 7，插入 1, 2, 4, 6, 8, 12, 15 在 chaining、linear probing、quadratic probing 下各自的落點
• 第 26 題｜N 個 key 存在 N 格的 open-addressing 表：找最大 key、找 successor 的最壞複雜度、能否靠選好 hash function 讓最壞搜尋 O(1)、N 個 key 能否存進 N 格
• 第 27 題｜chaining、h(k)=k mod 5，插入 7, 1, 10, 12, 2, 55, 5，問哪些槽有超過兩個 key

排序與 heap（16、20、23、24、25）

• 第 16 題｜用 queue、stack、linked list、array、binary tree 做排序，哪個比較快
• 第 20 題｜binary heap：取最小與取最大的複雜度、n 個隨機整數轉成 max-heap 的複雜度、min-heap 轉 max-heap 的複雜度
• 第 23 題｜insertion sort 的填空：第 6 行缺的那一行；另外判斷它是遞增還是遞減排序、是否為 stable
• 第 24 題｜給 max-heap array [94, 23, 82, 11, 19, 2, 3, 4, 9, 15, 17]，取出最大的 6 個元素後還剩哪些
• 第 25 題｜Wikipedia 版 quicksort（pivot 取最右）：已排序、逆序、全部相同時各自是否 Θ(n²)、partition 的呼叫次數、遞迴深度

資料結構基礎（12–15、17–19）

• 第 12 題｜stack 的 push 與 pop 操作後的內容判斷
• 第 13 題｜stack 與 queue 的實作與性質
• 第 14 題｜linked list：是否為靜態結構、merge sort 的最壞複雜度、改成 circular 需要多久、加上 tail pointer 後合併兩條 linked list 的複雜度
• 第 15 題｜兩條 doubly linked list 的刪除、合併、排序複雜度，以及能否 O(n) 建成 BST
• 第 17 題｜用 doubly linked list 實作 BST 的複雜度
• 第 18 題｜BST 的定義（左子樹小於根、右子樹大於根、子樹也是 BST、樹高一般為多少）
• 第 19 題｜(A+B)*D+E/(F+A*D) 的 prefix 與 postfix 形式，以及 expression tree 高與 prefix、postfix 長度的漸進分析

複雜度與遞迴（11、21、22）

• 第 11 題｜五組漸進等式的判斷，包含 n! = O(nⁿ)
• 第 21 題｜T(n) = 3T(n/2) + n 的漸進界
• 第 22 題｜遞迴函式 sum(n) = sum(n-1) + n 的複雜度

演算法設計與複雜度類（6、31、32、36–40）

• 第 6 題｜哪些圖演算法用 DP（與 110 年第 7 題相同的題目）
• 第 31 題｜Knapsack：fractional 版能否用 greedy、是否有多項式演算法、0-1 版的 O(nW) DP、O(nW) 是否算多項式時間
• 第 32 題｜差限制系統（system of difference constraints）：判斷解的個數與各組 x_i−x_j 的最大值
• 第 36 題｜哪些問題有多項式時間的驗證演算法（即屬於 NP）
• 第 37 題｜MINCUT 的決策版屬於哪些複雜度類（P、NP、co-NP …）
• 第 38 題｜VERTEX-COVER 的決策版屬於哪些複雜度類，以及是否有 2-approximation algorithm
• 第 39 題｜給 10 個問題或演算法，各自屬於 divide and conquer、DP、greedy、其他四類，設四類各有 x、y、z、w 個，再判斷 x+y、y+z 等式
• 第 40 題｜給 10 個問題，各自是 P、NP-hard 或兩者皆非，設三類各有 x、y、z 個，再判斷各種等式

作答時要注意的地方

1. 40 題、12 頁，每題 2.5 分，多選題全對才給分，答錯不倒扣。
2. 第 39、40 題各要先分類十個問題，再比對五個等式。
3. 第 2 題承第 1 題的結果，是先插入 61 再刪除 7。
4. 第 6 題與 110 年第 7 題是相同的題目。

準備方向

• 複雜度類的歸屬（P、NP、co-NP、NP-complete、NP-hard）：111 第 36、37、38 題連續三題，第 40 題又考一次（第 39 題是設計技巧分類）。
• MST 的 cut property、cycle property、light edge：106 第 14 題、111 第 33 題；110 第 13 題則是比較 shortest path 樹與 MST。
• 演算法分類（111 第 39 題）與 DP、greedy 的適用情形（110 第 7、27 題，111 第 6、31 題）。
• 110 與 111 年有重複出題，可以兩年一起看。