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

題型與配分

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

計分規則：「選擇題每一題組須全答對才計分」，沿用 108、109 年的題組全對制。第 1 題組 7 分（3 小題）、第 6 題組 9 分（2 小題），錯一小題整組歸零。

Part I 選擇題考點

• 第 1 題組（7%，3 小題）｜用 singly linked list 實作 queue 的 C++ 程式，push 與 pop 各要填三個空格，再追蹤一段 push、pop 序列後 head 與 tail 指向的值
• 第 2 題組（5%，3 小題）｜給一支 C 的排序函式：正確的呼叫方式（array 索引從 0 到 9）、計數器 c 的最大值，以及哪一組輸入會造成最多次遞迴呼叫
• 第 3 題組（6%，3 小題）｜Double hashing：h₁(k)=k mod 13、h₂(k)=1+(k mod 11)、表大小 13，插入 80, 69, 99, 16, 73, 30, 41。問 key 30 的落點、哪幾組 key 在 h₁ 下會 collision、哪些索引最後仍是空的
• 第 4 題組（6%，3 小題）｜Kruskal 求 MST：哪些邊入選、總權重、移除 MST 中權重最小的邊後哪組節點會斷開
• 第 5 題組（5%，2 小題）｜Max-flow 理論與實作。第一小題：cut 與 flow 的 closure（兩個合法割的聯集是否仍為割、兩個可行流相加是否仍可行）、weak duality 方向、Ford-Fulkerson 能否改成多項式時間。第二小題：給 residual network，判斷指定路徑是否為合法 augmenting path、給定分割是否為 min cut、Edmonds-Karp 會選哪條路徑
• 第 6 題組（9%，2 小題）｜給兩支 C++ 函式 sum(n)（數字和）與 foo(n, target)，問 foo(12321, 7) 的輸出性質，以及這段程式在解什麼問題。這是全卷配分最高的題組
• 第 7 題組（6%，2 小題）｜質數 p 與 Z_p 上的向量映射 b_j = Σ a_i·jⁱ mod p。問每個 b_j 的計算時間、整體複雜度、映射是否一對一、能否由 b 還原 a，以及線性性質
• 第 8 題組（6%，3 小題）｜凸多邊形在給定方向上的極值點：先問凸集與邊界的基本性質，再問區間 [a,b] 是否含極大點的判斷條件，最後檢驗一段 binary search pseudo-code 是否正確、是否一定終止

Part II 非選擇題考點

• 第 1 題（13%，5 小題）｜給 trv1（用 queue）與 trv2（用 stack）兩支 traversal 函式：(A) 3% 由兩個 traversal 序列重建 binary tree (B) 3% 把 "COMPUTERS" 逐字插入空 BST，寫出 preorder (C) 2% preorder、postorder、inorder、level-order 中，哪一種可以單獨唯一決定一棵 BST (D) 3% B-tree 節點最多 M 個 key、M+1 個 child pointer 時，各子樹 key 值與 key[] 的大小關係 (E) 2% 為了讓深度最小，非根的非葉節點至少要有幾個 key（以 M 表示）
• 第 2 題（13%）｜Bellman-Ford：(A) 4% 補完 pseudo-code 的四個空格（初始化 ∞、源點 0、relaxation 條件、negative cycle 判斷條件） (B)(C)(D) 各 3% 在給定的四節點 directed graph（含 negative-weight edge A→C = −4）上追蹤 dist[C]、dist[B]、dist[D] 的值
• 第 3 題（14%）｜最長回文雙峰子序列（Longest Palindrome Bimodal Subsequence）。題目先給出 LIS 的標準 recurrence 當範例，要寫出 PV(i)（以位置 i 為峰的最長回文雙峰子序列長度）的正確 recurrence，可以自行定義輔助函式，但必須精確簡潔
• 第 4 題（10%）｜給正整數 k 與正實數 a₁…a_k、b₁…b_k（b_i > 1）滿足 Σ a_i/b_i = 1：(A) 5% 證明某個實數 r 存在 (B) 5% 設計有效率的程序求出誤差在 10⁻⁶ 內的 r。題目明訂 (A) 沒答對則 (B) 不給分

作答時要注意的地方

1. 選擇題採題組全對制，第 6 題組 9 分（2 小題）與第 1 題組 7 分（3 小題）配分最高。
2. 非選擇題第 3 題 14 分，題目允許自行定義輔助函式。
3. 非選擇題第 4 題明訂 (A) 沒答對則 (B) 不給分。
4. 第 5 題組第二小題要判斷的是 Edmonds-Karp 會選哪條路徑。

準備方向

• LIS 與其變形（113 第 3 題）。
• Bellman-Ford 的 pseudo-code 與 negative cycle 判斷（113 第 2 題）。
• B-tree 的 minimum degree 與 key 數下界：106、108、109、110、113 都有。
• 給一段程式碼問它在解什麼問題：113 第 6 題組、112 第 9 題、107 第 5、6 題。