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

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

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 分）

電腦的作業系統中，記憶體的管理機制之一，是需求分頁（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

已知下面兩部電腦的子網路（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

下圖為一個二元表示樹（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

寫一個電腦程式或是演算法，輸入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(); } } }

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