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

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

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

資料庫中有一個資料表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 = '時報出版公司');

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