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

題型與配分

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

科目代號從 110–112 年的 1101 改為 8101，113 年起沿用。

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

Part I 選擇題考點

• 第 1 題組（7%，3 小題）｜用單向串列實作 queue 的 C++ 程式，push 與 pop 各要填三個空格，再追蹤一段 push／pop 序列後 head 與 tail 指向的值。指標操作的細節題
• 第 2 題組（5%，3 小題）｜給一支 C 的排序函式（其實是 quicksort 的 Hoare partition 版）：正確的呼叫方式（陣列索引從 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₁ 下會碰撞、哪些索引最後仍是空的
• 第 4 題組（6%，3 小題）｜Kruskal 求 MST：哪些邊入選、總權重、移除 MST 中權重最小的邊後哪組節點會斷開
• 第 5 題組（5%，2 小題）｜Max-flow 理論與實作：
• 割與流的封閉性（兩個合法割的聯集是否仍為割、兩個可行流相加是否仍可行）、弱對偶方向、Ford-Fulkerson 能否改成多項式時間
• 給殘餘網路，判斷指定路徑是否為合法增廣路徑、給定分割是否為最小割、Edmonds-Karp 會選哪條路徑
• 第 6 題組（9%，2 小題）｜給兩支 C++ 函式 sum(n)（數字和）與 foo(n, target)，問 foo(12321, 7) 的輸出性質，以及這段程式在解什麼問題（答案：找出最小的加數使數字和不超過 target）。這是全卷配分最高的題組
• 第 7 題組（6%，2 小題）｜質數 p 與 Z_p 上的向量映射 b_j = Σ a_i·jⁱ mod p —— 這就是多項式求值／Reed-Solomon 編碼。問每個 b_j 的計算時間、整體複雜度、映射是否一對一、能否由 b 還原 a、以及線性性質
• 第 8 題組（6%，3 小題）｜凸多邊形在給定方向上的極值點：先問凸集與邊界的基本性質，再問區間 [a,b] 是否含極大點的判斷條件，最後檢驗一段二分搜尋 pseudo-code 是否正確、是否一定終止。這是計算幾何的內容，在資工所考卷中很罕見

Part II 非選擇題考點

• 第 1 題（13%，5 小題）｜給 trv1（用 queue，即 level-order）與 trv2（用 stack，即 preorder）兩支走訪函式：
• (A) 3%｜由兩個走訪序列重建二元樹（答案不唯一，寫出一棵即可）
• (B) 3%｜把 "COMPUTERS" 逐字插入空 BST，寫出 preorder
• (C) 2%｜preorder／postorder／inorder／level-order 中，哪一種可以單獨唯一決定一棵 BST
• (D) 3%｜B-tree 節點最多 M 個 key、M+1 個子指標時，各子樹 key 值與 key[] 的大小關係
• (E) 2%｜為了讓深度最小，非根的非葉節點至少要有幾個 key（以 M 表示）
• 第 2 題（13%）｜Bellman-Ford：(A) 4% 補完 pseudo-code 的四個空格（初始化 ∞、源點 0、鬆弛條件、負環判斷條件） (B)(C)(D) 各 3% 在給定的四節點有向圖（含負權邊 A→C = −4）上追蹤 dist[C]、dist[B]、dist[D] 的值
• 第 3 題（14%）｜最長回文雙峰子序列（Longest Palindrome Bimodal Subsequence）。題目先給出 LIS 的標準遞迴式當範例，要你寫出 PV(i)（以位置 i 為峰的最長回文雙峰子序列長度）的正確遞迴式，可以自行定義輔助函式但必須精確簡潔。這是全卷最難的一題
• 第 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. 第 3 題（14 分）的雙峰子序列要同時定義「向左遞增」與「向右遞減」兩個方向的輔助函式，再組合成 PV(i)，是典型的「LIS 雙向版」但敘述抽象。
2. 第 8 題組的計算幾何超出一般資工所範圍，要理解凸多邊形上投影值的單峰性質才能判斷二分搜尋是否正確。
3. 第 4 題的 (A) 不對則 (B) 零分，這種連動計分讓 10 分變成一個賭注。
4. 題組全對制下，第 6 題組（9 分，2 小題）與第 1 題組（7 分，3 小題）風險最高。

準備建議

• LIS 的遞迴式必須默寫到反射，113 年直接拿它當範例再要你推廣；雙向 LIS（bitonic subsequence）是常見變形
• Bellman-Ford 的 pseudo-code 要能逐行默寫（113 第 2 題直接考填空），包含負環偵測那一輪
• B-tree 的 minimum degree 與 key 數下界（113 Part II 第 1(E) 題）是交大 106、108、109、110、113 反覆出現的考點
• 交大近年很愛「給一段程式碼，問它在解什麼問題」（113 第 6 題組、112 第 9 題、107 第 5、6 題），這需要真的讀懂程式而非認關鍵字