中原大學九十學年度碩士班入學招生考試

4月27日　　第3節 　　　　資管系 誠實是我們珍視的美德，
我們喜愛「拒絕作弊，堅守正直」的你！
科目： 資料結構及資料庫 （共4頁 第1頁）

第一題 佇列(Queue). 佇列之運作係從前端(front)取，後端(rear)加入。今設佇列採用環狀單向串列的形式來製作，如下圖：
串列上資料假設為整數型態。


問題 1. 請寫一程序佇列的加入。(7%)
問題 2. 請寫一程序做佇列的取出。 (7%)
    (程式語言不限)

第二題 河內塔(遞迴方式改為非遞迴方式) (10%)
設有下列河內塔之遞迴語法：
河內塔(N,A,B,C)
做    
  如果 N＞0
  則做  
    河內塔(N-1,A,C,B)
    搬第N個盤子，從A搬到B
    河內塔(N-1),C,B,A
  完做  
完做    

參數說明：N表示要搬的盤子數，A表示起點，B表示終點，C表示輔助點，也就是要將N個盤子從A搬到B，藉助C。
問題：請將上述遞迴寫法改用非遞迴方式。

第三題 請將Shell sort之運作方案寫出來(程式言或虛擬碼---pseudo-code寫法不限) (10%)

第四題 樹之追蹤(後序式LRN) (8%)

問題：請將上列二元樹之節1點資料用LRN追蹤方式依序寫出來。

第五題 參考完整性原則(referential integrity rule)
問題 1：請簡單舉例說明何謂參考完整性。 (6%)
問題 2：請簡單舉例說明參考完整性被破壞的情況。 (6%)
問題 3：請簡單舉例說明參考完整性問的題的處理方式。 (6%)

第六題 正規化(normalization form) (8%)
BCNF之定義：關係表中功能相依決定者，皆為備選鍵。
設下列關係表R與時間無關，也就是說該關係表上的資料情況為所有可能情況，請依據BCNF之定義，證明該關係表為BCNF。
R關係表
A
B
C
 
a2
b1
c1
 
a3
b1
c2
 
a1
b2
c1
 
a1
b1
c3
 
a1
b2
c3

第七題 共時問題(concurrency)
問題 1：請簡單舉例說明何謂dirty read (7%)
問題 2：請簡單舉例說明何謂phantom現象。（7%）

第八題 資料流量估算。
設有下列四關係表及相關資料大小：
倉庫(倉庫編號，配件名稱，倉庫電話)
配件(配件編號，配件名稱，配件庫存，倉庫編號)
組件(產品編號，配件編號，數量)
產品(產品編號，產品名稱，產品庫存)
說明：組件關係表，係表示一產品由哪些配件所組裝而成，及組裝該一產品所需的配件數量。
倉庫：倉庫編號：8bytes，倉庫名稱：10bytes，倉庫電話：10bytes
配件：配件編號：8bytes，配件名稱：10bytes，配件庫存：1byte
組件：產品編號：8bytes，數量：1byte
產品：產品名稱：10bytes，產品庫存：1byte
共有2000個配件，100個產品，10個倉庫，平均每個產品由20個倉件組成。
請根據上述的資訊，計算下圖中的f1,f2,f3,f4,f5各相關運算後所產生的資料量(請將計算過程寫出，並簡述理由)
特別注意代表等聯結(equi-join)，而非自然聯結(natural-join)小心兩者的差異。表示投射(projection)。表示選擇(selection) (10%)


第九題 多層次子查詢句(所牽涉到的關係表，請參考第八題)(8%)
請將下列SQL查詢語言改用多層次子查詢句(Subquery)的寫法作答。
Select配件編號，配件名稱，倉庫名稱
From倉庫，配件，組件，產品
Where(產品.產品名稱='prod-namex')AND(產品.產品編號=組件.產品編號)AND(組件.配件編號=配件.配件編號)AND(配件.倉庫編號=倉庫.倉庫編號)

 

　　　　　--- END---