| 91年 4月13日 14:00 ~ 15:30 資管系選考 | 誠實是我們珍視的美德， 我們喜愛「拒絕作弊，堅守正直」的你！ |
| 科目：資料結構與資料庫 |
| 第一題： | 請寫一程序，計算一棵二元樹的深度(高度)。(8%) | |
| 定義：設根部節點的階度(level)為1，而其他任一節點的階度為其父節點的階度+1。 | ||
| 深度(高度)：一棵二元樹中的最大階度值。(程式語言不限) | ||
| 第二題： | fibonacci 數列之定義 | |
|
|
||
| 設有下列遞迴語法： | ||
|
|
||
| 問題：請將上述遞迴寫法，改用非遞迴方式。(程式語言不限)(8%) | ||
| 第三題： | 一棵滿足錐特性(heap property)的二元樹，我們叫錐形樹，請問什麼是錐形特性。(6%) | |
| 第四題： | 設有一個大小為n的陣列，陣列上的資料完全隨機置放，在不准更動目前陣列中資料存放位置的情況下，是否有辦法加速尋找某個資料，該怎麼找？並簡述理由(理由未寫，或寫錯，一律不給分)。(6%) | |
| 第五題： | 樹之追蹤(反後序式RLN)(6%) | |
|
|
||
| 問題：請將上列二元樹之節點資料用RLN追蹤方式依序寫出來。 | ||
| 第六題： | 設一棵B-tree(如下圖)，其Order(m=2)。Order之m值在規範一棵B-tree節點上的鍵值數目。如果是根部，則1≦鍵值數目≦2m，否則m≦鍵值數目≦2m。 | |
 |
||
| 問題：請將加入鍵值為98後之b-tree畫出來。(10%) | ||
| 第七題： |  |
|
| 設R關係表上的資料與時間無關，也就是上列資料是Ｒ關係表所有可能的資料。 | ||
| 問題1：請証明Ｒ關係表不為第二正規化關係表。(8%) | ||
|
問題2：請將Ｒ關係表分解成第二正規化關係表(請分別給予一個特定的名稱)，並請寫出所得第二正規化關係表的資料。(6%) |
||
| 問題3：請分別寫出分解後，所得關係表的備選鍵(Candicate Key)，並簡述理由(理由錯者或未寫者一律不給分)(6%)。 | ||
| 第八題： | 在共時問題(concurrency)內，我們會用(1)Wait-die(老待少)或(2)Wound-wait(少待老)來解決問題。 | |
| 問題1：請問是解決什麼問題。(5%) | ||
| 問題2：請証明(1)Wait-die為何可解決該問題。(7%) | ||
| 第九題： | 資料流量估算。 | |
| 設有下列三關係表及相關資料大小： | ||
| 顧客(顧客編號，顧客姓名，電話，地址) | ||
| 訂購(顧客編號，產品編號，訂購日期，訂購數量，送交數量) | ||
| 產品(產品編號，產品名稱，庫存量，安全存量) | ||
| 送交數量係指送交顧客的數量。 | ||
| 假設共有50種不同的產品，100個顧客，訂購關係表共有1000個列錄。到目前為止尚有20%的訂購仍未將貨完全交給顧客。平均每10個產品，就有一個，其庫存量＜安全存量。關係表內特性項的長度如下： | ||
| 顧客：顧客編號：5 bytes，顧客姓名：10 bytes，電話：10 bytes，地址：55 bytes | ||
| 訂購：顧客編號：5 bytes，產品編號：5 bytes，訂購日期：8 bytes，訂購數量：2 bytes，送交數量：2 bytes | ||
| 產品：產品編號：5 bytes，產品名稱：15 bytes，庫存量：2 bytes，安全存量：2 bytes | ||
| 請根據上述的資訊，計算下圖中的 f3，f4，f6，f8 各相關運算後所產生的資料量(請將計算過程寫出，並簡述理由)。 | ||
 |
||
| 第十題： | SQL語言所牽涉到的關係表，請參考第九題。 | |
| 問題1：請用exist的寫法回答下列查詢句。 | ||
| 將被訂購且已完全交貨的產品編號及產品名稱印出來。(6%) | ||
| 問題2：多層次子查詢句。 | ||
| 請將下列SQL查詢語言，改用多層次子查詢句(Subquery)的寫法作答。(8%) | ||
| Select產品編號，產品名稱 | ||
| From顧客，訂購，產品 | ||
| Where(產品.庫存量＜產品.安全存量) | ||
| and(訂購.送交數量＜訂購.訂購數量) | ||
| and(產品.產品編號＝訂購.產品編號) | ||
| and(訂購.顧客編號＝顧客.顧客編號) | ||
| and(顧客.顧客姓名＝”陳水木”)； | ||
--- END---