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

電子計算機資料的表示方式採用2 的補數表示法，如果記憶體內容只 有4 個位元長度，請問可表示的整數範圍為何？又0100+1101 與 0100+0101 的十進位值各為何？（15 分） 請利用NOT，OR，與XOR 邏輯閘設計1 個比較器，其輸入為2 個四 位元A3A2A1A0與B3B2B1B0的邏輯線路，如輸入A3A2A1A0與B3B2B1B0 的值相同，則輸出A = B 為1，否則，輸出A = B 為0，例如，輸入 A3A2A1A0 = 1100，B3B2B1B0 = 1100，則輸出A = B 為1，反之，輸入 A3A2A1A0 = 1100，B3B2B1B0 = 1111，則輸出A = B 為0。（15 分）

匯流排拓樸（bus topology）是一種網路裝置之間的連接方式。請舉例畫 出一個匯流排拓樸，並詳細說明使用匯流排拓樸的優點和缺點。（15 分）

有一部32 位元CPU 的電腦，其處理器（Processor）具有位址匯流排 （Address Bus）30 條，請回答下列問題：（每小題5 分，共30 分） 此處理器可以定址多少記憶體空間？ 用那一個暫存器來儲存下一個指令的位址？ 儲存下一個指令位址的暫存器需要多少位元才合理？ 當此處理器的算術邏輯運算單元（ALU）執行有號數的加法（ADD） 運算時，如何知道發生溢位（Overflow）？ 此處理器的算術邏輯運算單元（ALU）運算時，二進位的負數使用2 補 數表示法來代表，請問十進位的數字 -67 在此處理器中該如何表示成二 進位數字？ 此電腦在處理每一個指令（Instruction）時，第一個階段通常必須由記 憶體取出指令放在CPU 中準備執行，請解釋此動作所代表的行為和 使用的暫存器為何？

下圖顯示作業系統（Operating System）組成的五大元件： 其中的User Interface 主要有兩種類型：command-line interface（如Unix 作業系統所用的）及graphical user interface（如Windows 作業系統所 用的），請問這兩種interface 的主要差別為何？（5 分） 其中的Memory Manager 需針對兩種可能的技術加以管理記憶體： paging 及partitioning，請問這兩種技術的主要差別為何？（5 分） 其中的Process Manager 需針對process 兩個可能的問題加以解決： deadlock 及starvation，請問這兩個問題的主要差別為何？（5 分） 其中的Device Manager 通常會為每一個輸出入裝置準備一個I/O queue，並使用FIFO 或shortest length first 策略來存取輸出入裝置，請 問這兩種策略的主要差別為何？（5 分） 其中的File Manager 通常要處理archiving 及backups 兩種工作，請問 這兩種工作的主要差別為何？（5 分） 26650-26850

在TCP/IP 網際網路協定中，在傳輸層（Transport Layer）的協定有TCP 和UDP。何者可以提供可靠的傳輸（Reliable Transmission）？並試述對 應的設計機制？（15 分）

常用的正負整數表示法包括一補數（1’s complement）、二補數 （2’s complement）及帶符號大小（signed-magnitude)。詳細比較這三種 表示法的優缺點。（15 分）

有一個迷宮（maze）如下圖所示：（每小題10 分，共20 分） 請畫出相對於此迷宮之樹狀圖（Tree Diagram）？ 請用深度優先搜尋法（Depth-First Search）找出迷宮起點（A）到終點 （Q）的路徑？ A F B C D E Q J K G I L H P O M N 起 點 終 點 70470

下圖是Huffman encoding 的一個例子： 請說明其中步驟b 為何是選擇節點B 及C 來合併？（5 分） 請說明最後Code 部分B 的編碼為何是010？（5 分） 這個例子如果原本的A、B、C、D、E 符號各自使用3 個位元來編碼， 則使得整個檔案總容量為300 個位元。請問改用此Huffman encoding 後整個檔案總容量變為多少個位元？（5 分） Huffman encoding 是一種lossless compression method，請問lossless 意思為何？（5 分） Huffman encoding 是一種greedy algorithm，請問如何判別它是greedy algorithm？（5 分）

將資訊加密傳送是網路上防範機密資訊外洩的主要方法，目前兩種通用 的加密技術為對稱加密法（Symmetric Encryption）與非對稱加密法 （Asymmetric Encryption），請試述這兩種加密方法。（10 分） 34150

有一最大堆積（max heap）如下圖，若增加一筆資料33 到此堆積中，則 此堆積的結果為何？請詳細畫出堆積增加資料時的步驟及最後結果。 （15 分）

