114 成大資工所考古題詳解｜軟體考點分析

題型與配分

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

複選題規則：每題有五個選項，其中至少有二個是正確答案。選擇題劃記答案卡、問答題寫答案紙，寫錯地方不予計分。

Part I 資料結構考點

一、單選題（1–4，各 3 分），都是讀 C 程式：

• 第 1 題｜circular queue 的 enqueue／dequeue 實作，追蹤一長串操作後 array Q 的內容
• 第 2 題｜給一支 unknownFunction（把下一節點的值複製過來再刪除下一節點），問它對 singly linked list 做了什麼
• 第 3 題｜給 operation1 與 operation2 兩支函式，問程式輸出與功能敘述
• 第 4 題｜給 quadratic probing 的 insert 與 delete（刪除用 −2 當墓碑），問四個 search 實作哪一個正確

二、複選題（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 的最大／最小 degree、root list 的內容
• 第 7 題｜n 節點樹的通用性質：最大成本 spanning tree 的邊數、AVL 刪除的複雜度、compressed trie 的 key 數是否為 n、red-black tree 根的 rank 上界、BST 樹高是否為 O(log n)
• 第 8 題｜給一棵 AVL tree，判斷刪除 35／插入 1／刪除 9／連續刪除 35 和 60／連續插入 27, 28, 29 後的 balance factor 與重整需求
• 第 9 題｜由 inorder 與 postorder 重建 binary tree，再判斷根的 balance factor、樹高、葉節點數、從 B 開始 DFS 後 B 到 O 的 shortest path 邊數、level-order 的最後一個元素
• 第 10 題｜red-black tree 的插入與刪除：插入 1 後黑節點數、連續插入 100 和 58 後紅節點數、刪除 42 是否可能降低樹高、刪除後根的 rank
• 第 11 題｜由 adjacency matrix 重建 undirected graph，判斷 BFS spanning tree 的頂點數、某頂點的 degree、是否有 articulation point、connected component 數、cycle 的數量

三、問答題（12–13）：

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

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

• 第 14 題｜給一個分群遞迴演算法：把大小 n 的集合分成 |S₁| = |S₂| = √n、|S₃| = n − 2√n 三群，只遞迴 S₁ 與 S₂，分群本身要 Θ(lg n)，求 T(n) 的緊界 Θ
• 第 15 題｜weighted interval scheduling：n 堂課各有開始、結束時間與權重，已按結束時間排序並給了 p(j)，要補完 recurrence
• 第 16 題｜承第 15 題的排課情境，改成沒有時間限制、只有總時長 C，寫出 (n+1)×(C+1) 表格 T[i,j] 的 recurrence
• 第 17 題｜承第 15 題的排課情境，改成時間無限但要最小化加權完成時間 Σw_if_i，給 15 堂課的時長與權重，求最佳 schedule 的值
• 第 18 題｜補完 Floyd-Warshall 的 d^k 遞推公式，與 110 第 9(2) 題相同

作答時要注意的地方

1. 選擇題劃記答案卡，問答題寫答案紙，寫錯地方不予計分。
2. 複選題每題有五個選項、至少二個是正確答案。
3. 第 17 題要算 15 堂課的最佳 schedule，且不可使用計算機。
4. 第 5、6 題用同一組 11 個數字，分別建 leftist tree 與 binomial heap。

準備方向

• leftist tree 與 binomial heap：114 第 5、6 題，113 第 6 題也考 leftist tree。
• weighted interval scheduling、knapsack 與加權完成時間（114 第 15、16、17 題）。
• Floyd-Warshall 的遞推式：110 第 9 題、114 第 18 題。
• quadratic probing 的 search、delete 實作（114 第 4 題）。
• AVL tree 與 red-black tree 的插入刪除：114 第 8、10 題，112 第 4、5 題。
• 圖的 articulation point 與 connected component：114 第 11 題、115 題組 B。
• 最大成本 spanning tree：113 第 4 題、114 第 13 題。
• B-tree 的插入與刪除（114 第 12 題）。