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

 請畫出NAND 匣（NAND GATE）以及XOR 匣（XOR GATE）的代表圖。（4 分）  請用最少的NAND 匣（只能用NAND 匣）組合出XOR 匣，請畫出電路圖。（6 分）

計算機的內部設計架構，依Flynn 所提出的論述，可分成四類：SISD、SIMD、 MISD 及MIMD。（每小題5 分，共15 分） 請問其中那一種架構最不常見？為什麼？ 大多數計算機內部只含有單一的處理器，應將之歸類為那一種架構？為什麼？ 請寫出SIMD 的英文全名。

如下4 個邏輯線路圖所示，每個線路圖均有兩個輸入值A 和B，及一個輸出值，請在下 列(a)到(f)的六個選項中，選出一個正確敘述各邏輯線路圖的功能。（8 分） (a)到(f)六個選項如下： (a)輸出時均為真 (b)輸出時均為假 (c)A 和B 的值相等↔輸出值為真 (d)A 和B 的值均為假↔輸出值為真 (e)A 和B 的值不等↔輸出值為真 (f)A 和B 的值均為真↔輸出值為真

 在陣列儲存的方法中，有所謂以列為主（column-major）的儲存方式，請說明這 種儲存方式的原理。（5 分）  給定一個2 維陣列：A[0：M , 0：N]，現在要將這個陣列放在主記憶體，每個陣 列占一個記憶體位置。假設A[0,0]放在位置1，請問A[i,j]會放在第幾個位置？ （你必須說明計算的推導過程，只列出公式無法獲得任何分數）（10 分）

internet documents 有三種：static documents dynamic documents active documents。請說明這三者最主要的差別為何？（15 分）

執行下列遞迴（Recursion）程式，並回答下列各題： public class CrazyR { public static void R(int n, int t) { if (n == 0) { StdOut.print(t + " "); return; } R(n-1, 3*t); R(n-1, 3*t+2); R(n-1, 3*t+1); } public static void main(String[] args) { R(2, 0); StdOut.println(); } }  程式執行時會產生那些遞迴呼叫（Recursive call），依執行順序畫出其樹狀結構。（8 分）  程式在執行後依序列出輸出的數字。（4 分）   A B A B A B A B OR OR OR OR AND AND NOT NOT NOT NOT NOT NOT AND output output output output   103年公務人員高等考試三級考試試題 代號： 全一張 （背面） 22750、26550 26650、26750

在網路通訊協定中，有所謂的滑動視窗法(Sliding window protocol)，請說明其工作 原理。（15 分）

作業系統中常發生的一些狀況如下，請說明其發生的原因。（每小題5 分，共 20 分） 死結（dead lock） 飢餓（starvation） 分頁錯誤（page fault） 記憶體外部碎片問題（external fragmentation ）及內部碎片問題（internal fragmentation）

下列圖靈機（Turing Machine）中，H 代表終止狀態，R 代表執行狀態。若圖靈機的記憶帶 （Tape）其讀寫頭（read/write head）每次執行指令前均先向右移一個記憶位置（Cell），下 圖中x:y 代表指令執行時如記憶位置為x，則在執行後記憶位置內容更新為y，若未明示 x:y 內容者，則x=y，試回答下列問題：  若圖靈機的儲存記憶帶的初始內容如下，執行結束後，記憶帶的內容為何？（3 分） 初始記憶帶內容 … # 0 1 1 0 0 1 0 1 0 1 # … 讀寫頭  若圖靈機的儲存記憶帶的初始內容如下，執行結束後，記憶帶的內容為何？（3 分） 初始記憶帶內容 … # 1 0 1 0 1 1 0 0 1 1 # … 讀寫頭  說明此圖靈機的功能為何？（4 分）

 何謂分散式阻斷服務攻擊？（4 分）  請說明其攻擊方式及原理。（6 分）

