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

你只能利用基本的三種邏輯閘AND、OR、NOT，設計出一個1-bit 的 比較器（comparator）線路，這個比較器有兩個1-bit 的輸入a 與b，一 個輸出c，當a>b 時，輸出c 的值為1，否則輸出c 的值為0。（10 分） 在電腦的數字系統中，假設使用4-bit 的二補數（2’s complement）方 式來儲存整數，則計算1+7 之後的結果是多少？請詳述你的計算過程， 並解釋你的理由。（10 分）

計算機由記憶體、中央處理單元、輸出入子系統等組成，請回答下列 問題： 說明暫存器（Register）、程式計數器（Program Counter）之功用以及使 用快取記憶體（Cache Memory）之目的。（15 分） 說明工作排程器（Job Scheduler）與行程排程器（Process Scheduler） 有何差異？（10 分）

請將十進位的14.625 轉換成二進位。（5 分） 請將十進位的負整數-179 轉成16-bit 的二補數（2’s complement）的二 進位整數。（5 分） 下列整數都是以十六進位方式表示的16-bit 的二補數整數，請計算 (712A)16+(9E00)16 的結果，並以十六進位方式表示其結果。（5 分） 下列整數是8-bit 的二補數整數，那幾個式子計算結果是整數溢位 （overflow）？並請說明之。（5 分） (i) 11000010 + 00111111 (ii) 00000010 + 00111111 (iii) 11000010 + 11111111 (iV) 10000010 + 10000000

Scheme 是一種函式程式語言（functional programming language），其中定 義了一個函式如下： (define (mystery input-list) (cond ((null？ input-list) 0) (else ( + 1 (mystery (cdr input-list)))))) 執行下列函式的呼叫，結果為何？（5 分） (mystery (list 4 5 6)) 解釋這個mystery 函式，在計算什麼？（5 分） 用Scheme 語法，定義出一個函式factorial n，這個函式要算出n!。（10 分）

有關無線網路與網路協定，請回答下列問題： 依其定義、標準、傳輸距離，說明WLAN（Wireless Local Area Network） 與WPAN（Wireless Personal Area Network）之差異？（15 分） 假設一個系統使用五層協定，如果應用程式創建一個100 bytes 的 訊息，每層（包括第五層和第一層）添加一個10 bytes 的header 到 資料單元，則該系統的傳輸效率（Transmission Efficiency）是多少？ （10 分）

寫一個演算法，輸入資料為有k 個整數值N1, N2,…Nk 的陣列N，以及一 個特別的值SUM。這個演算法找出陣列N 裡的一對整數，其加總的和剛 好等於SUM，並把這一對整數列印出來，如果都沒有這樣的一對整數， 則列印出“抱歉，找不到”。（20 分） 例如：陣列N 裡的數值為3、8、13、2、17、18、10。 且如果(i)SUM 的值是20，則你的演算法要印出：(2、18)或(3、17)。 但如果(ii)SUM 的值是29，則你的演算法要印出：抱歉，找不到。 37150

電腦的作業系統使用虛擬記憶體來管理記憶體，假設每個分頁（page） 大小為4 KB，總共有邏輯位址（logical address）空間共256 分頁，而 此電腦的實體記憶體總共只有64 框（frame）。則此電腦的邏輯位址、 實體位址（physical address）分別是多少bits？（10 分） 假設使用只有三個分頁框（frame）的需求分頁法（demand paging）機 制，且使用LRU（Least Recently Used）取代演算法，則下列分頁參考 （page reference）的順序7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1 會導致多少次的分頁錯誤（page fault），詳述說明整個過程。假設一開 始的分頁表（page table）內容是空的。（10 分） 34750

有關多程式（Multi-Programming）記憶體管理，請回答下列問題： 說明何謂Swapping 以及Non-Swapping 記憶體管理方法？分頁 （Paging）是屬於那種管理方式？（15 分） 假設某作業系統採用分頁記憶體管理，可用記憶體100 MB，分割成 25 個頁框（Frame）。今有3 個程式請求執行：程式A 需要21 MB、 程式B 需要27 MB、程式C 需要38 MB。則三個程式總共使用了幾 個頁框？未被使用頁框的比率是多少？（10 分） 70560 35550 35650