下列為C 語言的兩個程式，請分別寫出執行後的結果？（每小題10 分， 共20 分）  #include <stdio.h> int main (void) { int a, b, c; int *p; int *q; int *r; a = 60; b = 20; p = &b; q = p; r = &c; p = &a; *q = 8; *r = *p; *r = a + *q +*&c; printf("Result 1: %d %d %d \n", a, b, c); printf("Result 2: %d %d %d \n", *p, *q, *r); return 0; }  #include <stdio.h> int main (void) { int list[15] = { 2,1,2,1,1,2,3,2,1,2,-1,1,0,1,1}; printf("%d \n", list[2]); printf("%d \n", list[list[2]]); printf("%d \n", list[list[2]+list[3]]); printf("%d \n", list[list[list[2]]]); printf("%d \n", list[2]+list[12]); return 0; } 70470

樹（Tree）是一種常見的資料結構，可用來表示階層式（Hierarchical） 的資料集合。下圖是Tree 的一個例子： 此例子中，那個節點是root node？（5 分） 此例子中，那些節點是leaf node？（5 分） 此例子中，節點D 的degree 為何？（5 分） 請列出此例子的preorder traversal 其拜訪節點的順序。（5 分） 請列出此例子的postorder traversal 其拜訪節點的順序。（5 分） 26650-26850

利用陣列來實作堆疊，給予如下C 語言的宣告及建立堆疊（create_stack） 的程式片段：（20 分） #define MAX_STACK 100 typedef int ITEM_TYPE; typedef struct stack_type { ITEM_TYPE items[MAX_STACK]; int top; }STACK_TYPE; void create_stack (STACK_TYPE *stack) { stack -> top = 0; } 在不考慮堆疊滿（Full）及空（Empty）的條件下，請寫出堆疊的push 及 pop 程式片段；push 程式片段係先輸入新資料後，再移動指標; pop 程 式片段係先移動指標後，再取出資料。 void push (STACK_TYPE *stack, ITEM_TYPE new_item) { } void pop (STACK_TYPE *stack, ITEM_TYPE *old_item) { }

某一語言之BNF（Backus-Naur Form）表示法如下： <assignment> ::= <id> = <expr> <expr> ::= <expr> + <expr> | <expr> * <expr> | <digit> <id> ::= A | B | C <digit> ::= 1 | 2 | 3 將此BNF 轉換成語法相等的語法圖（syntax diagram）。（15 分） 20 8 15 35 16 10 19 19 27

請回答下列關於網際網路以及應用上的問題： 在IPv4 的網路位址中可以使用「192.168.1.0/27」來表示一段網路位 址，請問這段網路裡包含的IP 位址範圍為何？通常那一個IP 位址會 用來當網路識別碼（Network ID）使用？通常那一個IP 位址會用來當 該網路的廣播位址使用？（6 分） 資料傳輸的錯誤檢查常見會使用奇同位檢查（Odd Parity Check）或是 偶同位檢查（Even Parity Check），請問此兩種同位檢查的優點和缺 點？（4 分） 請說明何謂URL（Uniform Resource Locator）以及完整的URL 應該 包含那些部分？（10 分）

一般程式設計師在建立一支C++程式的過程通常如下圖所示： 上圖C++程式中"#include <iostream.h>"這一行的作用為何？（5 分） 上圖C++程式中"cin>>"這一個指令的作用為何？（5 分） 上圖Compiler 中有兩個部分Preprocessor 及Translator，請問它們的功 能有何差別？（5 分） 上圖中Linker 的功能為何？（5 分） 在Microsoft Windows 的作業系統中，假設已有一個檔名為test1.exe 的文件，請問這文件對應到上圖中何者？（5 分）

給予一串資料：40，25，35，60，63，55，18，76，請畫出將此串資料 依序建成的二元搜尋樹（Binary Search Tree），之後，如何利用此二元搜 尋樹來進行這些資料由小至大的排序（Sorting）？最後，給予如下二元 樹節點的C 語言宣告，請完成此排序的遞迴程式。（25 分） #include <stdio.h> #include <stdlib.h> struct node{ int data; struct node *left; struct node *right; }; typedef struct node *NODEPTR; void sort (NODEPTR tree) { }

作業系統（operating system）中常見的行程排班程式（process scheduler） 包括長程排班程式（long-term scheduler）和短程排班程式（short-term scheduler）。這兩種排班程式的功能各是什麼？以上那一種排班程式在現 今的作業系統中並非絕對必要？請詳細解釋你的答案。（20 分）

請說明RSA 非對稱式金鑰的加解密演算法如何產生所需的密碼金鑰？ （10 分）

詳細解釋下列Java 語言程式的執行過程，並寫出程式的輸出。（20 分） public class testA { static void multiply(int[] item) { for (int idx = 0; idx < item.length; idx++) item[idx] = item[idx] * 2; } static void add(int value) { value += 1; } public static void main (String[] args) { int[] nums = {1, 3, 5, 7, 9}; add(nums[1]); add(nums[2]); add(nums[3]); multiply(nums); for (int idx = 0; idx < nums.length; idx++) System.out.println(nums[idx]); } }