111 交大資工所軟體考點分析

題型與配分

科目「資料結構與演算法（1101）」，系所班別資訊聯招，考試日期 111 年 2 月 9 日第 1 節，全卷 12 頁、40 題、100 分，不可使用計算機，用答案卡作答。

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

題數是交大十年之最（40 題／12 頁），單題只有 2.5 分，等於每一題的機會成本都很低，但「全對才給分」讓實際得分率往往不高。

逐題考點

平衡樹（1–3、9、28–30）

• 第 1 題｜給一棵 AVL 樹插入 61，判斷插入後的祖先／葉節點／兄弟關係
• 第 2 題｜承上，再刪除 7，判斷結果樹的節點關係。兩題連動，第 1 題錯第 2 題必錯
• 第 3 題｜AVL 的性質：最壞搜尋是否 O(n)、走訪是否 O(log n)（不是，是 O(n)）、插入是否 O(log n)、是否比紅黑樹查詢快
• 第 9 題｜空紅黑樹依序插入 5, 2, 7, 3, 4 後的外部節點數、紅節點數、節點 3 的顏色、旋轉次數
• 第 28 題｜BST 的插入／刪除是否 O(h)、找最大值是否 O(1)、空間是否 O(n)、樹形是否由 key 集合唯一決定（不是，取決於插入順序）
• 第 29 題｜給五棵 BST，對根節點做一次旋轉後樹高可能變高的是哪些
• 第 30 題｜給一棵 AVL 樹，哪些插入或刪除操作會使它失衡

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

• 第 4 題｜用 Kruskal 求 MST，判斷總權重、節點 0 到 7 的路徑、節點 3 的關聯邊權總和、MST 的邊數
• 第 5 題｜給一段 pseudo-code（其實是 Dijkstra），判斷它的功能、複雜度、能否處理負環、能否處理帶權圖
• 第 8 題｜有向帶權圖從 b 出發跑 Dijkstra，判斷各條最短路徑的邊數與總權重
• 第 10 題｜BFS 的處理順序、strongly connected 的定義、BFS 是否用 stack（不是，用 queue）、complete graph 的定義
• 第 33 題｜MST 的 light edge 與 cut property：「在某棵 MST 中」是否等價於「是某個割的 light edge」、唯一 MST 與唯一 light edge 的雙向關係、以及環上最大權邊可移除的性質。五個選項每個都要小心，雙向命題常有一邊不成立
• 第 34 題｜給一張流網路（流量與容量相同），推出 x、y、z、a、b、c 的關係與流值，並判斷是否為最大流
• 第 35 題｜無向圖的 adjacency matrix 性質：是否對稱、列和是否為度數、邊數的計算式、奇數度頂點個數是否為偶數（握手定理）

雜湊（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 的最壞複雜度、能否靠選好雜湊函數讓最壞搜尋 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 是否 O(n)（是）、min-heap 轉 max-heap 是否 O(n)（是）
• 第 23 題｜insertion sort 的填空：第 6 行缺的是 key = arr[i]；另外判斷它是遞增還是遞減排序、是否為 stable。注意程式裡的比較是 arr[j] <= key，這使它變成不穩定且降冪
• 第 24 題｜給 max-heap 陣列 [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 的最壞複雜度、改成環狀需要多久、加上尾指標後合併兩條串列是否 O(1)
• 第 15 題｜兩條雙向串列的刪除、合併、排序複雜度，以及能否 O(n) 建成 BST
• 第 17 題｜用雙向串列實作 BST 的複雜度
• 第 18 題｜BST 的定義（左子樹小於根、右子樹大於根、子樹也是 BST、樹高是否一般為 O(log n)）
• 第 19 題｜(A+B)*D+E/(F+A*D) 的 prefix 與 postfix 形式，以及運算式樹高與前後序長度的漸進分析

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

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

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

• 第 6 題｜哪些圖演算法用 DP（與 110 年第 7 題完全相同的題目）
• 第 31 題｜Knapsack：fractional 版能否用貪婪、是否有多項式演算法、0-1 版的 O(nW) DP、O(nW) 是否算多項式時間（不是，是 pseudo-polynomial）
• 第 32 題｜差限制系統（system of difference constraints）：判斷解的個數與各組 x_i−x_j 的最大值。要轉成約束圖後跑最短路徑
• 第 36 題｜哪些問題有多項式時間的驗證演算法（即屬於 NP）
• 第 37 題｜MINCUT 的決策版屬於哪些複雜度類（P、NP、co-NP …）
• 第 38 題｜VERTEX-COVER 的決策版屬於哪些複雜度類，以及是否有 2-近似演算法
• 第 39 題｜給 10 個問題／演算法，各自屬於分治／DP／貪婪／其他四類，設四類各有 x、y、z、w 個，再判斷 x+y、y+z … 等式
• 第 40 題｜給 10 個問題，各自是 P／NP-hard／兩者皆非，設三類各有 x、y、z 個，再判斷各種等式

這份考卷的難點

1. 第 39、40 題是全卷最花時間的兩題。 各要先把 10 個問題正確分類，再算出總和並比對 5 個等式 —— 任何一個分類錯了，5 個選項的判斷全跟著錯，而且全對才給 2.5 分。
2. 第 33 題的 MST 雙向命題極容易失手。「唯一 MST ⇒ 每個割有唯一 light edge」與其逆命題只有一邊成立。
3. 第 1、2 題連動（先插入 61 再刪除 7），第一步算錯就丟 5 分。
4. 第 23 題的 insertion sort 陷阱：程式用 <= 比較，導致它不但是降冪排序，而且不穩定 —— 和課本標準版的答案相反。

準備建議

• 40 題、12 頁、每題 2.5 分，時間分配比正確率更重要。建議先掃一遍把「一看就會」的題目做完，再回頭處理第 32、39、40 這種要動筆算的
• 複雜度類的歸屬（P、NP、co-NP、NP-complete、NP-hard）在第 36、37、38、40 題連考四題，要能精確說出每個類的定義與包含關係
• MST 的 cut／cycle property、light edge 與 safe edge 的雙向命題是交大反覆考的細節（110 第 13 題、111 第 33 題）
• 交大很愛重複前一年的題目（111 第 6 題與 110 第 7 題一字不差），練考古題時 110 與 111 建議一起看