統計 104 年資料處理考古題

電腦的記憶體分為那幾種？請比較它們的功能、速度和大小。（20 分）

邏輯資料庫設計（logical database design）的輸入和輸出各為何？實體資料庫設計 （physical database design）的輸入和輸出各為何？寫出邏輯資料庫設計和實體資料庫 設計的差異之處，並試申論之。（20 分）

請根據資料庫中的資料儲存架構，說明以下3 種不同的資料庫，所採用的儲存架構 以及該架構的優缺點。（每小題10 分，共30 分） 階層式資料庫 網狀式資料庫 關連式資料庫

考慮關聯式資料庫的三個table：學生（Student）、課程（Course）和修課紀錄（Taken）。 它們的結構（schema）定義如下：Student（sName, sID）、Course（cName, cID, credit）、 Taken（sID, cID, grade）。（每小題20 分，共40 分） 以E-R diagram 畫出三個table 的關係，並標註table 中的primary key 和foreign key。 給定學生姓名（王小明），請以SQL 語法列出學生姓名（sName）、學號（sID） 和學生的加權平均成績（GPA ）。一個學生的一門課的加權成績是 Course.credit*Taken.grade，一個學生的總加權成績是所有修過課加權成績的總和， 一個學生的GPA 計算如下： 學生總修課學分數 學生修課的總加權成績 ＝ GPA 注意可能會有學生有相同的姓名，查詢必須列出所有相同姓名學生的GPA，並且 以學生的sID 大小排列。

現在有100 個正數儲存在陣列A(1)至A(100)中，說明下列程式碼的意義為何？其中 符號〝^〞代表次方。 B = 0 C = 0 For j = 1 to 100 B = B + A(j) Next j B = B / 100 For j = 1 to 100 C = C + (A(j) – B) ^ 2 Next j C = C / 100 Output B, C 上述程式包含了二個迴圈，若只能使用一個迴圈來得到所要的B 和C，其程式碼應 如何撰寫？（20 分）

Ethernet（乙太網路）是一種廣泛使用的電腦區域網路技術。 請說明早期的Ethernet 的主要連線架構。（5 分） Etherne  t 採用CSMA/CD 來解決多部電腦間，資料傳輸相衝突的問題，請說明 CSMA/CD 的工作原理。（20 分）

請回答下列關於IP 網路封包欄位的問題：（每小題10 分，共20 分） TTL 的作用是什麼？請以IP routing 的原理說明為何需要TTL 這個欄位。 header checksum 的作用是什麼？為何checksum 可以達到這個功能？

在設計關聯式（relational）資料庫時，其資料的完整性（integrity）可區分成二種： 個體（entity）完整性和參照（referential）完整性，首先說明這二者分別為何，並論 述在關聯式資料庫管理系統（database management system, DBMS）中，要透過何種 方式來達到這二種完整性。（15 分）

在作業系統領域，有所謂的分時（time-sharing）作業系統。 請說明其工作原理。（5 分） 請說明外部中斷（Interrupt）如何協助作業系統提供分時（time-sharing）功能。 （5 分） 當中央處理機（CPU）無法接受外部中斷時，小明突發奇想，提出利用內部中斷 （Trap）指令的替代方案。小明宣稱只要將Trap 指令，適當的插入機器程式碼中， 並適當的修改作業系統，仍然可以讓作業系統達到高度的分時（time-sharing）功 能。請對小明的奇想，提出評論。你必須先回答，同意或不同意小明的論點（請 勿提供模稜兩可的答案），再說明你同意或不同意的理由。（10 分）

一個binary tree 的node 定義如下： struct node { int value; struct node *left, *right; }; 寫出一個recursive function，int maxvalue(struct node *p)，找出一個binary tree 中的最 大值。（20 分）

符號⊕表示電腦中二元的exclusive-or 運算，而16 進位的5E 可表示成二進位的 01011110： 計算A7⊕3B⊕69。（5 分） 對任三個16 進位的位元(byte)U、V、W，證明若U⊕V = V⊕W，則U = W。（10 分）

為了簡化程式設計細節，本題假設，對程式所將輸入的數字，都會是大於2 的正整數。 小明設計了一個演算法，用來判斷所輸入的一個正整數，是否為質數。小明的演 算法，用虛擬碼寫出如下： procedure check_prime(N) { isprime = TRUE for ( i = 2 ; i <= N ; i = i + 1) { If ( N 是 i 的倍數 ) then isprime = FALSE } print ( isprime ) } 小華將小明的演算法輸入電腦，發現演算法有錯誤。小華跟小明詢問，發現小明 的觀念沒錯，只是打字時不小心。請問，小華該如何為小明改正這個演算法？ （註：你只能更正演算法中打字錯誤的部分，不可以重新設計新的演算法）（10 分） 小華是個遞迴演算法的愛好者。所以，小華嘗試用遞迴程式呼叫，重新設計了一 個，也能判斷所輸入的一個正整數，是否為質數的遞迴演算法，交給小明。結果 小明不小心弄丟了。現在，請你為小明重新設計這個，能用來判斷所輸入的正整 數是否為質數的遞迴演算法，請注意，在你的演算法中不可以使用任何的迴圈。 （15 分）

在網路中進行資料傳輸時，會將資料先加密（encryption）後再傳送，俟加密完成的 資料送達後再進行解密（decryption），以還原成原來資料，這種資料加解密的方法 （cipher）可以分二大類：對稱的（symmetric）和非對稱的（asymmetric）；說明這二 類加解密方法的區分依據為何？並申論其個別的適合使用時機。（20 分）

在設計關聯式（relational）資料庫時，若二個個體（entity）為多對多的關係，則應 如何進行處理？其原因為何？（10 分）