電力工程 105 年計算機概論考古題

試將十進位數(54.54)10 轉換為二進位數（計算至小數點後六位）。（20 分）

在CPU 中，算術邏輯單元（arithmetic and logic unit, ALU）為一個重要的電路。請回 答下列問題： 請定義ALU 電路相關的四個旗號位元：N（negative）、Z（zero）、V（overflow）、 C（carry）。（8 分） 假設A＝010001112 而B＝010100102 為未帶號數（unsigned number），則A＋B 與 旗號位元N、Z、V、C 的值為何？（6 分） 若設A＝010001112 而B＝010100102 為帶號2 補數（signed 2’s complement number），則A＋B 與旗號位元N、Z、V、C 的值為何？（6 分）

下列C 語言程式碼，讓程式main()執行後將會印出什麼訊息？（10 分） #include <stdio.h> int main(void) { int a[] = {9, 7, 5, 3, 1, 8, 6, 4, 2, 0}; int i, j, z; for (i = 0; i < 9; i++){ for(j = i + 1; j < 9; j++){ if (a[i] > a[j]){ z = a[i]; a[i] = a[j]; a[j] = z; } } } for (i = 0; i < 10; i++) printf("%d", a[i]); return 0; }

試述作業系統中virtual memory working set 的意義及其用途。（10 分）

在當代的計算機系統中，作業系統（例如Windows、Ubuntu、MacOSX）均儲存於硬 碟或是固態硬碟（SSD）中。請說明計算機系統在開機時，如何執行儲存於硬碟中的 作業系統？（15 分）

停止並等待自動重傳請求協定（stop-and-wait ARQ）是相當原始的錯誤糾正協定。請 說明其原則。為了克服停止並等待自動重傳請求協定的缺點，陸續發展了回退N （Go-Back-N）自動重傳請求和選擇重傳（Selective-Repeat）自動重傳請求方法。請 說明這兩種改善方法的差異性。（20 分）

已知一二元樹（binary tree）的前序追蹤（preorder traversal）及中序追蹤（inorder traversal）分別為GECDABFH 和CDEGFBAH，其中A 到H 為此二元樹節點（node） 的名稱。請寫出此二元樹的後序追蹤（postorder traversal）。（20 分）

假設某一個網路分成四個層次（layer）：應用層（application layer）、網路層（network layer）、資料連結層（data-link layer）、物理（實體）層（physical layer）。請說明將一 個使用者的封包由一個主機透過一個路由器（router）傳遞到另外一個主機時，網路 對於該封包的處理情形。（20 分）

范紐曼架構（von Neumann architecture）即儲存程式型電腦，有可能會導致所謂的范 紐曼瓶頸（von Neumann bottleneck）。請說明范紐曼瓶頸的意義，與可行的解決方法。 （15 分）

試寫出下圖的adjacency matrix 及adjacency list。（20 分）

請定義陣列（array）、序列（list）、佇列（queue）、堆疊（stack），並舉例說明。（20 分）

請說明 Big O notation 和 Big Theta notation 的區別。並證明線性函數 f(n) = an+b; a>0，是O(n)。（20 分）

深度優先搜尋法（depth first search）及廣度優先搜尋法（breadth first search）是圖形 中的兩種搜尋法，試說明此二搜尋法的運作過程及此二搜尋法所需用到的資料結 構。（20 分）

結構化程式設計至少應該包含那幾種類型的指述，方能順利完成程式的撰寫？（15 分）

請回答下列問題： 在N 個bits 的有正負之二補數系統裡，可表示的整數範圍為何？另，二補數系統 具有對於加法或減法處理方式相同的優點。其原因為何？（15 分） 針對十進制加法的題目：14+(-5)，使用5 個bits 的二補數（2' complement）之算術 運算改寫，進行加法而得到二補數的和，並討論其結果。（10 分） 針對十進制加法的題目：14+3，使用5 個bits 的二補數（2' complement）之算術運 算改寫，進行加法而得到二補數的和，並討論其結果。（10 分）

試以卡諾圖（Karnaugh map）化簡下列布林式。（10 分） CD B A D ABC D C AB CD AB CD B A D C B A D BC A BCD A D BC A + + + + + + + + a b c d e

在網路上流傳的惡意攻擊程式通常包括：病毒（virus）、蠕蟲（worm）、特洛伊木馬 （Trojan horse）、間諜程式（spyware）。請說明上述四種惡意攻擊程式的意義。（10 分）