電子工程 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）為何？

下圖是將一個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」顯然會造成問 題，請問結束條件應該如何修正？

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

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

− ㈡下列浮點表示圖樣（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年特種考試交通事業鐵路人員考試試題 全三頁 第二頁 考試別： 鐵路人員考試 等 別： 高員三級考試 類科別： 電力工程、電子工程 科 目： 計算機概論 三、由任務節點及線所構成的工作網路（task network）圖和關鍵路徑法（critical path method）常被用來規劃軟體專案行程。假設某一軟體開發專案預計將於2018/7/1 開 始執行，下表內容是執行該專案之工作行程相關資訊（假設開發過程無任何休假日）。 工作 工作天數 先行工作 A 8 無 B 4 無 C

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年特種考試交通事業鐵路人員考試試題 全三頁 第三頁 考試別： 鐵路人員考試 等 別： 高員三級考試 類科別： 電力工程、電子工程 科 目： 計算機概論 （請接背面） 五、某精簡指令集電腦（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 分）