電子工程 107 年計算機概論考古題

一個正整數n 的階乘（factorial）函數定義為Factorial(n)= n!=1×2×3×…×n， 並且定義0!=1。（每小題5 分，共25 分） 下列是計算Factorial(n)的一個虛擬碼（pseudocode）。如果我們呼叫 Factorial(6)，那麼這個程式執行到最後"return F"這一行時，F 的值會 等於多少？ 承上題，如果我們呼叫Factorial(6)，那麼這個程式執行到最後"return F" 這一行時，i 的值會等於多少？ 承上題，以上的方法我們將之稱為是一種"iteration solution"，請說明 何謂"iteration solution"？ 階乘函數亦可以遞迴（recursion）方式定義：0!=1，n!= n×(n-1)!。以 下是計算Factorial(n)的一個recursive solution 虛擬碼（pseudocode）。 請說明何謂"recursive solution"？ 承上題，如果n 值很大，計算Factorial(n)的recursive solution 的空間 複雜度（space complexity）為何？ 33650

隨電腦運用的普及與網際網路的蓬勃發展，資訊安全已成為企業及個人不可忽視的 重要課題。然而，安全的電腦系統需具備機密性（confidentiality）、完整性（integrity）、 可用性（availability）、不可否認性（nonrepudiation）等特性。常見的資訊安全措施 則包括備份與復原（backup/recover）、數位簽章（digital signature）、加密/解密 （encryption/decryption）、防火牆（firewall）、入侵偵測系統（intrusion detection system）、代理人伺服器（proxy server）等。試問： 請詳述何謂防火牆？（4 分）入侵偵測系統？（4 分）代理人伺服器？（4 分）前 述三類系統何者非為被動式的阻擋網路攻擊系統？（2 分） 資訊安全措施之備份與復原是否滿足機密性？（3 分）加密/解密是否滿足可用性？ （3 分）（答案為”否”者，須說明其滿足本題目所提及之何種特性）

中央處理器（CPU）的組成元件有那些？請詳述元件名稱及其功能。（20 分）

下圖是將一個10 進位的小數0.125 轉換為2 進位的小數0.001 的過程的示 意圖，其結束條件為「乘上2 後小數部分等於0」。（每小題5 分，共25 分） 如果要將一個10 進位的小數0.6875 轉換為2 進位的小數，請你也同 上圖一樣，繪圖表示這個過程。 如果要將一個10 進位的小數0.3 轉換為2 進位的小數，請你也同上圖 一樣，繪圖表示這個過程。請問會發生什麼困難？ 請問使用IEEE-754 的實數表示法後，會不會有誤差？為什麼？ 上述方法可以推廣轉換到其它進位。如果要將一個10 進位的小數 0.65625 轉換為16 進位的小數，請你也同上圖一樣，繪圖表示這個過程。 上述方法的結束條件若為「乘上2 後小數部分等於0」顯然會造成問 題，請問結束條件應該如何修正？

某電腦採八位元浮點數表示法（floating-point notation）：符號位元（1 個位元）、指數 部分（3 個位元）及假數部分（4 個位元）；格式說明如表(a)。 符號位元（sign bit） 0 表示正、1 表示負 指數（exponential） 採超額/偏移4 表示法（Excess/biased 4 notation）〔如表(b)〕 假數（mantissa） 採以二進位表示法中最左的一個1 開始 填入假數欄的正規化格式（亦即非零數 值的假數欄第一位數必為1） 表(a)浮點表示格式說明 位元圖樣 代表數值 111 110 101 100 011 010 001 000

請詳述編譯器（compiler）將原始程式（source program）轉化為目標程式（object program） 所需的步驟。（20 分）

JPEG 是一種影像壓縮法，它有三個步驟：DCT、Quantization、Lossless Compression，如下圖所示。（每小題5 分，共25 分） JPEG  演算法先將影像切割成較小的圖像區塊"Blocked Image"來一一 處理。請問這個較小的圖像區塊的像素數量是多少？ 請寫出DCT 的英文全名。 第三個步驟稱為Lossless Compression，請問"Lossless"意思為何？ JPEG 的壓縮比率可大可小，請說明其理由。 請說明Quantization 這步驟做了什麼計算。 33650

2 1 0 -1 -2 -3 -4 表(b)超額4 表示法 試問： 下列實際數值（十進制）之浮點表示圖樣各為何？各有無捨棄誤差（round-off error） 現象？（10 分） (a) 3.5 (b)

