程式設計題 (a)search(txt, pat) 追蹤輸出結果
考點：Boyer-Moore 字串比對演算法：Bad Character Heuristic
pattern occurs at 4
pattern occurs at 8
國立臺灣大學資訊管理學系
參考答案 PDF各校參考答案的 PDF，訂閱考試資源分享信後會寄到您的信箱。訂閱領取 PDF
參考答案由作者與 AI 討論後逐題確認，不是各校公布的標準答案；若與各校公布不同，以各校為準。
最後更新：2026 年 11 月 3 日。發現錯誤歡迎來信。
這份考卷每一題的解析與手寫題的答題範例，收在《資管所考古題 111-115 計概資結全解》，可以免費試閱。
| 題號 | 考點主題 | 答案 |
|---|---|---|
| 1 | Von Neumann 架構：四大單元與 Von Neumann Bottleneck | (C) |
| 2 | RISC v.s CISC 比較 | (D) |
| 3 | CPU 內部暫存器與資料流架構圖、I／O 定址模式：Isolated I／O 與 Memory-Mapped I／O、記憶體定址空間計算範例 | (E) |
| 4 | 3 種 I／O 中斷處理方式：Programmed I／O、Interrupt I／O、DMA | (E) |
| 5 | 記憶體階層（Memory Hierarchy） | (C) |
| 6 | OS 四大管理活動總覽：Process／Secondary Storage／Memory／File Management | (D) |
| 7 | Page Memory：分頁式記憶體管理與 Logical／Physical Address | (C) |
| 8 | Virtual Memory 基本概念：定義、優點與行程虛擬位址空間 | (B) |
| 9 | 分散式系統基本概念：定義、三大優點、設計問題與 8 種通透性 | (C) |
| 10 | OS 四大管理活動總覽：Process／Secondary Storage／Memory／File Management | (E) |
| 11 | OS 四大管理活動總覽：Process／Secondary Storage／Memory／File Management | (B) |
| 12 | CPU 排程演算法比較：FCFS、SJF、Priority、RR 與 Multilevel Queue | (D) |
| 13 | Process Memory Layout（Stack／Heap／Data Segment／Code Segment） | (C) |
| 14 | CSMA／CD 與 CSMA／CA 碰撞處理機制、RTS／CTS 解決 Hidden Terminal Problem | (B) |
| 15 | IEEE 802.X 區域網路標準總覽 | (A) |
| 題號 | 考點主題 | 答案 |
|---|---|---|
| 16 | IP 路由與三種路由協定：Link-State、Distance-Vector、Path-Vector | (C) |
| 17 | TCP 三向交握、流量控制與壅塞控制 | (A) |
| 18 | 常見網路攻擊手段整理：Malware（Virus／Trojan／Worm）與其他攻擊手法 | (D) |
| 19 | 程式語言分類：Assembler、Compiler、Interpreter 比較與編譯流程 | (E) |
| 20 | NoSQL 資料庫：CAP 定理、BASE 特性與四種資料模型 | (A) |
| 21 | 關聯式資料庫基本概念：Key 種類與完整性限制 | (E) |
| 22 | 關聯式資料庫基本概念：Key 種類與完整性限制 | (C) |
| 23 | 數位孿生（Digital Twin）概念 | (B) |
| 24 | 區塊鏈（Blockchain）基本概念：Mining 與交易驗證 | (D) |
| 25 | B-tree／2-3 Tree／B+tree 節點度數與高度性質整理 | (B) |
| 26 | Spanning Tree 定義與性質 | (E) |
| 27 | Binary Heap 與 Fibonacci Heap 操作複雜度比較表 | (B) |
| 28 | Binary Heap 與 Fibonacci Heap 操作複雜度比較表 | (C) |
考點：Boyer-Moore 字串比對演算法：Bad Character Heuristic
pattern occurs at 4
pattern occurs at 8
考點：Boyer-Moore 字串比對演算法：Bad Character Heuristic
。程式只用 Bad Character Heuristic；pat 與 txt 皆由同一字元組成時（如全為 A），每次比中後只位移 1 格，約 個起始位置各比對 個字元。
考點：Boyer-Moore 字串比對演算法：Bad Character Heuristic
。pat 的字元都不出現在 txt 時，每次在最右端 mismatch 即位移 格，只需檢查約 個起始位置、每個位置比對 1 個字元。