統計 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），並給出此路徑上之權重和。

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

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

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

假設某圖書館之關聯資料庫中有七個關聯資料表，其資料綱要（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 分） ㈠該圖書館的所有分館各擁有多少本書名為“三國演義＂的書？ ㈡現在那些借閱人在各分館借出“三國演義＂這本書？ ㈢現在那些借閱人在各分館有逾期未還的書？ ㈣該圖書館擁有多少不同的書籍？