:::
資料處理概要4033-002
三、我們若針對集合 S = {6, 2, 7, 4, 1, 5, 9, 8, 3},用快速排序(quicksort)來排序,請說明步驟及過程,並說明快
速排序法應歸屬於下列四種演算法中之那一類:暴力法(brute force algorithm)、貪婪法(greedy algorithm)、各
個擊破法(divide-and-conquer algorithm)、動態規劃法(dynamic programming algorithm),請解釋其原因。

◎【擬答】:

(一)快速排序步驟及過程為:
1.從數列中挑出一個元素,稱為"基準"(pivot)。
2.重新排序數列,所有比基準值小的元素擺放在基準前面,所有比基準值大的元素擺在基準後面(相同的數可以到任一
邊)。在這個分割結束之後,該基準就處於數列的中間位置。這個稱為分割(partition)操作。
3.遞迴地(recursively)把小於基準值元素的子數列和大於基準值元素的子數列排序。遞迴到最底部時,數列的大小是
零或一,也就是已經排序好了。這個演算法一定會結束,因為在每次的疊代(iteration)中,它至少會把一個元素擺
到它最後的位置去。
(二)快速排序使用各個擊破法(Divide and conquer)策略來把一個序列(list)分為兩個子序列(sub-lists),此可由(一)
的步驟 2 分割操作後分別針對分割開的兩個數列在步驟 3 遞迴進行看出。
 

四、一關聯式資料庫之綱要(relational database schema)如下:
產品(編號,名稱,價格)
客戶(身分證號,姓名,地址,年齡)
購買(身分證號,編號,數量)
(一)請用 SQL 指令來查出所有購買產品的客戶中,年齡小於 15 歲的客戶所購買的產品名稱、數量和這些客戶的姓名。
(10 分)
(二)今欲查出所有沒有購買任何產品之客戶身分證號和姓名,某位資料庫管理員所寫下的 SQL 指令如下:
 SELECT 身分證號,姓名
 FROM 客戶,購買
 WHERE 客戶.身分證號≠ 購買.身分證號;
 請問他的寫法是否正確?若不正確,請說明錯處,並寫出正確的 SQL 查詢。

◎【擬答】:

(一)
SELECT 產品.名稱, 數量,客戶.姓名
FROM 產品, 購買, 客戶
WHERE 產品.編號 = 購買.編號 AND 購買.身分證號 = 客戶.身分證號 AND
年齡<15
(二)此 SQL 查詢寫法不正確,應使用下列 SQL
SELECT 身分證號, 姓名
FROM 客戶
WHERE NOT EXISTS(
SELECT *
FROM 購買
WHERE 購買.身分證號 = 客戶.身分證號 )