112 師大資工所考古題詳解｜軟體考點分析

題型與配分

全卷 6 頁、10 題、100 分，作答於答案卷，卷面沒寫倒扣。卷面注意事項是「請依序在答案卷上作答，並標明題號，不必抄題」與「答案必須寫在指定作答區內，否則依規定扣分」。

逐題考點

• 第 1 題（9%）｜以 array term a[MAX_TERMS] 儲存 sparse matrix 的非零項（依 row-major 順序，a[0] 存行數、列數與非零項個數）：(a) 6% 給定一個 sparse matrix，執行題目給的 transpose() 函式（用 rowTerms[]、startingPos[] 計算位置）後，寫出 rowTerms[]、startingPos[] 與 b[] 的內容 (b) 3% 矩陣為 m×n、有 k 個非零項時，這個 transpose() 的時間複雜度
• 第 2 題（10%）｜在 circular linked list 的前端插入節點的 insertFront(list_pointer *last, list_pointer node)，*last 指向最後一個節點，空 linked list 時為 null：(a) 6% 補完程式中的三個空格 (b) 4% 如何多加一道指令，讓節點改成插在 linked list 的最後
• 第 3 題（6%）｜由 postfix 運算式建構 expression tree 並回傳樹根，運算子都是 binary operation 子，可用 create(V)、Push()、Pop() 與必要的變數，填完 (a) 掃到數字 (b) 掃到運算子 (c) 運算式結束時的步驟
• 第 4 題（9%）｜給 undirected graph G 的帶權 adjacency matrix（10 條邊 E1 到 E10）：(a) 5% 用 Prim 演算法求 MST，在表上標出各邊被選取的順序（從節點 1 開始），沒被選的邊寫「.」 (b) 4% 實作 Kruskal 演算法時，哪些資料結構可以讓演算法更有效率（可複選）：binary search tree、minimum heap、hash table、adjacency matrix、disjoint tree
• 第 5 題（6%）｜依 heap sort 把 array 由小到大排序：(a) 3% 初始調整後的 max-heap (b) 3% 最大的兩個數字換到 a[9] 與 a[8] 之後的 array
• 第 6 題（10%）｜給 undirected graph G2 的 adjacency matrix（頂點從 0 開始編號）：(a) 2% 寫出對應的 adjacency list graph[] (b) 6% 依題目給的 dfnlow() 程式碼執行 dfnlow(0, -1)，寫出 dfn[] 與 low[] (c) 2% 說明如何依據 dfn[] 與 low[] 決定圖的 articulation point
• 第 7 題（10%）｜divide and conquer 演算法通常比暴力演算法有效率。和暴力排序（例如 bubble sort、selection sort）相比，(a) 5% merge sort (b) 5% quicksort 各省略了哪些計算
• 第 8 題（20%）｜LCS：給兩個序列 X 與 Y，找 LCS，例如 ATTGA 與 CCTTAG 的 LCS 長度是 3：
• 第 8(a) 題（5%）｜描述暴力解法並分析時間複雜度
• 第 8(b) 題（5%）｜DP 表 L[i,j] 的 recurrence
• 第 8(c) 題（5%）｜X = ATTGA、Y = CCTTAG，填出 L 表
• 第 8(d) 題（5%）｜LCS 也可以看成 longest simple path 問題（從起點 s 到終點 d 找權重總和最大的路徑），題目給了 X = ATTGA、Y = CCTTAG 對應的圖與邊權。一般的 longest simple path 問題是 NP-complete，說明為什麼這個實例可以在多項式時間內解決
• 第 9 題（15%）｜Huffman code：
• 第 9(a) 題（5%）｜說明為什麼 Huffman 演算法是 greedy 演算法
• 第 9(b) 題（5%）｜字母表 {A, B, C, D, E}，出現機率依序為 0.35、0.1、0.2、0.2、0.15，Huffman 演算法的輸出是什麼
• 第 9(c) 題（5%）｜n 個字元的字母表，Huffman 編碼中碼字的最大可能長度
• 第 10 題（5%）｜最大字元頻率小於最小字元頻率的兩倍時，Huffman 編碼是否比 8-bit 定長碼更有效，並說明理由