假設在時間0 的時候，行程（process）P1，P2，P3，P4，P5，依序進來系 統。其需要的CPU 處理時間（burst time）和優先權（priority）的資訊如 下表： Process Burst time priority P1 10 3 P2 1 1 P3 2 3 P4 1

一個無階級（classless）IP 位址為167.188.170.83/27，它所屬的子網域 （subnet）範圍為多少？（10 分） 在一個區域網路內，多個使用者共用同一個通道（channel），使用下列 那些媒介存取控制（Medium Access Control）協定，會讓當使用者站 台數目很多時，因為通道碰撞（collision）嚴重，而使得系統的吞吐量 驟降，甚至癱瘓掉？解釋原因。（10 分） ⑴ALOHA ⑵CSMA/CD ⑶CSMA/CA ⑷TDMA

請回答以下Python 程式設計問題： 說明下列程式一的功用為何？（7 分） 執行程式一，且輸入整數8，則輸出的結果為何？（6 分） 執行程式二，則輸出的結果為何？（6 分） 執行程式三，則輸出的結果為何？（6 分） 01 02 03 04 05 06 07 08 09 10 11 12 def theNum(n): if n == 1: result = 1 else: result = theNum(n - 1) + n return result a=int(input()) print(theNum(a)) 01 02 03 04 05 06 07 08 09 10 11 12 def main(): x=3 print(x) f() print(x) def f(): x=8 print(x) main() 01 02 03 04 05 06 07 08 09 10 11 12 def f(num): num = num + 5 return num num = 2 print(f(num)) print(num) 程式一 程式二 程式三

P5

下列式子是用後序（postfix）表示式，計算出它的答案。（5 分） 2 3 4 + * 5 + 假設一個二元樹的走訪（binary tree traversal），用後序走訪（postorder） 得到的是HGDBFECA，用中序走訪（inorder）的結果是HDGBACFE， 畫出這個二元樹。（15 分）

2 分別使用FCFS、SJF、nonpreemptive priority（數字小代表優先權高）、 RR（quantum 為1）的排程演算法，詳細畫出甘特圖（Gantt chart）表示執 行這些行程所需時間。每單位時間執行那個行程必須標示清楚。（20 分） 四、志銘跟春嬌是很好的朋友，有邀約的話一定會欣然赴約。現在志銘 想要跟春嬌約會，因為沒有網路，所以用傳統寫信的方式，寄給春 嬌跟她約定約會的時間與地點。但因為傳統寄信的方式，可能因為 某些因素，信件沒有送達或延遲很久時間才送達。那麼請問志銘如 果按照他定的時間地點準時赴約，春嬌一定會去嗎？會或不會，都 請解釋原因。（10 分） 那如果春嬌收到信後，回確認信給志銘說會準時赴約，那請問春嬌按 約定時間到達約會地點時，她能確定志銘一定會在那邊嗎？會或不 會，都請解釋原因。（5 分） 繼上述，那如果志銘有收到春嬌的確認信後，再回信說，讚，我一定 會去的。請問那這次，兩個人都會確定對方一定會準時到現場赴約 嗎？請分析各種可能性。（5 分） 37150 五、假設我們使用多表置換密碼（polyalphabetic ciphers）機制來加密資料。 這個機制需有個密鑰串（key stream）K = (K1,K2,K3,…)，將我們的明文 （Plaintext）P = P1P2P3…的每個字母，依序加上key 值，轉換成新的字母， 變成密文（Ciphertext）C = C1C2C3…。也就是： 加密機制為Ci = (Pi + Ki) mod 26 解密機制為Pi = (Ci – Ki) mod 26 其中，英文字母與數字的轉換如下表，並以module 26 來計算（除以26 的餘數）。 假設我們使用的密鑰串為：12, 00, 19, 19, 00, 02, 10, 08, 18, 19. 那麼收到的密文是EUVVEUCNME 請問原來的明文是什麼？（20 分）