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

題型與配分

全卷 7 頁、15 個題組、36 小題、100 分，不可使用計算機，請使用答案卡作答。

計分規則與 108 年相同：同一題組全部小題都對才給該題組的滿分，錯任何一小題整組 0 分。題號旁有 † 記號者，每一小題可能有多個正確答案，必須全選才算對。

逐題考點

• 第 1 題組（†，6%）｜6 節點 8 邊的 connected undirected graph、r 在 G 中 degree 為 5：r 在 DFS tree 中可能的 degree 有哪些、r 是否必為 articulation point
• 第 2 題組（6%）｜k-coloring 的最佳已知複雜度：k = 2、k = 3、k = 4 各是什麼等級
• 第 3 題組（†，13%）｜已知 HamC(G) 可在 O(n⁷) 判定 Hamiltonian cycle，要補完同樣 O(n⁷) 的 HamP2x3 演算法的四個空格，處理從 a₁ 或 a₂ 出發、停在 x₁、x₂、x₃ 之一的路徑問題。四小題全對才給 13 分
• 第 4 題組（†，6%）｜B-tree 的兩組性質判斷：每個節點最多幾個 key、葉的深度是否可不同、根節點是否可能少於 t 個子節點，以及分裂的相關敘述（是否繞 median 分裂、樹高何時增加）
• 第 5 題組（7%）｜給一張 weighted graph：選出正確的 MST、把某一條邊的權重改成 1 後 MST 的最小可能總權重、刪掉某一條邊後 MST 的最大可能總權重
• 第 6 題組（8%）｜有 negative-weight edge 的 directed graph，求 A 到 F 的最低權重路徑，在三種不同限制下各求一次：同一節點最多走兩次、同一節點最多走一次、同一條邊最多走兩次
• 第 7 題組（4%）｜union by rank、path compression、weighted-union heuristic 三者各自的目的是什麼（配對題）
• 第 8 題組（†，6%）｜a_n + b_n√3 = (1+2√3)ⁿ 的遞迴計算：判斷 a、b 的值與 recurrence relation、演算法的最壞複雜度，以及能否用更快的方法完成
• 第 9 題組（†，9%）｜Prefix-Sum 條件的子序列問題：選出最長的子序列使得每一項的前綴和都不超過該項的 6 倍。給輸入 2, 5, 3, 6, 2, 1, 2 求最大 k、判斷一個給定序列的性質，以及選出正確的 DP recurrence D(i,s)
• 第 10 題組（†，5%）｜綜合性質判斷：chaining 的期望搜尋時間、heap 中搜尋某個 key 的複雜度、chaining 能否存超過 m 個 key、AVL 是否為 BST、red-black tree 中有兩個子節點且其一為紅的節點顏色
• 第 11 題組（5%）｜BUBBLESORT 與 HEAPSORT 的最壞複雜度
• 第 12 題組（†，10%）｜雙處理器模組分配：N 個模組各有在處理器 1、2 上的執行成本 a_i、b_i，兩模組分在不同處理器時有通訊成本 c_ij，求總成本最小的分配。三小題分別問給定表格的最佳解 X 的性質、此問題的建模方式，以及可用的演算法
• 第 13 題組（5%）｜max heap 插入 35 後，問 post-order 與 in-order traversal 的輸出
• 第 14 題組（†，5%）｜給一段找 BST successor 的程式碼，判斷執行後 y 與 x 的關係
• 第 15 題組（5%）｜circular doubly linked list 存 3, 4, 5, 9, 7，一段迴圈跑 2019 次 next[next[x]] 再做 prev[prev[prev[x]]]，問最後 value[x]

作答時要注意的地方

1. 第 3 題組 13 分有四小題要全對，第 12 題組 10 分是複選要全選，兩組合計 23 分。
2. 第 6 題組要在三種不同限制下各求一次最低權重路徑。
3. 第 10 題組的 heap 搜尋，問的是 heap 中搜尋某個 key 的複雜度。

準備方向

• Hamiltonian path、cycle 的 reduction 補空格：107、108、109 連三年都考。
• network flow 與 min cut：108 第 12 題組、109 第 12 題組。
• B-tree、AVL、MST：106、108、109 三年都有。
• k-coloring 的複雜度分界、maximum adjacency ordering、scaling max flow 這類進階內容，108、109 都有題組。