作答時要注意的地方

1. 第 1、2、3、6 題是 C 或 pseudo-code 填空與追蹤，第 6(b) 要照題目給的 dfnlow() 程式碼執行。
2. 第 4(a) 要在答案卷上畫出表格，沒被選取的邊寫「.」。
3. 第 4(b) 可複選。
4. 第 8(d) 與第 9(a)、9(c)、第 10 題都要求說明理由。
5. 第 8 題 (a)(b)(c)(d) 各 5 分，第 9 題三小題各 5 分。
6. 第 8(a)(b)(c) 題的架構與 108 年第 4 題相同（暴力解、recurrence、填表）；第 7(a) 題的問法與 109 年第六(b)題相同。

準備方向

• 複雜度分析：112 第 1(b)、8(a) 題；106 第 3(2)、5(2)、6(b) 題、107 第 7(a)(c) 題、108 第 4(a)(b) 題、109 第一(8)、四(c)、六(a)題、110 第 1、2 題、111 第 4、5 題、113 第 8(a)(b) 題、114 第三、五題、115 第 1、5、6 題也有。
• C 程式的填空、追蹤與手寫：112 第 1、2、6 題；106 第 2(1)、3(1)、4(2)、5(1) 題、107 第 1(c)(d) 題、108 第 2 題、110 第 7、8 題、113 第 1–4、6、7、8(c)、11、12 題、114 第一題也有。
• sparse matrix 的表示與 transpose：112 第 1 題；107 第 2(a) 題也有。
• Linked list、stack 與 queue 的實作：112 第 2 題；106 第 2(1) 題、108 第 1.9、2(a) 題、109 第四題、110 第 7 題、113 第 11 題、114 第一題也有。
• binary tree 與 BST：112 第 3 題；107 第 3(a) 題、108 第 1.1、1.8、1.10、1.12 題、109 第一(2)、一(7)、二題、110 第 2(a)、3-5、8 題、111 第 1 題、113 第 8、10 題、114 第三(二)(四)題、115 第 5 題也有。
• Stack 與 queue 的應用（運算式轉換、迷宮、BFS）：112 第 3 題；106 第 2(2) 題、108 第 1.2、1.4 題、109 第三題也有。
• minimum spanning tree（Prim／Kruskal）：112 第 4 題；109 第七題、110 第 10 題、114 第七(一)題也有。
• Heap 與 priority queue：112 第 5 題；106 第 5 題、107 第 3(b) 題、108 第 1.6、1.7 題、109 第一(1)、一(6)、一(9)題、110 第 2(c)(d)、5 題、111 第 4 題、114 第三(三)題、115 第 4 題也有。
• 排序演算法：112 第 5、7 題；106 第 3 題、107 第 1(a)(b) 題、108 第 1.11 題、109 第一(4)、六題、110 第 3-3、3-4、9 題、111 第 2 題、114 第二(二)題、115 第 5 題也有。
• 圖的表示法：112 第 6(a) 題；108 第 1.3 題、109 第一(3)題、110 第 3-1、3-2 題、113 第 9 題、114 第三(一)、四題也有。
• 圖的 traversal 與 connectivity（DFS／BFS、dfn／low、biconnected、strongly connected）：112 第 6 題；106 第 4(1) 題、107 第 2(b) 題、108 第 1.3、1.5、3、5(a) 題、110 第 6 題、111 第 3 題、113 第 9、13(a) 題、114 第四題、115 第 8 題也有。
• DP（rod cutting／knapsack／LCS／matrix chain）：112 第 8 題；106 第 7 題、108 第 4 題、111 第 6 題、115 第 7 題也有。
• Huffman 與最佳合併：112 第 9、10 題；114 第二(一)題、115 第 10 題也有。