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

題型與配分

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

作答規定：Part I 同樣明訂「請在答案卷第一頁做表，將答案整理於該表中，否則不予計分」。111、112、113 年連續三年要在答案卷第一頁做表，112、113 年另寫否則不予計分。

Part I 資料結構考點（1–10）

• 第 1 題（3%+2%）｜BST 依序插入 15, 8, 13, 18, 17, 6, 11, 14, 5：(i) 某節點的層數 (ii) 刪除 15 時，用左子樹最大或右子樹最小的哪個 key 替代
• 第 2 題（1%+1%+3%）｜同一組數字 20, 5, 10, 18, 4, 22, 11, 32, 21 分別建成：(i) max heap 時 5 的層數 (ii) min heap 的節點位置 (iii) symmetric min-max heap 的性質
• 第 3 題（2%+3%）｜由 postfix 與 infix traversal 序列重建 binary tree，再問 level-order 與 preorder
• 第 4 題（2%+3%）｜帶權 undirected graph：(i) DFS 與 BFS 的合法 traversal order 判斷 (ii) maximum cost spanning tree 的 degree、成本、邊與路徑長度
• 第 5 題（3%+2%）｜Bloom filter：給三個具體 hash function 與一張 15 格 filter，(i) 判斷插入、刪除、查詢的結果 (ii) 元素數為 5 時，最小化 false positive 的最佳 hash function 個數
• 第 6 題（5%）｜height-based leftist tree（HBLT）刪除最小元素後的結構判斷
• 第 7 題（5%）｜Fibonacci heap 連續操作：decrease key 14 by 5、decrease key 21 by 14、delete key 12、insert 14、delete min，判斷過程中是否發生 cascading cut 與最終的 min tree 個數
• 第 8 題（5%）｜red-black tree 插入 62 後的結果是哪一棵，與 111 第 3 題插入的值相同（都是 62），但兩題的 red-black tree 不同
• 第 9 題（5%）｜B\*-tree（order 4，即 2-3-4 tree）的插入與刪除後各節點的 key
• 第 10 題（5%）｜給一棵 binary trie，問轉換成 Patricia 後哪一個是正確結果

Part II 演算法考點（11–15，各 10 分）

• 第 11 題｜Strassen 的變形：一個矩陣分塊遞迴程序，但 C₂₂ 只呼叫一次，求 T(n) 的緊界 Θ
• 第 12 題｜neural network 包裝的 matrix chain multiplication：n 層 fully connected 網路，各層 neuron 數為 ⟨10, 6, 12, 5, 50, 3⟩，求從 input layer 算到 output layer 的最少乘法次數
• 第 13 題｜寫出 LCS 的 recurrence c[i,j]
• 第 14 題｜以比較與交換為基礎的排序其下界是多少，與 107 第 7 題相同
• 第 15 題｜差限制系統求可行解集合或判定無解，與 111 第 16 題同型

作答時要注意的地方

1. Part I 要在答案卷第一頁做表，否則不予計分。
2. Part I 第 1 至 5 題的配分分成兩個以上的小項。
3. 第 7 題要跑完五個連續操作，後面的操作接在前面的結果上。
4. 第 11 題的 Strassen 變形，C₂₂ 只遞迴呼叫一次。

準備方向

• 冷門樹結構：leftist tree、min-max heap、symmetric min-max heap、Fibonacci heap、B\*-tree、Patricia、trie 家族。
• Bloom filter：109 第 2 題、111 第 4 題、113 第 5 題、115 題組 A。
• Fibonacci heap：111 第 12 題、113 第 7 題。
• 差限制系統：111 第 16 題、113 第 15 題。
• 排序下界：107 第 7 題、113 第 14 題。
• matrix chain multiplication：112 第 12 題、113 第 12 題。
• red-black tree 插入 62：111 第 3 題、113 第 8 題（兩題的樹不同）。