統計 114 年資料處理概要考古題

給定以下有向加權圖（7 個節點A~G，15 條有向邊） 執行Dijkstra 演算法，逐步計算節點A 到每個節點的最短距離與路 徑。請以此例說明Dijkstra 演算法的運作方式，寫出每一步目前的「A 到每個節點的最短距離」與「前接節點（predecessor）」。（15 分） 請寫出A 到各節點的最短路徑與路徑長度。（5 分） 舉出兩個Dijkstra 演算法實際上的應用。（10 分）

某一公司的採購資料如下所述： 每一位客戶包含有屬性客戶編號、姓名、電話、地址。在客戶中，客戶 編號具有唯一性。 每一張訂單包含有屬性訂單編號、購貨日期。在訂單中，訂單編號具有 唯一性。每一張訂單裡的每一項產品都有其訂購數量之屬性。 每一項產品包含有屬性產品編號、產品名稱、單價。而在產品中，產品 編號具有唯一性。 每一位客戶可能都沒下過訂單，也可能下過多張訂單。 每一張訂單必定為某一位客戶且也僅能為一位客戶所下訂的。 每一張訂單包含有至少一項以上產品；每項產品可能被多張不同訂單所 訂購過，也可能未被任何訂單所訂購過。（每小題10 分，共40 分） 試依上述說明，為該公司畫出一實體關聯圖（Entity Relationship Diagram, ER Diagram）。該實體關聯圖需標出每一實體的名稱、屬性、 主鍵屬性（Key attribute）、每一關係（Relationship）及其基數性 （cardinality）。 試為該實體關聯圖（ER Diagram），決定出最簡化之各關聯表格。需描 述出每一表格的名稱、屬性（attribute）、主要鍵（primary key）及外來 鍵（foreign key）。 試寫出一SQL 程式片段，為每一張訂單所採購之每一項產品，列印出 該訂單編號、產品名稱及採購金額。 試寫出一SQL 程式片段，為每一張訂單列印出該訂單編號及該訂單所 採購總金額。

QuickSort 和MergeSort 是常見的排序演算法，各自有優點與缺點。 假設你負責設計一個「線上圖書目錄系統」，需要對50 萬筆已經按照 「出版年份」由大到小排序的書籍資料，重新依照「作者名稱」排序， 讓使用者能快速找到作者撰寫的書，但同時需要保持同一作者撰寫的 書籍能依據原本出版年份順序排列。根據QuickSort 和MergeSort 兩 種演算法的特性，你會選擇那一種演算法？為什麼？（10 分） 有一個數列[39, 18, 61, 46, 11, 2, 24, 33]，利用QuickSort（以第一個元 素為基準）進行由小到大的排序，請寫出並說明每一次循環的結果。 （10 分） 與上面問題同一個數列，利用MergeSort 進行由小到大的排序，請寫 出並說明每一次循環的結果。（10 分）

L1 為一由小而大排序之資料串列，L2 為一由大而小排序之資料串列，其 分別含有N1 與N2 筆資料，且N1, N2≫0：（每小題10 分，共20 分） 請設計出一最佳演算法，以能最快速查詢一資料D 是否存在於資料串 列L1 或L2 內。 並求出該演算法之時間複雜度（請越精確估算越佳）。

資料庫中有一個資料表Books，包含以下欄位BookID（書籍編號）、Title （書名）、Author（作者）、Publisher（出版社）、PubYear（出版年份）、 ISBN（國際標準書號），其中BookID 為資料表的主鍵。 請寫一個SQL 查詢，尋找張曼娟於2020 年出版的書籍名稱與出版社。 （10 分） 請說明下列SQL 語法之查詢過濾條件與輸出欄位為何？（10 分） 請以JOIN 指令，利用自我關連的概念，改寫上面的查詢。（20 分） SELECT Title, Author, Publisher FROM Books WHERE PubYear IN (SELECT PubYear FROM Books WHERE Author = '村上春樹' AND Publisher = '時報出版公司');

請撰寫一演算法，透過堆疊（stack）以計算出一後序式數學運算式（Postfix Expression）（例如"E=23*5+"）之結果。假設運算式中只含加、減、乘、 除（+, -, *, /）四種運算子（operator），及0, 1, …, 9 十種運算元（operant）。 （10 分）

應用適當的密碼學機制，可確保資料的機密性（confidentiality）、完整性 （integrity）、鑑別性（authenticity）、不可否認性（non-repudiation）之安 全目標。 試解釋何謂機密性、完整性、鑑別性、不可否認性。（8 分） 若A 欲將機密資料D，透過網路傳送給B。請透過雜湊（Hash）函式 及RSA 加密法，設計一資料加密機制，以確保機密資料之機密性、完 整性、鑑別性。（10 分） 若A 欲將一電子合約D，透過網路傳送給B 簽章。請透過雜湊（Hash） 函式及RSA 加密法，設計一數位簽章機制，以確保電子合約之機密 性、完整性、鑑別性、不可否認性。（12 分）