112 台大資工所軟體考點分析

題型與配分

科目「資料結構與演算法」（題號 347、節次 1），全卷 7 頁、16 題、100 分。

計分規則（這一年開始改變）：

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

「每個選項單獨計分」代表不必全對也能拿分，但每猜錯一個選項要用兩個對的選項來補。這和 113 年的規則相似、和 114、115 年的無倒扣完全不同。

選擇題考點（1–14）

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

非選擇題考點（15–16）

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

這份考卷的難點

1. 第 16 題只有 9 分，卻要手動跑完整個 KMP prefix function 並精確計數，而且沒有部分分數。錯一次回退就整題沒分。
2. 第 15 題要求「緊的界」，寫 O(k²n log k) 這種寬鬆上界不給分；學生 B 與 C 的複雜度相同但推導方式不同，兩個都要寫對。
3. 第 12(E) 的「所有邊加同一常數」是最經典的陷阱：邊數不同的路徑增加量不同，最短路徑會改變。
4. 複選題的選項設計都很細。例如第 11 題問 DP 解完後「是否容易得到次佳解」—— 直覺會說是，但實際上 DP 表只保留最佳值，次佳解需要額外結構。

準備建議

• 112 年是台大明顯轉向「考理解與應用場景」的一年：heap 用在哪、DFS 為何優於 BFS、postfix 為何方便 —— 這類題目背複雜度沒有用，要能說出原因
• KMP 的 failure function 必須練到能手算並計數（112 第 16 題、110 第 17 題、111 第 11 題、115 第 8 題）
• 合併 k 條串列的三種解法與複雜度（k²n／kn log k）建議完整推一次，這是 LeetCode 23 的經典題
• 「由哪兩種走訪能還原二元樹」、「所有邊加常數最短路徑會變」這兩個陷阱幾乎每年都有學校考