加載中. ..
PDF
108
年公務人員特種考試警察人員、一般警察人員考試及
108
年特種考試交通事業鐵路人員、退除役軍人轉任公務人員考試試題
考 試 別：一般警察人員考試
等 別：二等考試
類 科 別：刑事警察人員犯罪分析組
科 目：計算機概論（包括計算機結構、資料結構、程式設計）
考試時間：2小時 座號：
※注意： 禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號：20260
頁次：1
－
1
一、假設處理器執行某個程式，在沒有任何記憶體停頓（stall）時，每個指
令的平均時脈數（CPI）為 2。已知資料快取（data cache）的 錯 失 率（ miss
rate）為 3%，指令快取（instruction cache）的錯失率為 1%，每一次快
取錯失的懲罰為 100 個時脈週期。假設有 30%的指令需要存取資料記憶
體的內容，相對之下，完全沒有快取錯失的處理器效能會是有快取錯失
時的多少倍？（20 分）
二、假設可以平行執行兩個 10×20 整數矩陣的相加，接著還要循序執行 20
次整數的相加。使用 20 個處理器的時候，相對於只使用一個處理器，
可以得到多大的增速（speedup）？（20 分）
三、針對下列的組合語言程式
sub $3, $4, $5 //暫存器 3 = 暫存器 4 - 暫存器 5
sub $1, $2, $3
說明：
有或沒有管線危害（pipelining hazard）的理由。如果有，可能
是那一種危害？（10 分）
是否可以利用什麼硬體的方法加速？是否可
能完全避免管線的停頓（stall）？（10 分）
四、針對 Quicksort 演算法：
請敘述如何用遞迴的方式來製作（10 分），並
且
說明它的優點和缺點。請涵蓋時間複雜度，以及在什麼情況下會有
很差的效能。（10 分）
五、TN代表一個程式在輸入資料的個數為 N時的執行時間。已知：
T1 = 1
TN = TN-1 + N, N >= 2
請逐步推導出該程式的時間複雜度。（20 分）