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

何謂軟體開發生命週期（software development life cycle）？試述之。 （20 分）

圖1 為一個sequential logic circuit，圖中的小圓點表示not 的意思。請 問：當a 值為1、b 的值為0、c 的值為1 時，x 的值為何？請詳述計算 求解過程。（10 分） 圖1：sequential logic circuit

CPU 執行指令（instruction）的一連串過程稱之為機器週期（machinecycle）， 包含擷取（fetch）、解碼（decode）與執行（execute）三個步驟，請詳 細說明這三個步驟分別在電腦的組織單元內作了那些動作？（12 分） 假設有個簡易的機器，它的指令格式是16 bits，其中前4 個bits 是運 算碼（op code），後12 bits 是運算元（operand）。今天執行一個指令 LOAD R M，將記憶體M 的內容載到暫存器R（register），其格式 為LOAD 占前面4 個bits，接下來依序暫存器編號有4 個bits，記憶 體位址有8 bits。請問這個機器最多有幾個暫存器，以及多少記憶體字 元（word）？（4 分）

在無線通訊網路中，常用來傳輸訊號的電磁波（electromagnetic waves） 有那些種類？依據各分類，詳述其特性，如頻譜範圍、應用場景及優缺 點等。（20 分）

以卡諾圖化簡F(W, X, Y, Z) = Π M(1, 3, 9, 11, 12, 14)為最簡和項之積。 （20 分）

請將16 進位的(86E)16 轉換成8 進位。（10 分） 假設某台電腦用二補數的方式將10 進位的-35 儲存在8 個bits 的暫 存器裡頭，請寫出該暫存器裡頭，每個bit 的內容。（10 分）

電腦的作業系統中，記憶體的管理機制之一，是需求分頁（demandpaging）。 這個機制是在多程式的系統（multiprogramming）還是單程式的系統 （monoprogramming）下運作的？為什麼？請詳述你的理由。（10 分） 需求分頁與一般分頁（regular paging）有何不同？試分析彼此間的優 缺點，詳述說明理由。（4 分）

什麼是一次（one-pass）及二次組譯器（two-pass assembler）？並試述其 優缺點。（20 分）

完全符合以下三個條件的二元樹（binary tree）有幾個？請畫出來。 （20 分） 有6 個節點，每個節點均儲存一個英文字母 使用層序走訪（level order traversal）的結果：A B C D E F 使用後序走訪（postorder traversal）的結果：D E B F C A

給定二個大於2 的正整數x 和y，請用程式語言C 或pseudo code 寫出 gcd 函式（function），能以x 和y 為參數，回傳x 和y 的最大公因數。 限定用recursive 函式的方式寫出gcd 函式。（10 分） 限定用「for 迴圈」的方式寫出gcd 函式。（10 分）

已知下面兩部電腦的子網路（subnet）的遮罩（mask）為255.255.255.128。 那麼IP 位址140.116.61.150 與140.116.61.60 的電腦是屬於同一個子 網路的範圍嗎？另外，IP 為140.116.61.150 的電腦，它所在的子網路 的IP 位址範圍是多少？並請陳述你的理由。（10 分） 數位簽章（digital signature）如何保證訊息確認（message authentication） 以及不可否認性（non-repudiation）？請詳細說明它的原理。（10 分） 70460 35450

試述作業系統中的最短工作優先排程演算法（shortest-job-first scheduling algorithm）。它有什麼特性？在現實中為何不適合用於中央處理器排程 （CPU scheduling）？（20 分）

說明下列python 語言程式的執行過程，並寫出程式的輸出。（25 分） num = 80586 ans = [] i = 1 while i < num: i += 1 if num % i == 0: ans.append(i) num /= i while num % i == 0: num /= i print(ans) 34150

如圖2 所示，我們假設當行動台（mobile station）X 正傳輸資料給access point（AP）時，行動台Y 也想傳輸資料給AP。由於Y 偵測不到X 的訊 號，誤以為沒有其它設備在傳送資料，便傳送資料給AP，如此將導致 AP 無法正常接收X 和Y 所傳送的資料。此一現象稱為hidden terminal problem。請問WiFi 的國際標準IEEE 802.11 如何避免hidden terminal problem 的發生？（15 分） 圖2：X正傳輸資料給AP（虛線表示無線設備的訊號傳輸與偵測範圍）

下圖為一個二元表示樹（expression tree），請問它的後置運算式 （postfix expression）是什麼？（10 分） 如果前置運算式（prefix expression）是+3-7*21，請畫出它的二元表示 樹。那這個運算式運算結果又是多少？（數字均為一位元）（10 分）

如圖所示，一電腦系統有甲、乙、丙、丁、戊五個元件，其錯誤率分別 為0.4、0.5、0.6、0.7 及0.8。如果要確認此系統是否正常運作，須逐一 檢測元件的正確性：只要其中有任三個元件正確，則此系統可正常運作； 若有任三個元件損壞，則此系統不能正常運作。假使想要以最少的檢測 元件個數就能判定系統正常與否，則應該最先挑選那一個元件來檢測？ 詳述其理由。（20 分） 甲0.4 乙0.5 丙0.6 丁0.7 戊0.8 輸入 輸出 | 37850

三個區域網路（LAN）連接方式如下圖，其中有八台電腦及兩台橋接器 （bridge）。試述橋接器的功能。若電腦6 需要傳遞資料給電腦1，如何達 成資料傳輸？請詳述工作流程。（15 分） 區域網路1 區域網路2 區域網路3 電腦6 電腦1 橋接器1 橋接器2 電腦2 電腦3 電腦7 電腦8 電腦4 電腦5

圖3 為AVL tree。畫出在圖3 裡頭增加key 值為90 的node 之後的 AVL tree。（註：此時AVL tree 裡頭共有9 個nodes）（10 分） 圖3 為AVL tree。畫出在圖3 裡頭刪除key 值為40 的node 之後的 AVL tree。（註：此時AVL tree 裡頭共有7 個nodes）（10 分） 圖3：AVL tree

寫一個電腦程式或是演算法，輸入k，和k 個整數，N1, N2, …, Nk，以及 一個整數SUM。這個程式或演算法，會檢查這k 個整數的任意兩兩的配 對和，是否存在有一對的和剛好等於SUM。如果有存在一對的配對和等 於SUM，則將其印出；否則，如果所有配對和都不等於SUM，則印出沒 有任何配對和剛好等於SUM。（20 分） 例如：輸入的整數有3，8，13，2，17，18，10 輸入的SUM 是20 則程式會印出如下： （2,18）或（3,17） 輸入的SUM 是29 則程式會印出如下： 沒有任何配對和剛好等於SUM

詳細說明下列Java 語言程式的執行過程，並寫出程式的輸出。（20 分） public class Test { public static void main(String[ ] args) { int [] numbers = {60, 20, 55, 30, 40, 20}; for(int index = 1; index < numbers.length; index++) { int key = numbers[index]; int position = index; while(position>0 && numbers[position - 1] > key) { numbers[position] = numbers[position - 1]; position--; } numbers[position] = key; for(int count = 0; count < numbers.length; count++) System.out.print(numbers[count] + " "); System.out.println(); } } }

解釋下列有關電腦及網路安全的名詞：（每小題5 分，共15 分） 巨集病毒（macro virus） 特洛伊木馬（Trojan horse） 字典攻擊（dictionary attack）

在下列數列（array）資料內，去搜尋35 這筆資料。如果你使用二元搜尋 （binary search）演算法，這個演算法的搜尋過程會是如何？請完整說明 之。（10 分） 3，6，7，9，12，14，18，21，22，31，43