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

題型與配分

科目「資料結構與演算法（8101）」，系所班別資訊聯招，考試日期 115 年 2 月 4 日第 1 節，全卷 9 頁、17 題、100 分，不可使用計算機。

這一年的結構和交大過去十年都不一樣，分成四大部分：

兩個十年僅見的規則：

1. 單選題答錯倒扣 1 分 —— 交大 106–114 年都沒有倒扣，115 年首次出現。
2. 第四部分可以寫「PASS」換 1 分 —— 卷面原文：「If you do not know the answer, you have the option to answer "PASS"; in this case, you will receive exact ONE point for that question. Other irrelevant answers to the question make you lose the option. Make good use of the option to maximize your score.」

也就是說 亂寫比誠實認輸更糟。第 17(c) 題有 7 分，不會寫時 PASS 至少保 1 分，硬掰則是 0 分。

一、單選題考點（1–8，各 3 分）

Bellman-Ford（1–3）

• 第 1 題｜給定一張圖與指定的邊鬆弛順序（字典序），問 Bellman-Ford 需要幾個 pass 才收斂、以及 S 到 G 的最短距離
• 第 2 題｜承上圖，若可以自己決定鬆弛順序，收斂所需 pass 數的最小值與最大值各是多少
• 第 3 題｜承上圖，五種鬆弛順序中哪一種讓 pass 數最少

這三題合計 9 分，全繞著「邊的處理順序如何影響 Bellman-Ford 的收斂速度」，是很少見但很有深度的切入點。

邏輯電路圖論化（4–6）

• 第 4 題｜把 4-bit ripple carry adder 的閘級電路當成 DAG，問從任一輸入到任一輸出共有幾條相異路徑（提示：到 S₁ 有 3 條）
• 第 5 題｜同一個電路，critical path 經過幾個閘
• 第 6 題｜求解第 5 題的最快演算法時間複雜度（答案是 O(M+N)，DAG 上的拓撲排序＋DP）

2-SAT（7–8）

• 第 7 題｜五個 2-SAT 的 CNF 式子中，哪一個是可滿足的
• 第 8 題｜關於 2-SAT 的 implication graph：是有向還是無向、頂點與邊數、是否連通、有幾個強連通元件（SCC）、找 SCC 的複雜度

二、簡答題考點（9–11）

• 第 9 題（8%）｜三位學生用同一組數字（10, 20, 30, 15, 25, 35, 45, 12, 22, 32）建出三棵不同的紅黑樹。(a) 6% 逐一判斷是否為合法紅黑樹，答 NO 必須說明理由才給分 (b) 2% 紅黑樹中同一父節點的兩棵子樹深度比最多是多少（答案 2）
• 第 10 題（10%）｜有向圖的拓撲排序：(a) 2% transitive closure 中 1 的個數 (b) 2% 給一個合法的拓撲順序 (c) 2% 把邊 2→5 反向後會發生什麼 (d) 2% 加一條邊 1→3 後會發生什麼 (e) 2% 判斷「選對起點就能用 BFS 得到拓撲順序」這句話的真假，並說明如何選起點或什麼情況會失敗
• 第 11 題（7%）｜無向帶權圖的 MST：(a) 2% Kruskal 第二步與第五步選的邊（兩個都對才給分） (b) 2% Prim 第二步與第五步選的邊（兩個都對才給分） (c) 3% 三小題全對才給分 —— MST 是否唯一、Dijkstra 產生的生成樹是否必為 MST（否）、(a)(b) 得到的 MST 各有幾條邊

三、程式碼除錯題考點（12–14）

這是交大十年來第一次出現的題型，要指出行號並寫出正確的 C 程式碼。

• 第 12 題（5%）｜Binary Search，程式中有 1 個 bug。錯在 arr[mid] < target 時寫成 right = mid - 1，應為 left = mid + 1
• 第 13 題（10%）｜雙向串列程式，有 2 個 bug。一是 insertEnd 少設 newNode->prev = temp；二是 deleteNode 中 free(temp) 寫在讀取 temp->prev／temp->next 之前（use-after-free）
• 第 14 題（10%）｜Min Heap 程式，有 2 個 bug。一是 heapify 裡 int r = rightChild(1) 應為 rightChild(i)；二是 deleteMin 中把最後一個元素搬到根時寫成 heap->arr[1]，應為 heap->arr[heap->size - 1]

題目瑕疵：第 13 題的標題印為「Binary Search Tree」，但題目內容與敘述都是 doubly linked list。作答時以內容為準。

四、非選擇題考點（15–17）

• 第 15 題（4%）｜給一個從 index 1 開始的陣列 11, 5, 10, 2, 9, 3, 8, 4, 7, 6，用 bottom-up 線性時間建堆法建成 binary min-heap，並把結果填回同一個陣列
• 第 16 題（5%）｜已知 Hamiltonian Cycle 是 NP-Complete，問函式 f(G, u, v, k)（判斷 G 中 u 到 v 是否存在長度 k 的路徑）是否 tractable，並論證。關鍵在「path」是否要求簡單路徑，以及 k 是否為輸入的一部分
• 第 17 題（17%）｜二元搜尋樹的 NULL 指標與最近共同祖先：
• (a) 4%｜證明 n 個節點的 BST 中恰有 n+2 個 NULL 指標（含 parent 指標）
• (b) 6%｜給一段「a 走到底就跳到 n2、b 走到底就跳到 n1」的迴圈，問它計算出什麼（答案：n1 與 n2 的最近共同祖先 LCA）
• (c) 7%｜證明這段程式的正確性。核心是兩個指標走過的總步數相同，因此必在 LCA 相遇

這份考卷的難點

1. 程式碼除錯題（25 分）是全新題型。 要在紙上找出 C 程式的 bug 並指出行號，free() 順序、rightChild(1) 這種打字錯誤都要看得出來。
2. 第 17(c) 的正確性證明（7 分）是全卷最需要論證功力的地方 —— 要說明為什麼「走完自己的路徑再走對方的路徑」總長相同。
3. 單選題倒扣 1 分，加上第 1–3 題要實際追蹤 Bellman-Ford 的多輪鬆弛，第 4–5 題要數電路裡的路徑，全都很花時間。
4. PASS 規則是雙面刃。 用得好可以在不會的題目穩拿 1 分，但只要寫了不相關的內容就失去資格。

準備建議

• 程式碼除錯是新趨勢，建議實際動手寫過 binary search、雙向串列、min heap 的標準實作，才能在紙上看出偏差
• Bellman-Ford 的 pass 數與邊順序的關係（115 第 1–3 題）是很少見的考點，核心觀念是「一個 pass 能推進多少層」
• 2-SAT 的 implication graph 與 SCC 解法（Tarjan/Kosaraju）建議補齊，115 第 7、8 題直接考
• LCA 的雙指標解法（LeetCode 160 型）與其正確性證明值得練，第 17 題佔 17 分
• 進考場先看第四部分的 PASS 規則 —— 不會的題目寫 PASS，不要硬掰