電子計算機原理考古題｜歷屆國考試題彙整

試述編譯器（compiler）如何將高階語言程式翻譯為機器語言程式。 （20 分）

試述二分搜尋法（binary search）的工作原理，並舉例說明以及分析此搜 尋演算法的效能。（20 分）

以卡諾圖化簡F (W, X, Y, Z) = Σm (0, 2, 5, 7, 8, 10, 12)為最簡積項之和。 （20 分）

作業系統中的程序間通訊（interprocess communication）有兩種模式，試 述這兩種模式的工作原理。（20 分）

試述快速排序法（quick sort）的工作原理，並舉例說明以及分析此排序 法的效能。（20 分）

控制器（controller）是負責電腦與周邊設備（例如印表機、網路卡等） 之間通訊（communication）的元件；當控制器以直接記憶體存取（Direct Memory Access；DMA）方式運作時，可以直接與主記憶體（main memory） 進行資料交換，而不需要依賴中央處理器（CPU）。試解釋為何直接記憶 體存取（DMA）對電腦效能（performance）是重要的技術？但同時也會 加劇馮紐曼瓶頸（von Neumann bottleneck）？（25 分）

CSMA/CD（載波感測多重存取/碰撞偵測）和CSMA/CA（載波感測多重 存取/碰撞避免）是兩種常見的網路協定（protocol）。CSMA/CD 以偵測碰 撞是否發生並解決碰撞問題來提高網路效率；CSMA/CA 則採用避免碰撞 的方式，在傳輸前透過等待退避和頻道偵測來減少碰撞的機率。試分析為 什麼在無線網路環境中，CSMA/CA 相較於CSMA/CD 是更適合的通訊 協定？（建議的分析面向包括：技術可行性、網路效能，隱藏節點問題 等等）（25 分）

