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

下圖為一有向權重圖（weighted directed graph），每條邊上的數字是其權重（weight）。 試回答下列問題（注意，各小題之間基本上互相獨立，可獨立作答）。 （每小題10 分，共50 分） A C B E D 若欲以資料結構的連結串列（linked list）方式來表達此圖，請圖示說明此連結串 列裡的每個節點（node）的結構是如何？ 並繪出表達此圖的完整連結串列。 若欲以資料結構的矩陣方式來表達此圖，請以圖示說明該矩陣的內容。 若欲以關連式資料庫（relational database）的一個關連（relation）來儲存此圖， 請寫出此關連的所有欄位（attribute）及所有記錄（record）。 假設子題中關連的名字為XYZ。針對所有連接二個同向的相鄰邊（edge）的二 個端點，今欲列出所有這樣的端點配對，請以SQL 語言寫出此查詢。例如圖中 邊AB 是A 指向B，邊BC 是B 指向C，而且有B 為中間節點，因此邊AB 與邊 BC，就是二個同向的相鄰邊，故A 與C 就是這二個同向相鄰邊的二個端點。故 （A,C）這對組合就是答案之一。注意，A 與C 雖然也經由邊AC 直接相連，但 這並不影響邊AB 與邊BC 是二個同向相鄰邊的事實。同樣的，邊AD 與邊DB 也是二個同向的相鄰邊，因此 （A,B） 這對組合也是答案之一。但注意，AB 與DB 並非同向相鄰邊，因為他們同指向B，而沒有中間點。 列出此圖的關鍵路徑（critical path），並給出此路徑上之權重和。

SSL（Secure Sockets Layer）為一提供應用程式通訊安全與信賴的協定，請說明： SSL 如何建立使用者與服務伺服器間的安全通道，尤其是秘密鑰匙（secret key） 的建立方式？SSL 與SET 的不同處為何？（20 分）

請將SQL 查詢“Select A, B, C From X, Y Where X.D = Y.E”用關連式代數（relational algebra）表達出來。（10 分）

無線區域網路（Wireless LAN)將推動網際網路進一步的發展，請說明無線區域網路 有何優勢？（10 分）

請回答下列問題：（每小題10 分，共20 分） 資料庫的設計裡要針對每個關連（relation）作正規化（normalization）的動作。 為什麼要正規化，如果沒有作正規化，會造成什麼問題？ 什麼是同步控制（concurrency control）裡的可序向化（serializability）？

一個鏈結串列使用C 語言宣告如下： typedef struct node { int data; struct node *next; } NODE; 假設現在已經產生一個共有n 個節點的NODE 的鏈結串列，已知變數pointer 是指 向該串列前端（head）之指標，請撰寫一程序將pointer 所指向的串列，整個串列進 行反轉。（15 分）

請回答下列問題：（每小題10 分，共20 分） 堆疊（stack）和佇列（queue）二種資料結構的區別是什麼？二者分別適合在什 麼應用（或者說 “場合”）中使用，試各舉一例來說明。 關連式資料庫裡限定用戶權限的方法之一，是透過使用景觀（view）的方式。 試簡述如何透過景觀來限制用戶使用資料的權限。

給定一數列54, 65, 50, 45, 89, 40, 25, 31, 72, 78。（15 分） 畫出對應二元樹（Binary Tree）。 請將這二元樹轉換成堆集樹（Heap Tree）。 在使用堆集排序（Heap Sort）的前二個步驟後可輸出89 和78 兩數，請畫出在經 過該二個步驟後的堆集樹。

假設某圖書館之關聯資料庫中有七個關聯資料表，其資料綱要（data schema）如下， 底線代表主要鍵。 BOOK（BookId, Title, PublisherName） BOOK_AUTHORS（BookId, AuthorName） PUBLISHER（Name, Address, Phone） BOOK_COPIES（BookId, BranchId, No_Of_Copies） BOOK_LOANS（BookId, BranchId, CardNo, DataOut, DueDate） LIBRARY_BRANCH（BranchId, BranchName, Address） BORROWER（CardNo, Name, Address, Phone） 寫出以下查詢之SQL：（40 分） 該圖書館的所有分館各擁有多少本書名為“三國演義＂的書？ 現在那些借閱人在各分館借出“三國演義＂這本書？ 現在那些借閱人在各分館有逾期未還的書？ 該圖書館擁有多少不同的書籍？