106 中央資工所考古題詳解｜軟體考點分析

題型與配分

全卷 5 頁、8 題、100 分，禁用計算器，作答於答案卷。沒有選擇題。

逐題考點

• 第 1 題（5%）｜追蹤一段 divide and conquer 求最小值的遞迴程式（array {0,1,2,3,4,5}，min(0,5)），寫出 printf 的完整輸出
• 第 2 題（15%）｜Max heap：(a) 把給定的 binary tree 調整成 max heap (b) 再插入 4 (c) 再刪除 8。三小題各 5 分，都要畫出結果的樹
• 第 3 題（20%）｜BST：(a) 5% 寫出 postorder (b) 5% 插入一個節點後重畫整棵樹 (c) 10% binary tree 存在 array A 中、A[i] 的父節點存在 A[⌊i/2⌋]，補完 preorder 遞迴函式的兩個空格
• 第 4 題（10%）｜Insertion sort 的程式填空，insert 函式中有兩個空格
• 第 5 題（12%）｜已知問題 X 是 NP-complete：(a) 6% 如何利用多項式時間 reduction 證明 Y 是 NP-hard (b) 6% 如何證明 Y 屬於 NP
• 第 6 題（18%）｜給定 BFS 的 pseudo-code（建立只含根節點的 queue、檢查第一個元素是否為目標、取出第一個並把子孫加到 queue 尾端、queue 空了回傳 NIL），改寫成 DFS、hill climbing、best-first search 三種演算法，各 6 分。要求寫出完整的 input、output 和所有步驟
• 第 7 題（10%）｜給定 Dijkstra（DSPA）的 pseudo-code，延伸它使路徑總長同時計入節點權重（節點 w 的權重存在 rw[w]，終點的權重不計入），要求依縮排表示區塊結構，寫出完整的 input、output 和所有步驟
• 第 8 題（10%）｜給定 0/1 knapsack 的 DP 演算法（V[i,w] 以 max 遞迴填表），改寫成解 subset sum 問題：給 n 個值 v₁…v_n 與特殊值 C，判斷是否有子集合總和為 C。要求寫出完整的 input、output 和所有步驟

作答時要注意的地方

1. 第 6、7、8 題都要求寫出完整的 input、output 和所有步驟。
2. 第 7 題終點節點的權重不計入路徑總長，pseudo-code 用縮排表示區塊。
3. 第 5 題要寫出文字論證。

準備方向

• BFS 與 DFS（106 第 6 題），109、112 年也有圖的 traversal。
• Dijkstra 的 pseudo-code 改寫（106 第 7 題），107、108、112、114、115 年也有 shortest path。
• 0/1 knapsack 與 subset sum（106 第 8 題），107 第 19 題、109 第 4 題也有 subset sum 類型。
• Max heap 的建立、插入、刪除（106 第 2 題），107、108、109 也有 heap。
• BST 的 traversal 與插入、array 表示法（106 第 3 題），109 第 3 題也有樹的 array 與 thread。
• Insertion sort（106 第 4 題），107、108、109、110、111 也有排序。
• NP-hard 與 NP-complete 的證明（106 第 5 題），107、109、110、111、112、114、115 也有 NP 理論。