符記環（token ring）是區域網路（local area network, LAN）常用的通訊協定之一。 請試述符記環的工作原理。（20 分）

下圖顯示典型的作業系統組成的元件。（每小題5 分，共25 分） 何謂作業系統的kernel？ 何謂作業系統的shell？ 有一類型的User Interface，簡稱為GUI，請寫出其英文全名。 Process Manager 是用來管理Process。請問Process 和Job 有何差別？ 在paging system 中，Memory Manager 需處理page fault interrupt。何 謂page fault interrupt？

1

請分別以陣列表示法（array representation）及鏈結表示法（linked representation）來表 示圖一所示之二元樹（binary tree)。（20 分） 圖一 S T U X W

− 下列浮點表示圖樣（pattern）之實際數值（十進制）各為何？（5 分） (a) 11011100 (b) 01001011 下列計算式由左向右運算總和的結果（十進制）各為何？各有無捨棄誤差（round-off error）現象？（10 分） (a) 0.125 + 0.125 + 0.125 + 6.5 (b) 6.5 + 0.125 + 0.125 + 0.125 （請接第二頁） 107年公務人員特種考試警察人員、一般警察人員考試及 107年特種考試交通事業鐵路人員考試試題 70570 全三頁 第二頁 考試別： 鐵路人員考試 等 別： 高員三級考試 類科別： 電力工程、電子工程 科 目： 計算機概論 三、由任務節點及線所構成的工作網路（task network）圖和關鍵路徑法（critical path method）常被用來規劃軟體專案行程。假設某一軟體開發專案預計將於2018/7/1 開 始執行，下表內容是執行該專案之工作行程相關資訊（假設開發過程無任何休假日）。 工作 工作天數 先行工作 A 8 無 B 4 無 C

請詳細解釋下列C 語言程式的執行過程，最後寫出程式的輸出。（20 分） #include <stdio.h> int main() { int i; for (i=0; i<=8; i=i+2) { switch (i) { case 0: printf("0"); break; case 1: printf("1"); break; case 4: printf("4"); case 5: printf("5"); break; case 6: printf("6"); case 7: printf("7"); continue; default : printf("8"); break; } printf("\n"); } return(0); }

A D 1 A E 4 C,D F 6 B G 1 E,F 試問： 請畫出該專案之工作網路圖。（4 分） 專案最早可完成之日期？（4 分） 任務D 最晚需完成之日期？（4 分） 關鍵路徑之重要性為何？（4 分） 該專案之關鍵路徑為何？（4 分） 四、下面電路圖所示之邏輯閘（gate）分別為OR（OR gate）、AND（AND gate）、XOR （exclusive OR gate）、？ gate（NOT_AND, NOT_OR 或NOT_XOR）。 電路圖(a) 電路圖(b) 試問： 請寫出所有能使電路圖(a)之輸出為1（D=1）之輸入組合（A=？、B=？、C=？）。 （10 分） 電路圖(b)之每個方塊代表同一類型之邏輯閘（gate）。請問每個方塊為何種邏輯閘 （NOT_AND、NOT_OR 或NOT_XOR）時，其所有輸入為0（A=B=C=D=0）或 為1（A=B=C=D=1），其輸出（E）將為1？（5 分） （請接第三頁） ？ ？ ？ 107年公務人員特種考試警察人員、一般警察人員考試及 107年特種考試交通事業鐵路人員考試試題 70570 全三頁 第三頁 考試別： 鐵路人員考試 等 別： 高員三級考試 類科別： 電力工程、電子工程 科 目： 計算機概論 （請接背面） 五、某精簡指令集電腦（RISC），其處理器時脈速度（clock rate）為100MHz，各類型 指令（instruction）執行所需之時脈週期（clock cycles）如下表所示。 指令形式 時脈週期 資料轉換 3 輸出輸入 2 整數運算 1 浮點運算 2 流程控制 2 若有一10,000 行指令的程式將於該電腦上執行，該程式包含了四類不同型態指令（資 料轉換、整數運算、浮點運算、流程控制），各類指令行數比例依序分別為（20%、 38%、25%、17%）。 試問： 該程式之CPI（Cycles Per Instruction）、MIPS（Million Instructions Per Second）及 執行（execution time）各為何？（15 分） 請詳述何謂RISC（Reduced Instruction Set Computing）？（5 分）