加載中. ..
PDF
100 年特種考試地方政府公務人員考試試題 代號：
等 別： 四等考試
類 科： 統計、資訊處理
科 目： 資料處理概要
考試時間： 1小時 30 分 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
全一頁
41320
43720
一、下圖為一有向權重圖（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）的方式。
試簡述如何透過景觀來限制用戶使用資料的權限。