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

題型與配分

全卷 9 頁、17 題、100 分，不可使用計算機。

第四部分卷面原文：「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.」

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

Bellman-Ford（1–3）

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

邏輯電路（4–6）

• 第 4 題｜把 4-bit ripple carry adder 的閘級電路當成 DAG，問從任一輸入到任一輸出共有幾條相異路徑（題目給出到 S₁ 有 3 條）
• 第 5 題｜同一個電路，critical path 經過幾個閘
• 第 6 題｜求解第 5 題的最快演算法時間複雜度

2-SAT（7–8）

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

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

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

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

要指出行號並寫出正確的 C 程式碼。

• 第 12 題（5%）｜Binary Search，程式中有 1 個 bug
• 第 13 題（10%）｜doubly linked list 程式，有 2 個 bug
• 第 14 題（10%）｜Min Heap 程式，有 2 個 bug

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

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

• 第 15 題（4%）｜給一個從 index 1 開始的 array 11, 5, 10, 2, 9, 3, 8, 4, 7, 6, 1，用 bottom-up 線性時間建 heap 法建成 binary min-heap，並把結果填回同一個 array
• 第 16 題（5%）｜已知 Hamiltonian Cycle 是 NP-Complete，問函式 f(G, u, v, k)（判斷 G 中 u 到 v 是否存在長度 k 的路徑）是否 tractable，並論證
• 第 17 題（17%）｜BST 的 NULL pointer 與最近共同祖先：(a) 4% 證明 n 個節點的 BST 中恰有 n+2 個 NULL pointer（含 parent pointer） (b) 6% 給一段「a 走到底就跳到 n2、b 走到底就跳到 n1」的迴圈，問它計算出什麼 (c) 7% 證明這段程式的正確性

作答時要注意的地方

1. 單選題答錯倒扣 1 分，未作答 0 分。
2. 第四部分可以答 PASS 得 1 分，但寫了不相關的內容就失去這個選項。第 17(c) 配分 7 分。
3. 程式碼除錯題 25 分，每題要指出行號並寫出修正。
4. 第 17 題 17 分，是全卷配分最高的一題。

準備方向

• 程式碼除錯：binary search、doubly linked list、min heap 的標準實作（115 第 12–14 題）。
• Bellman-Ford 的 pass 數與邊順序的關係（115 第 1–3 題）。
• 2-SAT 的 implication graph 與 SCC（115 第 7、8 題）。
• BST 的最近共同祖先與正確性證明（115 第 17 題）。