114 成大資工所軟體考點分析

題型與配分

編號 148，系所「電機資訊學院－資訊聯招」，考試科目：程式設計，考試日期 114 年 2 月 10 日第 2 節，全卷 11 頁、18 題、100 分，不可使用計算機。

Part I 首次細分成三種題型：

複選題規則：「每題有五個選項，其中至少有二個是正確答案。」這個提示很有用 —— 只選一個一定錯。

卷面明訂選擇題劃記答案卡、問答題寫答案紙，寫錯地方不予計分。

Part I 資料結構考點

一、單選題（1–4，各 3 分）—— 全部是「讀 C 程式」

• 第 1 題｜環狀佇列的 enqueue／dequeue 實作，追蹤一長串操作後陣列 Q 的內容
• 第 2 題｜給一支 unknownFunction（把下一節點的值複製過來再刪除下一節點），問它對單向串列做了什麼 —— 經典的「刪除指定節點但無法處理尾節點」
• 第 3 題｜operation1 與 operation2 其實是 disjoint set 的 find（含路徑壓縮）與 union，問程式輸出與功能敘述
• 第 4 題｜給 quadratic probing 的 insert 與 delete（刪除用 −2 當墓碑），問四個 search 實作哪一個正確 —— 關鍵是遇到 −2（已刪除）要繼續探測、遇到 −1（從未使用）才能停

二、複選題（5–11，各 4 分）

• 第 5 題｜依序插入 10, 20, 30, 40, 50, 60, 70, 5, 4, 15, 16 到 height-based min leftist tree，判斷結果樹的結構與兩次 delete-min 後的狀態
• 第 6 題｜同一組數字插入 min binomial heap（每次插入都做 pairwise combine），判斷 binomial tree 的最大／最小度數、root list 的內容。第 5、6 題用同一組數字對照兩種 heap，是很好的設計
• 第 7 題｜n 節點樹的通用性質：最大成本生成樹的邊數、AVL 刪除的複雜度、compressed trie 的 key 數是否為 n、紅黑樹根的 rank 上界、BST 樹高是否為 O(log n)（否）
• 第 8 題｜給一棵 AVL 樹，判斷刪除 35／插入 1／刪除 9／連續刪除 35 和 60／連續插入 27, 28, 29 後的平衡因子與重整需求
• 第 9 題｜由 inorder 與 postorder 重建二元樹，再判斷根的平衡因子、樹高、葉節點數、從 B 開始 DFS 後 B 到 O 的最短路徑邊數、level-order 的最後一個元素
• 第 10 題｜紅黑樹的插入與刪除：插入 1 後黑節點數、連續插入 100 和 58 後紅節點數、刪除 42 是否可能降低樹高、刪除後根的 rank
• 第 11 題｜由 adjacency matrix 重建無向圖，判斷 BFS 生成樹的頂點數、某頂點的度數、是否有 articulation point、連通元件數、環的數量

三、問答題（12–13）

• 第 12 題（5%）｜order 4 的 B-tree 依序插入 62, 5, 85, 12 再依序刪除 5, 50, 62, 85, 10，畫出最終的樹
• 第 13 題（5%）｜最大成本生成樹：(a) 1% 總成本 (b) 2% Kruskal 最後選入的邊 (c) 2% 從 a 出發的 Prim 第 5 條選入的邊

Part II 演算法考點（14–18，各 10 分）

第 15–17 題是一個「排課」系列，三題層層遞進：

• 第 14 題｜給一個分群遞迴演算法：把大小 n 的集合分成 |S₁| = |S₂| = √n、|S₃| = n − 2√n 三群，只遞迴 S₁ 與 S₂，分群本身要 Θ(lg n)。求 T(n) 的緊界 Θ
• 第 15 題｜加權區間排程（weighted interval scheduling）：n 堂課各有開始、結束時間與權重，已按結束時間排序並給了 p(j)，要補完遞迴式 F(j) = max(w_j + F(p(j)), F(j−1))
• 第 16 題｜承上，改成沒有時間限制、只有總時長 C，寫出 (n+1)×(C+1) 表格 T[i,j] 的遞迴式 —— 這就是 0-1 knapsack
• 第 17 題｜承上，改成時間無限但要最小化加權完成時間 Σw_if_i。給 15 堂課的時長與權重，求最佳排程的值。這是 Smith 規則：依 p_i/w_i 由小到大排序
• 第 18 題｜補完 Floyd-Warshall 的 d^k 遞推公式（與 110 年第 9(2) 題完全相同）

這份考卷的難點

1. 第 17 題要實際算出 15 堂課的最小加權完成時間。 先按 p_i/w_i 排序，再累加 —— 禁用計算器的情況下計算量非常大，是全卷最耗時的一題。
2. 第 5、6 題的 leftist tree 與 binomial heap 都要對同一組 11 個數字完整建樹，且是複選題。
3. 第 4 題的 quadratic probing search 很細：要分清「−1 從未使用（可停）」與「−2 已刪除（要繼續）」。
4. 第 11 題要從 adjacency matrix 重建圖再判斷 articulation point，是多步驟推理。

準備建議

• 第 15–17 題的排課三連發展示了成大喜歡「同一情境、三種變形」的出題法：加權區間排程 → knapsack → Smith 規則。這三個經典問題建議一起複習
• Smith 規則（依 p_i/w_i 由小到大排）是排程理論的基本結果，很少在資料結構課出現，但成大考了 10 分
• leftist tree 與 binomial heap 對照（114 第 5、6 題）是成大特有的考法，兩種 heap 的合併規則都要熟
• Floyd-Warshall 的遞推式在 110、114 考了兩次填空，務必默寫得出來
• 單選題四題全是讀 C 程式，環狀佇列、單向串列刪除、disjoint set、quadratic probing 的標準實作都要看得懂