刑事警察人員 107 年計算機概論考古題

下圖是使用Cache 裝置的電腦內部示意圖： 請將Registers、Cache、Memory 這三種資料儲存裝置的存取速度，由慢至快列出 來。（4 分） 有人說過“Cache memory is so efficient despite its small size. The answer is due to the 80-20 rule.”，請說明何謂80-20 rule？（4 分） 為何Cache memory 會讓電腦的計算比較有效率？（4 分） 上圖Control Unit 中有一個裝置：PC。請說明PC 的主要用途為何？（4 分） 上圖Control Unit 中有一個裝置：IR。請說明IR 的主要用途為何？（4 分） （請接第二頁） 107年公務人員特種考試警察人員、一般警察人員考試及 107年特種考試交通事業鐵路人員考試試題 全三頁 第二頁 考試別： 一般警察人員考試 等 別： 二等考試 類科別： 刑事警察人員犯罪分析組 科 目： 計算機概論（包括計算機結構、資料結構、程式設計）

下圖是一般電腦其程式（Program）、工作（Job）、程序（Process）之間的狀態轉移圖。 請問“Ready”和“Running”的狀態有何差別？（4 分） 圖中有一句話“Time slot exhausted”，通常一個time slot 是多久？（請寫“介於1 天至1 小時”、“介於1 小時至1 分鐘”、“介於1 分鐘至1 秒鐘”或“少於1 秒鐘”）。（4 分） 圖中有一句話“an interrupt occurred”，請舉出一個會發生interrupt 的例子。（4 分） 請問這個系統是否屬於time sharing 的系統？說明理由。（4 分） 這個系統有可能會發生deadlock，請說明理由。（4 分） （請接第三頁） 107年公務人員特種考試警察人員、一般警察人員考試及 107年特種考試交通事業鐵路人員考試試題 全三頁 第三頁 考試別： 一般警察人員考試 等 別： 二等考試 類科別： 刑事警察人員犯罪分析組 科 目： 計算機概論（包括計算機結構、資料結構、程式設計） （請接背面）

下面為一以C 語言撰寫之副程式，用來解決河內塔（tower of Hanoi）問題。 void tower(int n, char start, char tmp, char end) { if (n==1) { printf("Move disk %d from %c to %c\n", n, start, end); return; } tower(n-1, start, end, tmp); printf("Move disk %d from %c to %c\n", n, start, end); tower(n-1, tmp, start, end); } 何謂河內塔（tower of Hanoi）問題？（4 分） 如果主程式呼叫tower(2, 'A', 'B', 'C')，請問輸出是什麼？（4 分） 如果主程式呼叫tower(8, 'A', 'B', 'C')，請問輸出總共會有多少行？（4 分） 上面tower 副程式中的“if (n==1)”如果改成“if (n==0)”，並且主程式呼叫 tower(8, 'A', 'B', 'C')，請問輸出總共會有多少行？（4 分） 上面tower 副程式屬於遞迴副程式（recursive subroutine）。另有一種型態稱為 coroutine，請說明recursive subroutine 和coroutine 有何差別？（4 分）

我們有各式各樣的問題想使用電腦來解決。而問題依計算的複雜度可分類為 polynomial-time solvable、NP-complete、unsolvable 等類別。 請問travelling salesperson problem 是否屬於NP-complete？（4 分） 請問travelling salesperson problem 是否屬於polynomial-time solvable？（4 分） 請問halting problem 是屬於其中那個類別？（4 分） 請問minimum spanning tree problem 是屬於其中那個類別？（4 分） 為了表達計算的複雜度，我們常使用big-O notation 來表示一個演算法或程式的效 能。何謂big-O notation？（4 分）

請回答下列有關單位的問題。 有一台雷射印表機解析度是1200 DPI，請寫出DPI 的英文全名，並說明1200 DPI 其意義為何？（4 分） 有一台雷射印表機速度是18 PPM，請寫出PPM 的英文全名，並說明18 PPM 其意 義為何？（4 分） 有一支手機螢幕的解析度是458 PPI，請寫出PPI 的英文全名，並說明458 PPI 其 意義為何？（4 分） 有一支手機其相機為1200 萬像素，請問1200 萬像素其意義為何？（4 分） 有一顆CPU 速度是49360 MIPS，請寫出MIPS 的英文全名，並說明49360 MIPS 其意義為何？（4 分）