刑事警察人員 108 年計算機概論考古題（共 5 題）
資料來源：考選部歷屆試題｜法律人 LawPlayer 整理
https://lawplayer.com/exam/criminal-police/108-computer-science-intro

第 1 題
假設處理器執行某個程式，在沒有任何記憶體停頓（stall）時，每個指
令的平均時脈數（CPI）為2。已知資料快取（data cache）的錯失率（miss
rate）為3%，指令快取（instruction cache）的錯失率為1%，每一次快
取錯失的懲罰為100 個時脈週期。假設有30%的指令需要存取資料記憶
體的內容，相對之下，完全沒有快取錯失的處理器效能會是有快取錯失
時的多少倍？（20 分）

第 2 題
假設可以平行執行兩個10×20 整數矩陣的相加，接著還要循序執行20
次整數的相加。使用20 個處理器的時候，相對於只使用一個處理器，
可以得到多大的增速（speedup）？（20 分）

第 3 題
針對下列的組合語言程式
sub $3, $4, $5    //暫存器3 = 暫存器4 - 暫存器5
sub $1, $2, $3
說明：㈠有或沒有管線危害（pipelining hazard）的理由。如果有，可能
是那一種危害？（10 分）㈡是否可以利用什麼硬體的方法加速？是否可
能完全避免管線的停頓（stall）？（10 分）

第 4 題
針對Quicksort 演算法：㈠請敘述如何用遞迴的方式來製作（10 分），並
且㈡說明它的優點和缺點。請涵蓋時間複雜度，以及在什麼情況下會有
很差的效能。（10 分）

第 5 題
TN 代表一個程式在輸入資料的個數為N 時的執行時間。已知：
T1 = 1
TN = TN-1 + N, N >= 2
請逐步推導出該程式的時間複雜度。（20 分）

題目為考試當年公告版本，實務標準請以現行規範為準。