下圖是某種排序演算法執行的範例。（每小題5 分，共25 分） 請問這個排序演算法的名稱為何？ 此排序演算法在處理n 個資料時，其平均時間複雜度為何？ 此排序演算法在處理n 個資料時，其最壞的時間複雜度為何？ 這個排序演算法採用divide and conquer 的解題策略，請說明如何由上圖看出它是 divide and conquer 的解題策略？ 這個排序演算法並不是一種in-place algorithm，請說明其理由。 已知數列： 排序第一步： 排序第二步： 排序第三步： 排序第四步： 1 0 3 年公務人員特種考試警察人員考試 103年公務人員特種考試一般警察人員考試 103年特種考試交通事業鐵路人員考試試題 全一張 （背面）

電腦作業系統可以有批次作業系統（batch system）與即時作業系統（real-time system）之 分別，請問兩者在作業方式與效能要求上有何差異？有別於單人單工作業系統，多元程式 作業系統（multi-programming OS）允許多個程式以執行的狀態存在記憶體中。請問要達 到有同時執行的效果，需要什麼樣的技術？當有多個程序（process）在同時執行時，需要 有程序排程機制來分配CPU 的時間。在常見的循環配額機制（round robin, RR）與先到先 服務（First Come First Serve, FCFS）機制中，請描述兩種排程機制的運作方式與彼此間的 關係。（每個問題5 分，共15 分）

C 語言的函數支援遞迴呼叫（Recursive Call）：  請說明遞迴呼叫的工作原理。（5 分）  請採用遞迴呼叫的技巧，設計一個可以執行合併排序法（Merge sort）的程式，可 使用虛擬碼或C 語言，需詳細定義將使用的資料結構。（10 分）  請針對67, 33, 77, 88, 41, 12, 38, 5 這8 個數字，逐步說明程式的執行過程。 （5 分）

下圖是RSA public-key cryptosystem 的示意圖。（每小題5 分，共25 分） 請問Plaintext 和Ciphertext 有何不同？ 上圖中Private key 必須隱密地加以保存，請問需由誰隱密地加以保存？ RSA public-key cryptosystem 被歸類為非對稱式密碼系統（asymmetric cryptosystem）， 請問為何是「非對稱式」？ 另外有一類對稱式密碼系統（symmetric cryptosystem），請問它和非對稱式密碼 系統的主要差別在那裡？ RSA public-key cryptosystem 運作時，需先選擇兩個大的質數p 和q，要計算其乘 積N＝p¯q 是很容易的，但是反過來說，有一個計算問題是非常困難的。故 RSA 之安全性取決於這個計算問題之困難度。請問這個困難的計算問題為何？

通訊網路中，何謂一個傳輸通訊協定？OSI 的參考模式，定義了七層通訊協定，除了最上 層的應用層與最底層的實體層之外，請由上而下，分別列出其它五層的名稱。一般的路由器 （router）涵蓋了OSI 通訊協定中，那幾層的功能？網際網路中的領域名稱伺服器（domain name server, DNS）的作用為何？位址解析協定（address resolution protocol, ARP）的作用 又為何？（每個問題3 分，共15 分）

 請說明interrupts、traps 兩者的定義。( 6 分)  請比較兩者之差異。（4 分）

以PC 電腦系統為例，何謂階層式記憶體管理模式？其主要的記憶元件有那些？請逐一說 明其用途。（20 分）

 請列出作業系統中，發生死結（deadlock）的4 個條件。（4 分）  有一條小河，河上方有一條單行橋，橋的左邊有一隻白羊，橋的右邊有一隻黑羊。 兩隻羊同時上橋，在橋的中間相遇，互不相讓，發生死結狀況。請分析這個例子， 如何分別滿足發生死結的4 個條件，你必須針對4 個條件逐一說明。（12 分）

請說明下列技術或服務之意義，您認為它對個人、企業、社會可能帶來的效益與風險為 何？  Social network（6 分）  Cloud computing（7 分）  Big data analysis（7 分） 開始 0:0 0:1 1:1 1:0 #:# #:# R R R H

請說明動態隨機存取記憶體（DRAM），為何需要具備refresh 機制？（4 分）