104年 - 104 專技高考_資訊技師：資料結構與資料庫及資料探勘#41547

科目：資料結構與資料庫及資料探勘 | 年份：104年 | 選擇題數：0 | 申論題數：13

試卷資訊

所屬科目：資料結構與資料庫及資料探勘

選擇題 (0)

申論題 (13)

⑴下列圖形是一棵 B-tree of order 3，若陸續加入資料：99、20，會成為怎樣的 B-tree，請畫出最後的 B-tree。（5 分）

⑵請問 B-tree of order 3 又稱為什麼樹？（5 分） 26, 66 5, 25 33, 52 72, 88

二、堆疊（stack）可應用於後序表示式（postfix expression）的運算處理，請利用下列的表示式，繪出堆疊內的變化來說明如何利用堆疊計算其結果，並請寫出演算法。後序表示式：4 8 – 9 3 / *（該表示式中的數值均為個位數）。（10 分）

三、請將 18、25、6、33、9、12、55、14 依快速排序（Quick sort）由小排到大，若是以最左的資料 18 為支柱點（pivot），請繪出 first pass（即是指將資料 18 放在正確的位置）之排序過程。（5 分）

⑴請問什麼是最小成本擴展樹（minimum cost spanning tree）？（5 分）

⑵依據下列的圖形，利用 Prim's algorithm 求出最小成本擴展樹 T，假設 TV 為 T 的頂點集合，設定 TV 的初始值為 A，即 TV= {A}。請繪出最小成本擴展樹的形成過程。（10 分） 8 12 A B C 16 23 4 25 18 D 10 F 15 E

五、資料庫管理系統一個重要的工作即是進行交易（transaction）管理，在同作控制（concurrency control）處理中要確保交易的四項特性，簡稱為 ACID，請逐一說明這四項性質。（15 分）

【已刪除】六、有一資料表 PRODUCT 之關聯綱要（relation schema）如下，其中產品代碼為主鍵（ primary key ），除了主鍵之相依性外，若以 →表示相依性（ functional dependency），該表還存在著右列的相依性，供應商代碼→供應商名稱

請問該資料表符合第三正規化的格式（third normal form）嗎？若不符合，請問該如何修改使之符合第三正規化之格式。（10 分）

請問該資料表的主鍵（primary key）應設為該資料表的那些屬性（attribute）？請說明你的答案。（5 分）

⑵寫出“列出平均體能分數大於 80 的科系代碼與該科系的平均體能分數”的 SQL 指令。（5 分）

⑶寫出“列出每科系的最高體能分數與科系代碼”的 SQL 指令。（5 分）

八、在資料探勘的分類方法（cluster analysis）中有一方法稱為 nearest-neighbor clustering algorithm，請說明該方法的運作原理？（10 分）

【已刪除】九、資料探勘中的關聯法則（Association rule）可用來尋找顧客購買產品的關聯規則， {麵包}→{牛奶}表示購買麵包的顧客也會購買牛奶。有一交易紀錄如下表，請寫出關聯規則 {b, c}→ {d} 的支持度（support）和信心度（confidence），及其計算過程（5 分），並說明這兩者是指什麼？（5 分）