108年 - 108 一般警察特種考試_二等_刑事警察人員犯罪分析組：計算機概論（包括計算機結構、資料結構、程式設計）#77046

科目：計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論) | 年份：108年 | 選擇題數：0 | 申論題數：5

試卷資訊

所屬科目：計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)

選擇題 (0)

申論題 (5)

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

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

三、針對下列的組合語言程式說明：⑴有或沒有管線危害（pipelining hazard）的理由。如果有，可能是那一種危害？（10 分）⑵是否可以利用什麼硬體的方法加速？是否可能完全避免管線的停頓（stall）？（10 分）

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

五、T_N代表一個程式在輸入資料的個數為 N 時的執行時間。已知：請逐步推導出該程式的時間複雜度。（20 分）