110 中央資工所軟體考點分析

題型與配分

科目全名「資料結構與演算法」（所別：資工類），全卷 5 頁、100 分，禁用計算器。

1.5 分是十年來單一選項最重的扣分。 一題五個選項只要錯兩個，這題就從 0 分變成 −3 分。

複選題（1–10）考點

• 第 1 題｜Infix ↔ postfix 轉換，以及轉換過程中 stack 內最多同時有幾個 token
• 第 2 題｜AVL tree — 刪除／插入的重平衡複雜度、高度 h 與 Fibonacci 數的關係、平衡條件 hL − hR
• 第 3 題｜Weight-biased leftist tree (WBLT) — 最右路徑長度上界、子樹高度上界、合併複雜度、max WBLT 的定義
• 第 4 題｜遞迴 — (A) 遞迴版是否一定較慢較耗空間 (B) Collatz 型函式 F1(x)（偶數回傳 x/2，奇數回傳 F1(F1(3x+1))）是否對所有正整數終止 (C) F2 是輾轉相除法，求 F2(21,12) (D) F3(5) 的遞迴求值
• 第 5 題｜二維陣列 arr[5][5] 的指標寫法，哪些等同於 arr[3][2]
• 第 6 題｜給定 PUSH／POP 序列，判斷容器是 stack、queue，還是兩者皆非
• 第 7 題｜Hash table size 17、h(k,i) = (k+i) mod 17（線性探測），刪除 46 之後哪些 key 必須搬位置
• 第 8 題｜QuickSort 的遞迴式 T(n)，分辨哪些對應 worst case、哪些對應 best case
• 第 9 題｜Linked list reverse 的 pseudo-code，判斷兩個空格該填什麼、以及各敘述的描述是否正確
• 第 10 題｜AOE network 以 adjacency list 表示（含 count／end／vertex／dur／link 欄位），求 critical path 總長、判斷某路徑是否為 critical path、求事件 4 的 latest time

問答題（1–2）考點

• 第 1 題（25%）｜NP-completeness，題目先給出四個定義與 Cook's Theorem，然後：
• (A) 15%：已知 SAT ∝ B、B ∝ C、C ∝ D 且 D ∈ NP，證明 D 是 NP-complete
• (B) 5%：判斷「一個 NPC 問題可以多項式歸約到任何 NPC 問題」真假，理由錯就不給分
• (C) 5%：判斷「若某 NPC 問題可用確定性演算法在多項式時間解出，則所有 NP 問題皆然」
• 第 2 題（25%）｜最短路徑
• (A) 12%：給出求 x→y 最短路徑的有效率演算法並分析複雜度
• (B) 13%：給定一個宣稱的距離陣列 d[]，設計 linear time O(|V|+|E|) 演算法驗證這個宣稱是否正確

這份考卷的難點

1. 倒扣 1.5 分／選項是最大陷阱。 複選題佔一半分數，但期望值極差，沒有十足把握的選項不要碰。
2. 第 2(B) 題是全卷最有鑑別度的題目 —— 大多數人會想到重跑一次 Dijkstra，但那不是線性時間。關鍵在於只需驗證每條邊的鬆弛條件。
3. 第 1 題的 (B)(C) 明寫「理由錯就不給分」，不能只寫 True／False。
4. 第 3 題的 WBLT 是課本較少著墨的資料結構，容易失分。

準備建議

• 這一年的複選題大量集中在資料結構的性質判斷（AVL、leftist tree、hash、stack／queue），而不是演算法設計，觀念要精確到選項等級
• AOE network 的 critical path、earliest／latest time 計算務必熟練
• NP-completeness 的證明要能完整寫出「屬於 NP」＋「所有 NP 問題可歸約到它」兩步