泡泡排序（Bubble Sort）是一種排序演算法，透過逐步交換相鄰元素將 序列按大小順序排列。試比較與評論下列兩個版本的泡泡排序程式（in Python）。（25 分） def bubble_sort_v1(arr): n = len(arr) for i in range(n): for j in range(n - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] def bubble_sort_v2(arr): n = len(arr) for i in range(n): swapped = False for j in range(n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True if not swapped: break char toHexDigit(int num) { if (num < 10) return '0' + num; else return 'A' + (num - 10); } void printHexFromBinary(int num) { int leading_zero_found = 0; unsigned int mask = 0xF0000000; int shift_amount = (sizeof(int) * 8) - 4; printf("0x"); for (int i = 0; i < sizeof(int) * 8 / 4; i++) { int hex_digit = (num & mask) >> shift_amount; if (hex_digit != 0 || leading_zero_found){ leading_zero_found = 1; printf("%c", toHexDigit(hex_digit));} mask >>= 4; shift_amount -= 4; } if (!leading_zero_found) printf("0"); printf("\n"); }

下列是一個C 語言的函式（printHexFromBinary）和一個輔助的小函式 （toHexDigit），若呼叫此函式（printHexFromBinary）時傳入一個正整數， 則函式執行完畢會傳回此正整數的十六進位表示法。試論述此函式 （printHexFromBinary）如何完成上述的轉換功能。（25 分）

L

M 2 P 5 Q 6 S

T 2 X 1 請完成以下矩陣相乘函式的指令。（10 分） Void Matrix_Multiplication(A, B, C, m, p, n){ for (i=0; i<m; i++){ for (j=0; j<p; j++){  for(k = 0; k < n; k++){ C[i][j] =  +  ; } printf("%d ", C[i][j]); } printf("\n"); }

假設下列的數字都是二進位的正數。（註：C 是有小數點的數字） A=(1011)2，B=(1111)2，C=(1011.1011)2 求A×B+C的結果並列出計算過程，結果用十進位表示。（20分）

(1011)　(1111) 20 分

在作業系統中，當一個行程（Process）執行時，它會改變狀態（State）， 常見的狀態有5 種：新建（new）、就緒（ready）、執行（running）、等待 （waiting）、結束（terminated）。請繪製行程狀態轉換圖（State Transition Diagram）表示這些狀態以及改變狀態的事件，並說明這些狀態與改變狀 態的事件。（20 分）

某個網際網路協定第四版（IPv4, Internet Protocol Version 4）的位址以二 進位表示如下： 10100011 00011001 00010001 00011110，回答下列問題並列出計算推導 過程。 它的十進位位址表示為何？（5 分） 它的位址用封包側錄軟體上看到的十六進位表示為何？（5 分） 一個IPv4 位址由網路編號（Network ID）和主機編號（Host ID）所組 成，若它的子網路遮罩（Subnet Mask）為255.255.255.0，則表示網路 編號的長度有幾個位元？（5 分） 承上題，它的子網路廣播位址（Subnet Broadcast Address）的十進位表 示為何？（5 分）

底下的C 語言程式的函式size 採用遞迴（recursive）呼叫的方式來算 出二元樹裡總共有幾個節點。struct node 是節點的定義，主程式main 傳給函式size 的參數是指向根節點（root node）的指標。 /*二元樹的節點有三個欄位：data 欄位，分別指向左、右兒子節點的 指標欄位*/ struct node { int data; struct node* left; struct node* right; }; int size (struct node* ptr) { if (ptr == NULL) return ___(a)____; else return _______(b)________; } 為了讓函式size 能夠運作正常，請寫出程式片段(a)和(b)。（a 和b 各5 分） 如果二元樹裡的節點總共有n 個，(c)請算出函式size 總共會被呼叫幾 次？（包含主程式main 呼叫函式size 那一次），(d)請敘述被呼叫次數 是如何計算出來的。（c 和d 各5 分）

有一棵二元搜尋樹（binary search tree）如下，其中圓圈內的數字代表節 點（node）的資料，請對下列問題先敘述作法後，再寫答案： 將此棵樹的節點資料用後序走訪（post-order traversal）的順序寫出。 （5 分） 畫出將資料15, 17 依序插入原本這棵樹後的二元搜尋樹。（5 分） 畫出原本這棵樹的每個節點（node）之左、右兒子（children）節點都 對調（swap）的二元樹。（5 分） 將上題所得到的二元樹裡的節點資料用中序走訪（in-order traversal） 的順序寫出。（5 分） 25 7 32 2 19 26 56

A= (9C7D)16，B = (1001011101101)2，C = (75432)8。求A、B、C 三數的 總和並將結果用八進位表示。（20 分）

(1001011101101)　(75432) 20 分

乙太網路（Ethernet）使用的媒體存取控制協定（medium access control protocol）為何？請詳述其工作方法。（20 分）

某一作業系統之CPU 排程使用循環分配方法（round-robin scheduling）， 每次程序使用CPU 的時間配額（time quantum）為5 毫秒。若今有一排 程，共有四個程序P1、P2、P3 及P4，其到達時間與執行時間如下表所 示。請問在此排程中，每個程序的總等待時間分別為何？請畫出甘特圖 （Gant chart）及詳列計算過程。（20 分） 程序 到達時間 所需執行時間 P1 0 8 P2 2 7 P3 7 5 P4 9 7 註：時間單位為毫秒。

有一最大堆積（max heap）如下圖，若將根節點刪除，則此堆積如何重 建？請詳細畫出重建堆積的過程及最後結果。依據重建的執行效率與正 確性給分。（20 分） 30 21 27 20 10 3 16 12 8

寫出下列C 語言程式的輸出，並詳細解釋程式的執行流程。（20 分） #include <stdio.h> int main() { int i; for (i=0; i<=10; i++) { if (i==0) i=i+1; if (i%2==0) printf("%d\n", i); if (i/3==2) i=i+2; else i=i+1; printf("%d\n", i); } return(0); }

(0)

109年專門職業及技術人員高等考試建築師、32類科技師 （含第二次食品技師）、大地工程技師考試分階段考試 （第二階段考試）暨普通考試不動產經紀人、記帳士考試、 109年第二次專門職業及技術人員特種考試驗光人員考試試題 等 別：高等考試 類 科：電子工程技師 科 目：電子計算機原理 考試時間：2小時 座號： 不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。 本科目除專門名詞或數理公式外，應使用本國文字作答。 若一個八進位數字其值為23456，則等值的十進位、二進位及十六進位數 字分別是多少？（15分） 電腦系統的輔助記憶體單元（auxiliary storage unit）常使用那兩種資料存 取（data access）方式？舉例並詳細說明其工作特性。（15分） 作業系統中的死結（deadlock）是什麼意思？請舉例說明並列出發生死結 的四個必要條件（necessary condition）。（15分） 使用基數排序法（radix sort）將以下數列由小到大排序。詳細敘述並完 整寫出排序的過程。（15分） 101, 23, 945, 712, 500, 9, 28, 654, 166, 111 試述水桶排序（bucket sort）演算法的工作原理、流程與排序效率。（20分） 詳細說明下列Java 語言程式的執行過程，並寫出程式的輸出。（20分） public class Name{ public String name; public int age; public Name(String name, int age){ this.name = name; this.age = age; } public static void x1(Name n1, Name n2){ n2.age = n1.age; n1.name = n2.name; } public Name x2(String name){ Name p1 = new Name(this.name, 30); this.name = name; return p1; } public void x2(Name p, String name){ p.name = name; this.age = p.age; name = "Cindy"; } } public class Main{ public static void main(String args[]){ Name p1 = new Name("Mary", 10); Name p2 = new Name("Ann", 20); Name p3 = new Name("Sara", 60); Name.x1(p2, p1); p2 = p3.x2("Jill"); p3.x2(p1, "Linda"); p1.x2(p1.x2("Wendy"), p2.name); System.out.println(p1.name + " " + p1.age); System.out.println(p2.name + " " + p2.age); System.out.println(p3.name + " " + p3.age); } } Name.java Main.java

以下是一個演算法，給定一個含有n 個數字元素的陣列A[1]～A[n]， 它會輸出其中最大的元素：（每小題5 分，共25 分） Algorithm arrayMax(A, n) 1 currentMax ←A[1]

for i ←2 to n do

if A[i] >= currentMax then

currentMax ←A[i]

return currentMax 此演算法若使用C 或C++程式語言來實作，請問其中「←」應該用什 麼符號來表示？ 給定一個含有n = 8 個數字元素的陣列A = < 8, 22, 22, 13, 34, 3, 34, 13>， 請問最後會輸出currentMax 的值為何？ 給定一個含有n = 8 個數字元素的陣列A = < 8, 22, 22, 13, 34, 3, 34, 13>， 請問此演算法的第3 行指令「if A[i] >= currentMax then」總共被執行 了多少次？ 給定一個含有n = 8 個數字元素的陣列A = < 8, 22, 22, 13, 34, 3, 34, 13>， 請問此演算法的第4 行指令「currentMax ←A[i]」總共被執行了多少次？ 此演算法處理一個含有n 個數字元素的陣列時，其執行時間T(n)的複 雜度（time complexity）為何？ 二、下圖可用來表示程式執 n、log2n 等6 種函數。 請問其中那些函數是 傳統的Merge sort 在 種？ 傳統的Quick sort 在 是這6 種的那一種？ 傳統的Selection sor 一種？ 傳統的Heap sort 在 種？ f(n) 0 40 30 20 10 執行時間f(n)的成長圖。其中有 。（每小題5 分，共25 分） 是屬於polynomial-time growth？ 在排序n 個資料時，其時間複雜度 在排序n 個資料時，在最糟的狀況 ？ rt 在排序n 個資料時，其時間複 在排序n 個資料時，其時間複雜度 n! 2n n2 n nlog2 lo 2 1 3 4 5

9 n!、2n、n2、nlog2n、 雜度是這6 種的那一 狀況下，時間複雜度 複雜度是這6 種的那 度是這6 種的那一 n 2n og2n n 三、在電腦內部有許多工作 需要安排很多queue 來 Ready queue、I/O queue （每小題5 分，共25 請問工作（job）及程 請問圖中「Time slo 請問圖中「I/O satis 請問Ready queue 儲 在實作queue 時，一 四、資料結構的分類可如下 請問Linear Data Stru 為何？ 請問圖中Static 和D 請問圖中何者亦稱為 在實作LinkedList 時 請問這兩個部分各存 下面顯示一個Grap adjacency matrix 及 兩個做法。 作（job）及程序（process）同時 來將它們做先後順序的排列。下圖 e 等3 種queue 在處理job 及proc 分） 程序（process）的主要差別為何 ot exhausted」所指意思為何？ fied」所指意思為何？ 儲存的內容為何？ 一般常用FIFO queue，請問FIFO 下圖所示：（每小題5 分，共25 ucture和Non-Linear Data Structu Dynamic 兩者主要的差別為何？ 為LIFO？ 時，每個元素通常會含有兩個部 存什麼資訊？ ph 例子。在實作Graph 時，通 adjacency list，請使用上面的G 時在爭用資源，因此 圖顯示Job queue、 cess 的整體流程圖。 何？ 意義為何？ 分） ure兩者主要的差別 部分：data 和link。 通常有兩種做法： Graph 例子，說明這

多元程式規劃作業系統（Multi-Programmed OS）的程序狀態圖如下所示。 其中分派程式（Dispatcher）之功用為何？（15 分） 程序狀態圖

多元程式規劃作業系統中之CPU 排程（CPU Scheduling）問題： 試以「先到先處理」（First-Come_First-Served, FCFS）排程方式處理下述 程序的資訊。 程序 抵達順序 所需時間（ms） P1 1 18 P2

3 P3 2 6 畫出程序處理之甘特圖。（10 分） 計算平均等待時間。（10 分） 三、何謂對等式架構或同儕式架構（Peer to Peer）？（15 分）

計算下列流程圖的循環複雜度（Cyclomatic Complexity）M。（10 分） （Hint：M = E – N + 2P, E = # of edges, N = # of nodes, and P = # of connected components）

何謂空間局部性（Spatial Locality）？存取局部性（Locality of Reference） 對電腦記憶體的影響為何？（20 分）

何謂網頁置換或網頁竄改（Web Defacement）攻擊？為何網頁置換深受 駭客喜愛？（20 分）

在快取記憶體（cache）系統，直接對映（direct mapping）、關聯對映（associative mapping） 及集合關聯對映（set-associative mapping）有何不同？（20 分）

國際標準組織（International Standard Organization, ISO）定義了開放系統互連（Open System Interconnection, OSI）的7 層（layers）架構，試問其中有那些層做流量控制（flow control）？（5 分）為何要做流量控制？（5 分）各層的作法有何不同？（10 分）

有一無向性連結圖（undirected connected graph）如圖所示，每一鏈路（link）的成本 標示在該鏈路旁邊。試依圖建構一個最小成本生成樹（minimum cost spanning tree） 並標示其生成順序。（每小題10 分，共20 分）  採用Kruskal’s algorithm 且無任何限制。  採用Kruskal’s algorithm 但限制每一分支（branch）最多只能有兩條鏈路。 （請接背面） G E D F A C B 5 9 10 12 8 14 7 13 11 6 106 年專門職業及技術人員高等考試 建築師、技師、第二次食品技師考試暨 普通考試不動產經紀人、記帳士考試試題 全一張 （背面） 等 別 ：高等考試 類 科 ：電子工程技師 科 目 ：電子計算機原理

有一虛擬記憶體（virtual memory）使用兩層記錄表（two-level page tables），其虛擬 位址（virtual address）之格式（format）為（table number, page number, displacement within page）。若最前面的四個記錄表如下圖所示： Page Table 0 Page Table 1 Page Table 2 Page Table 3 page number page frame # page number page frame # page number page frame # page number page frame # 0 on disk 0 15 0 6 page table not in main memory 1 12 1 7 1 13 2 9 2 on disk 2 0 3

3 0 3 on disk 試問：  針對下表有關虛擬記憶體的接取（access），試問(a)～(h)應為何？（8 分） 註：若未發生頁面錯誤（page fault），則以（frame number, displacement）的形式填 入其實體位址。 Access Table number Page number Displacement within page Physical address Access rights Fetch data 1 2 50 page fault read Fetch data 0 1 12 (a) (b) Store data 2 3 2000 (c) (d) Jump to 3 3 100 (e) (f) Jump to 0 2 60 (g) (h) 依照上表的接取資料，其虛擬位址空間（virtual address space）至少有多大？（6 分） 其實體記憶體（physical memory）至少有多大？（6 分） 五、請說明為何排程器（scheduler）要區別I/O 受限程式（I/O-bound programs）和CPU 受限程式（CPU-bound programs）。（20 分）

於下圖執行廣度優先搜尋法（Breadth First Search）後之結果為何？請將搜尋經過之 先後路徑以下法一一列出：(V0,V1), (V0,V?), …。（註：如有多個端點可供選擇時，以 下標較小者之端點為優先）（15 分）

試化簡右式：[(w' ⋅x) ⋅(y + z' )' + (w' ⋅y) ⋅(z' + y)' ⋅(v ⋅x)]'；式中⋅為AND 閘，+ 為OR 閘，' 為NOT 閘。（15 分）

試寫出一遞迴（Recursive）演算法或程式以求 ) , cos( k x 之值：（20 分） ) MAX ( !8 !6 !4 !2 1 ) cos( 8 6

2 ≤ − + − + − = k x x x x x L ;

!4 !6 ; 3 4 !2 !4 [ 2 4 6 2 2 4 × × ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = × × ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = x x x x x x ： 提示 )))] 1( 5 6 1( 3 4 1( 2 1 )! 2 ( )1 ( ) cos( 2 0 2 2 2 L − × − × − − = − = ∑ ∞ = x x x k x x k k k 四、執行下列C 程式後所列出每行之結果為何？主程式與副程式之參數傳遞方式為 Pass-by-value 或Pass-by-reference？（15 分） #include <stdio.h> void F1(int x) { printf("Inside F1 x = %d before adding 10.\n", x); x += 10; printf("Inside F1 x = %d after adding 10.\n", x); } int main() { int a=91; printf("a = %d before calling F1.\n", a); F1(a); printf("a = %d after calling F1.\n", a); return 0; } V3 V0 V1 V4 V5 V2 V6 V7 起始點 105年專門職業及技術人員高等考試建築師、 技師、第二次食品技師考試暨普通 考試不動產經紀人、記帳士考試試題 全一張 （背面） 等 別： 高等考試 類 科： 電子工程技師 科 目： 電子計算機原理 五、試分別說明.NET Framework 及C# 之功用。（15 分） 六、試分別說明IoT（Internet of Things）及M2M（Machine to machine）之功用。（20 分）

任何使用比較運算（comparison）的排序演算法，當其輸入的資料項目的數目為n 時，最少需要多少個比較運算方能完成？請使用時間複雜度表示之，並說明其理 由。（10 分） 就您所知，有無現存的排序演算法，其最壞情況之時間複雜度可以達到上述之下 限（lower bound）？若有，請舉一例說明之；若無，請說明理由。（10 分）

定義二元搜尋樹（binary search tree，BST）。（5 分） 使用下列八個資料，建構一棵二元搜尋樹：（5 分） 56，30，25，42，78，89，63，12 可否使用建構BST 的方法完成資料的排序？若可，請說明其方法，並估計其計算 複雜度（computational complexity）；若否，請說明其理由。（10 分）

何謂獨立程序（independent process）與協力程序（cooperating process）？（5 分） 何謂IPC（interprocess communication）？（5 分） IPC 有那兩種基本模型（model）？請說明之。（10 分）

所有的多處理器系統均使用多層次快取記憶器（multilevel cache）架構，以提升系 統之性能。請回答下列問題： 何謂多層次包含（multilevel inclusion）與子集性質（subset property）？（10 分） 假設L2 的區段大小（block size）為L1 的四倍。說明當一個快取失誤（miss）造 成的L1 與L2 置換（replacement）時，可能導致多層次包含性質不成立的理由。 （10 分）

何謂程序的關鍵部分（critical section）？（5 分） 解決程序的關鍵部分之問題時，必須滿足那三個重要條件？（15 分）

一般電腦硬體或者是程式語言中的運算有分為「算術運算」（Arithmetic Operation） 與「邏輯運算」（Logic Operation），請分別說明其不同之處？（10 分）請用 Pseudo code 寫出如何用「邏輯的移位」（Shift）運算與「算術的加法」運算模擬出 算術乘法c = a × b。程式中並請注意加上註解（Comment）。（10 分）

請比較「軟體中斷」（Software interrupt）與「硬體中斷」（Hardware interrupt）之 不同。（10 分）並請比較「不可遮罩式中斷」（Non-maskable interrupt）和「可遮 罩式中斷」（Maskable interrupt）之不同。（10 分）

A*(B+C)-D/E 為中序（Infix）表示式。 請將該中序表示式改為後序（Postfix）表示式與前序（Prefix）表示式。（10 分） 請用適當的資料結構，以繪圖（或表）與使用文字說明中序轉後序演算過程。 （10 分）

請比較LTE（4G）與WiMAX 之不同（請針對發展目的、標準制定單位、頻段、存 取技術、天線技術、傳輸效能…等項目比較）。（20 分）

請說明資料庫的「正規化」（Normalization）。（10 分）何謂BCNF（Boyce-Codd Normal Form）正規化形式？（10 分）

何謂兩個邏輯運算式是有等價（logically equivalence）的關係？（10 分） 假設P(x) 跟Q(x) 是兩個命題函數（propositional function），下列四種邏輯運算式 中，何者是和“¬∃x (P(x) ∨ Q(x))”有等價的關係？(i) ¬∃x P(x) ∧ ¬∃x Q(x)， (ii) ∀x (P(x) ∧ Q(x))，(iii) ∀x (¬P(x) ∧ ¬Q(x))，(iv) ∀x ¬P(x) ∧ ∀x ¬Q(x)，若無等價 關係，請舉例說明。（10 分）

假設f(x) 為十進位數轉十六進位數的函數，g(x)為二進位數轉十進位數的函數，那 麼合成函數 f。g(x)是從幾進位數轉幾進位數的函數？f(1010)、g(1010)、f。g(1010) 的值各為何？（20 分）

(1010)　(1010)　(1010) 20 分

遞迴呼叫程序（recursive procedure）乃是一個程序直接或間接呼叫程序本身。階層 計算（factorialization）的程序，輸入（input）為一個正整數N，而輸出（output） 為1*2*…*N。例如，呼叫階層函數factorial(5)，會得到的回覆值為 1*2*3*4*5=120。 請分別以使用遞迴呼叫與不使用遞迴呼叫，來撰寫此階層計算程序的虛擬程式碼。 （20 分）

(5) 20 分

當一般個人電腦開機時，作業系統是如何啟動的？何謂多工的作業系統？要達成多 工的作業環境，需要什麼樣的技術？在目前所流行的雲端運算環境中，客端（end user）所使用的作業系統，將會有什麼樣的改變？（20 分）

基本電腦的網路拓樸有所謂的星狀、環狀與樹狀（或稱匯流排），請問星狀的網路 拓樸有何優缺點？乙太網路是屬於何種拓樸型式？此外，在乙太網路上，如何辨識 網路上的節點？又要如何得到此辨識跟IP 位址的對應？（20 分）

請說明跳頻展頻（frequency hopping spread spectrum, FHSS）的工作原理。（8 分） 何謂多路徑衰退（multipath fading）？（6 分）跳頻展頻如何抗拒多路徑衰退 （multipath fading）？（6 分）

如何區別快取記憶體（cache）空間場所（spatial locality）和時間場所（temporal locality）的概念？（10 分）請說明實現（exploit）快取記憶體空間場所和時間場所 的策略。（10 分）

請以霍夫曼演算法（Huffman algorithm）用最少的位元（bits）將訊息（message） “AABCDBCACCFEDEFAC＂編碼（encode），求出各符號（symbol）的編碼、編 碼後的訊息及總位元數。（20 分）

請說明下列各組排程準則（scheduling criteria）在某些設定（settings）有所牴觸： CPU 利用度（utilization）和反應時間（response time）（10 分） 平均來回時間（average turnaround time）和最大等待時間（maximum waiting time） （10 分）

請說明C 語言程式中，下列各組在執行上有何不同： called by value 和called by reference（5 分） break 和continue（5 分） #include "filename"和#include <filename>（5 分） #define X 5.0;和float y=5.0;（5 分）

請說明 “複雜指令集電腦”（CISC）及 “精簡指令集電腦”（RISC） 之不同處。 （20 分）

說明一般程式語言中的巨集（macro） 和副程式（subroutine）有何差別？（10 分）

請將W *（X + Y / Z）的中序（infix）表示法改為後序（postfix）表示法與前序（prefix） 表示法。（10 分）請用相關資料結構，繪圖與使用文字說明你的中序轉後序方法。 （10 分）

一般系統程式之載入程式（loader） 的功能與分類為何？請加以說明。（10 分）

某報消息 「…13 部 DNS server 遭到大型DDoS攻擊…」，請解釋此段消息之所謂 「DNS server」 與 「DDoS 攻擊」之意義。（20 分） 六、某大學圖書館擬設計一個資料庫系統用以管理借書與還書資料，處理的資料有： ● 書[Book]：資料是由條碼號[Book_ID]與書名[Book_Name]所組成 ● 讀者[Reader]：資料是由讀者證號[Reader_ID]，讀者姓名[Reader_Name]組成 ● 每一次借還書[BR_Book]：會登記讀者證號[Reader_ID]、書名[Book_Name]、借 書時間[Borrow_Time]、與還書時間[Return_Time] 請以上述說明之實體名稱（如[Book]），依據資料庫管理系統-ERM（Entity- Relationship Model；個體-關係模式）建立以上之ERD（Entity-Relationship Diagram; 個體-關係圖），並加以文字說明。（20 分）

國際標準組織（international standard organization；ISO）定義了開放系統互連（open system interconnection；OSI）之7 層（layers）架構，試問其中有那些層有做流量控 制（flow control）？為何要做？各層的作法有何不同？（20 分）

有一導管（pipeline）處理機執行每一指令（instruction）必須分四級（stages）處理， 例如：擷取（fetch）、解碼（decode）、運算元擷取（operand fetch）、執行 （execute）四級。若各級之處理時間分別是：第一級需要80 奈秒（ns），第二級 需要50 奈秒，第三級需要90 奈秒，第四級需要40 奈秒（假設無其他延遲）。試 問：（20 分） 若執行10 個指令，共需要多少時間？ 若執行100 個指令，共需要多少時間？

乙太網路（Ethernet ）採用載波感測多重存取/ 碰撞偵測（carrier sense multiple access/collision detection；CSMA/CD）的存取（access）方式，請說明其原理。（20 分）

依序讀入一串數字：71, 48, 33, 11, 78, 51, 63, 18, 25, 9，試求其：（20 分） 最大堆積樹（maximum heap tree）。 二元搜尋樹（binary search tree）。

試依下圖之無向性連結圖（undirected connected graph），建構一個最小成本生成樹 （minimum cost spanning tree）並標示其生成順序，每一鏈路（link）之成本標示在 其旁邊，而啟始（source）節點（node）為節點0：（20 分） 採用Prim’s algorithm 且無任何限制。 採用Prim’s algorithm 但限制每一分支（branch）最多只能有兩條鏈路。

3 2 5 1 4 0 10 26 20 24 16 18 14 28 22 12 Source node

考慮三種排序方法：選擇排序法（Selection sort）、插入排序法（Insertion sort）與 泡沫排序法（Bubble sort）。對於下列的問題請說明其原因：（20 分） 當欲排序的資料都是很長的資料錄，且它們的鍵值長度都很短時，最適合用選擇 排序法，為什麼？ 當欲排序的資料已經幾乎達到排序結果時，最適合用插入排序法，為什麼？ 當欲排序的資料是完全相反次序時，最適合用選擇排序法，為什麼？ 當欲排序的資料是完全相同時，最適合用泡沫排序法，為什麼？

向量電腦（Vector Computer）主要借重其處理器CPU 中之ALU（Arithmetic Logic Unit，算術邏輯單元）個數多於控制單元，試說明其運作原理，並以虛擬程式指令 舉例說明其平行計算。（20 分）

試說明網路架構（Topology）規劃的準則（Criteria），並舉一校園為例規劃其網路 架構（Topology），且說明規劃的準則（Criteria）及採用的通訊協定（Protocol）。 （20 分）

試說明從單人單工作業系統、單人多工作業系統、多人多工作業系統到多 CPU 多人多工作業系統，系統要多考量處理那些工作（請分別從到、到、 到說明之）？（20 分）

若有布林函數XY’+X’Y，試問可用何種邏輯閘完成之，並請說明。（註：Y’表 NOT Y；X’表NOT X）（20 分）

設計一電路圖，以接受二個輸入值a 跟b，並輸出二個值c 跟d，其間關係要滿足下 列要求：（20 分） c＝(a OR b), d＝NOT ((a OR b) AND (NOT b))

如下之兩個關連式資料表中，表R1 之鍵值（Key）為（x, y, z），表R2 之鍵值為 （x, y），請問此資料庫為何不滿足第二正規化的設計？如何修改此兩個資料表， 使其得以滿足第二正規化？（20 分） R1(x, y, z, a, b) R2(x, y, b)

在資料排序的方法中，有所謂泡沫法逐一將比較大的數字往下移動，請撰寫此程式 （可使用虛擬碼Pseudocode），並求你所使用方法之計算複雜度？（20 分）

請分別以反覆（iterative）與遞迴（recursive）的程式方式撰寫（定義）階層函式 （factorial function）。階層函式f(n)＝n*(n-1)*…2*1, f(1)＝1, n 為正整數。（20 分）

(1) 20 分

作業系統中多工程度（degree of multiprogramming）與電腦之CPU 使用率 （utilization）有何關係？在分頁（paging）的虛擬記憶體環境中，什麼情況下會有 很多程序（process）在記憶體中，但CPU 的使用率卻很低的情況？（10 分） 六、假設有10 部伺服器以及15 部個人電腦，再假設個人電腦欲連結到伺服器必須經由 連接兩者之連接線直接連結，且每部伺服器同時間只能服務ㄧ部電腦。我們若要求 任何不超過10 部電腦要連接上伺服器時，每部電腦都要能連得上伺服器。請問最 少需架設多少條線？如何完成？若將直接連接的條件去掉，你有什麼較進步的網路 架設法？（10 分）

4 8 20 33 14 b 17 11 12 一、一個200MIPS 的CPU 平均執行一個指令所需時間為何？（5 分） 請說明何謂管線（pipeline）？（7 分）假設一個不具管線（pipeline）處理器執行 一指令分五個執行階段且每階段所需時間如後：指令擷取（instruction fetch）： 7ns、指令解碼（instruction decoding）：7ns、執行運算或計算位址：8ns、主記憶 體存取：7ns、結果寫回暫存器：7ns。若以管線對處理器予以改善後（同樣五個 執行階段），每個執行階段需多耗時1ns，若不考慮其他延遲影響，此管線結構 改善技術將使處理器指令執行速率改善多少？（8 分）

請將十進位數121.625 轉換成八進位數。（3 分） 八位元（bits）長度以2 補數（2’s complement）所能表示的最大正數與最小負數 分別為何？（4 分） 請計算兩十六進位數加法ADE + FACF。（以十六進表示結果）（3 分）

請解釋在作業系統行程（process）管理中的死結（deadlock）現象，又發生死結的 條件為何？（10 分）

請說明網路的Link State Routing Protocol 與Distance Vector Routing Protocol。（6 分） 為什麼大部分採用Link State Routing Protocol？（4 分）

請就圖一具權值（weight）的圖（graph）回答下列問題： 以節點a 為起點依廣度優先走訪（Breadth First Search）方法列出走訪的節點（node） 順序，當有多重選擇時再以邊（edge）之權值小者優先。（5 分） 請以Kruskal’s 演算法繪出此圖之最少成本生成樹（minimum cost spanning tree） （5 分） 圖一 95年專門職業及技術人員 高等考試建築師、技師考試暨 普通考試不動產經紀人、地政士考試試題 代號：01260 類 科： 電子工程技師 全一張 （背面） 六、請以時間效能為考量根據，從下列幾種不同的排序法（sorting）中，選擇適合各小 題情況的排序法。（每小題4 分，共20 分） 快速排序法（Quick Sort）、插入排序法（Insertion Sort）、合併排序法（Merge Sort） 、氣泡排序法（Bubble Sort）、堆積排序法（Heap Sort） 擬排序的對象大部分都已依需要的關係排列（例如由小到大）。 擬排序的對象數量大（約數千筆）且大部分未依任何關係排列。 擬排序的對象數量大（約數千筆）且大部分剛好與需要的關係成相反的關係排列 （例如我們需要由小到大，它們卻大部分由大到小）。 擬排序的對象數量小（約一、二十筆）。 排序法的時間效能在最差狀況均為O(n log n)。 七、請說明資料庫中，SQL（Structural Query Language）的下列三種語言的用途：資料定 義語言（Data Definition Language）、資料操作語言（Data Manipulation Language）、 資料控制語言（Data Control Language）。（10 分） 八、請說明並比較將高階程式語言轉換成計算機可執行語言的兩種模式：編譯器 （compiler）、直譯器（Interpreter）。（10 分）

請畫出一個一位元全加器（full adder）的結構圖。CPU 的暫存器中，程式計數器 （program counter）與指令暫存器（instruction register）的功能是什麼？又那兩個特 殊暫存器分別紀錄記憶體位址與記憶體內容？（20 分）

何謂B-tree？請具體說明如何應用B-tree 技術於硬碟的處理上。並請依序說明如何 將下列文字儲存在order 為5 的B-tree 結構： C N G A H E K Q M F（20 分）

請以八個位元串來表示浮點數3.5。依照你的表示法，說明8 個位元所能表示之最 大與最小的數值各為何？（10 分）

何謂哲學家吃飯的問題（Dining-Philosophers Problem）？請問如何以Semaphore 來 解決此問題？（10 分）

網路上的通訊協定中，SIP 的全稱及功能是什麼？如何識別一個SIP 網路中之來源 （source）？（10 分） 六、以二元搜尋法（binary search）來尋找1000 筆由小到大排列好的資料中之某筆資料 ，請問最少、平均及最多需作幾次比較才可找到該筆資料？（10 分） 七、何謂資料庫系統的三層架構？各層所描述的內容及應用的對象為何？那一層所描述 的性質會有所謂的關聯式或網路式之分？（10 分） 八、在一個程式呼叫一個副程式時，如何區別型式參數（formal parameter）與實質參 數（actual parameter）？參數的傳遞中，傳值呼叫法（call-by-value）與傳址呼叫 （call-by-reference）法有何不同？（10 分）

解釋名詞：（每小題5 分，共25 分） Web services XML SOAP（Simple Object Access Protocol） GRID Computing IEEE 802.11b

試討論TCP（Transmission Control Protocol）與UDP（User Datagram Protocol）的適 用範圍。（25 分）

試比較POP3（Post Office Protocol – version 3）與IMAP（Internet Mail Access Protocol）。 （25 分）

討論下列磁碟架構：（25 分） RAID-0, RAID-1, RAID-3, RAID-5, RAID-50 RAID（Redundant Arrays of Inexpensive Disks）