電子工程 95 年電子計算機原理考古題

4 8 20 33 14 b 17 11 12 一、一個200MIPS 的CPU 平均執行一個指令所需時間為何？（5 分） 請說明何謂管線（pipeline）？（7 分）假設一個不具管線（pipeline）處理器執行 一指令分五個執行階段且每階段所需時間如後：指令擷取（instruction fetch）： 7ns、指令解碼（instruction decoding）：7ns、執行運算或計算位址：8ns、主記憶 體存取：7ns、結果寫回暫存器：7ns。若以管線對處理器予以改善後（同樣五個 執行階段），每個執行階段需多耗時1ns，若不考慮其他延遲影響，此管線結構 改善技術將使處理器指令執行速率改善多少？（8 分）

請將十進位數121.625 轉換成八進位數。（3 分） 八位元（bits）長度以2 補數（2’s complement）所能表示的最大正數與最小負數 分別為何？（4 分） 請計算兩十六進位數加法ADE + FACF。（以十六進表示結果）（3 分）

請解釋在作業系統行程（process）管理中的死結（deadlock）現象，又發生死結的 條件為何？（10 分）

請說明網路的Link State Routing Protocol 與Distance Vector Routing Protocol。（6 分） 為什麼大部分採用Link State Routing Protocol？（4 分）

請就圖一具權值（weight）的圖（graph）回答下列問題： 以節點a 為起點依廣度優先走訪（Breadth First Search）方法列出走訪的節點（node） 順序，當有多重選擇時再以邊（edge）之權值小者優先。（5 分） 請以Kruskal’s 演算法繪出此圖之最少成本生成樹（minimum cost spanning tree） （5 分） 圖一 95年專門職業及技術人員 高等考試建築師、技師考試暨 普通考試不動產經紀人、地政士考試試題 代號：01260 類 科： 電子工程技師 全一張 （背面） 六、請以時間效能為考量根據，從下列幾種不同的排序法（sorting）中，選擇適合各小 題情況的排序法。（每小題4 分，共20 分） 快速排序法（Quick Sort）、插入排序法（Insertion Sort）、合併排序法（Merge Sort） 、氣泡排序法（Bubble Sort）、堆積排序法（Heap Sort） 擬排序的對象大部分都已依需要的關係排列（例如由小到大）。 擬排序的對象數量大（約數千筆）且大部分未依任何關係排列。 擬排序的對象數量大（約數千筆）且大部分剛好與需要的關係成相反的關係排列 （例如我們需要由小到大，它們卻大部分由大到小）。 擬排序的對象數量小（約一、二十筆）。 排序法的時間效能在最差狀況均為O(n log n)。 七、請說明資料庫中，SQL（Structural Query Language）的下列三種語言的用途：資料定 義語言（Data Definition Language）、資料操作語言（Data Manipulation Language）、 資料控制語言（Data Control Language）。（10 分） 八、請說明並比較將高階程式語言轉換成計算機可執行語言的兩種模式：編譯器 （compiler）、直譯器（Interpreter）。（10 分）