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

題型與配分

全卷 7 頁、16 題、100 分。

計分規則：

• 第 4、5、7 題為單選題，答對得 5 分，答錯倒扣 1 分，未答 0 分。
• 其餘 11 題為複選題，每個選項單獨計分，選項答對得 1 分，選項答錯倒扣 0.5 分，整題未作答則該題 0 分。

選擇題考點（1–14）

• 第 1 題（複選）｜排序演算法的選用情境：merge sort 的最壞、已排序時 bubble sort 的表現、隨機序列用 quick sort、交換成本很高時的選擇、範圍在 1..n² 時的 radix sort
• 第 2 題（複選）｜給一棵 B+ tree 的圖，找出所有違反 B+ tree 結構的地方
• 第 3 題（複選）｜給七個符號與機率，自己建 Huffman tree，再判斷各符號的碼長是否正確
• 第 4 題（單選）｜binary tree traversal 的最壞空間複雜度：DFS/BFS 與 balanced tree/一般樹共四種組合中有幾個是 O(N)
• 第 5 題（單選）｜把 N 個各含 M 個整數的已排序 array 做 N-way merge 的最壞時間複雜度
• 第 6 題（複選）｜給一棵 binary tree，判斷節點的 successor、是否為 AVL tree、以及刪掉某節點後是否變成 AVL tree
• 第 7 題（單選）｜給若干棵 0/1 binary tree，用 inorder traversal 得到的二進位序列轉十進位當 key，插入長度 11 的 linear probing hash table，問發生幾次 collision
• 第 8 題（複選）｜postfix 記號的優點：不需括號、不需考慮運算子優先序、是否較易閱讀、是否較易由電腦求值、是否比 prefix 簡潔
• 第 9 題（複選）｜八皇后問題為何偏好 DFS 而非 BFS：記憶體效率、可用 stack 實作、較快到達終端狀態等
• 第 10 題（複選）｜heap 的應用場景：串流取前 k 大、串流求 median、PageRank、股市買賣撮合、分子動力學的事件驅動模擬
• 第 11 題（複選）｜DP 的性質：是否都能視為最佳路徑問題、解完是否所有子問題都解了、是否容易得到次佳解、optimal substructure、overlapping subproblems
• 第 12 題（複選）｜shortest path 性質：Dijkstra 能否用於無 negative cycle 的任意 directed graph、heap 的角色、Floyd–Warshall 能否處理負權、是否基於 DP、所有邊加上同一個常數後 shortest path 是否不變
• 第 13 題（複選）｜MST 性質：cycle property、cut property、最小、第二小、第三小的邊是否必在某棵 MST 中
• 第 14 題（複選）｜preorder、inorder、postorder：能否用 stack 做 infix→postfix、postfix→infix，以及由哪兩種 traversal 可以唯一決定一棵 binary tree

非選擇題考點（15–16）

• 第 15 題（21%）｜合併 k 條各長 n 的已排序 linked list，三位學生提出三種做法，要分別分析最壞情況的漸進複雜度（以 k 和 n 表示）。學生 A 每輪掃過 k 個頭節點找最小，學生 B 用 min heap 維護 k 個候選，學生 C 用 divide and conquer 兩兩合併。題目註明只看最終答案、必須完全正確才給分、界必須是緊的
• 第 16 題（9%）｜給 KMP 的 COMPUTE-PREFIX-FUNCTION pseudo-code 與 pattern ABACABACABACABAD，問第 7 行（k = π[k]）被執行幾次

作答時要注意的地方

1. 第 16 題 9 分，要精確計數，沒有部分分數。
2. 第 15 題要求緊的界，過於寬鬆的上界不給分。
3. 複選題每個選項單獨計分，答錯倒扣 0.5 分，是這一年開始的計分方式。113 年規則相似，114、115 年沒有倒扣。

準備方向

• 這一年多題問資料結構的優點與應用場景，例如 heap 用在哪、DFS 為何優於 BFS、postfix 為何方便。
• KMP 的 failure function，112 第 16 題、110 第 17 題、111 第 11 題、115 第 8 題都考。
• 合併 k 條 linked list 的幾種做法與複雜度。
• 由哪兩種 traversal 能還原 binary tree，以及所有邊加常數對 shortest path 的影響，112 年都在複選題出現。