資訊處理 101 年資料處理概要考古題

一般資料庫系統之交易（transaction）需滿足什麼性質？（20 分）

假設資料庫運算的兩個交易，transaction_1 與transaction_2，有共用的資料項目x 跟 y。也就是說，兩個交易都分別有讀寫共用資料的動作。例如，一個是{read(x), read(y), write(y), write(x)}，而另一個交易為{read(y), write(y), read(x), write(x)}。類 此的交易運算表示方式，一個包含兩個交易的排程（schedule），在什麼條件情況 下是不允許並行處理（concurrent execution）？又在什麼情況下是允許並行處理？ 除了敘述緣由外，請分別舉例說明。（20 分）

專有名詞說明（含功能或特點）： 數位憑證（Digital Certificate）（5 分） 資料庫正規化（Database Normalization）（5 分） 強制性存取控制（Mandatory Access Control）（5 分） 完整二元樹（Complete binary tree）（5 分） XML（eXtensible Markup Language）（5 分）

購物資料如下：交易編號、付款方式、付款金額、交易時間、會員編號、姓名、送 貨地址、會員生日、商品編號、商品名稱、定價、數量等。現在想對該資料進行正 規化（normalization），請說明基本正規化的動作及最終的關聯綱目（schema）。 （20 分）

關於資料庫系統的設計，我們常需先定義資料的綱要（schema），請問綱要的作用 為何？在關聯式資料庫與物件導向式資料庫中，物件導向式資料庫比關聯式資料庫 較具優勢之處為何？在考慮關聯式的資料庫設計時，我們常會因正規化的需要，將 資料表作分解（decomposition）的動作。比如說，一個關於公司人員的資料表，假 設該表原包含三個欄位（名字、職稱、部門），若資料庫設計者想將其分成兩個表 格：（名字、職稱）與（職稱、部門），請問如此分解是好的正規化分解嗎？為什 麼？請進一步說明藉由資料表分解，已達到正規化的目的為何？（20 分）

對資料排序（Sorting）中的選擇排序（Selection sort）與快速排序（Quick sort）， 試說明： 兩種排序之演算法及比較兩者特點？（10 分） 以如下六個數：23，12，45，9，78，11，解說這兩種排序演算法之動作（由小 到大排序）？（10 分）

假設有一個陣列score[]儲存同學的成績，撰寫程式 找出最低的成績，並指出其 陣列索引 計算全班的平均分數 列印出所有成績並分別指出其名次（成績最高 者，名次為1）。（30 分）

請回答下列問題：（每小題5 分，共20 分） 資料結構中，樹（tree）的結構與圖（graph）的結構有何差別？ 在一個有根節點（root node）的樹，其節點（node）的數目與邊（edge）的數目 有何關係？ 在沒方向性的連接圖（connected graph）中，一個節點的度數（degree）定義為該 節點連接的邊的個數。請問其節點的度數與邊的數目有何關係？ 請分別舉出兩個樹結構與圖結構在電腦應用中實際的例子。

如要進行設計某客運公司司機員與路線之資料庫查詢系統，使用者對該資料庫的可 能查詢有：某司機員，在某段日期，行駛那些路線？某路線，會經過那些站 牌、及該站牌之經緯度？某日，行駛某路線之司機員姓名及電話號碼？ 試畫出此資料庫之實體關係圖（Entity-Relationship diagram）。（10 分） 註：如要額外外加某些限制，請在答案中說明。 依上述實體關係圖，設計關聯表表格綱要（Schema）並正規化到「第三正規型式」 （Third Normal Form）。（10 分） 依上題關聯表表格綱要（Schema），使用SQL 語法進行，司機員A，在日期s 到日期t 間，行駛過那些路線的查詢？（10 分）

說明成功且安全的網際網路交易的四項基本要求為何？電子商務存在之威脅為 何？網路攻擊的種類為何？（30 分）

在通訊網路上使用的資料交換技術，以電路交換（circuit switch）與封包交換 （packet switch）為主。請以線路的使用效率與資料傳輸的延遲因素，說明兩種技 術間的差異性？在TCP/IP 網路中，傳輸層的TCP 與UDP 的傳輸協定，何者可以 稱為電路交換技術的應用？為什麼？（20 分）

試回答下列問題： 何謂Ethernet 與Internet？（10 分） 若路由器（Router）執行RIP 路由協定（Routing Information Protocol），問： 路由器（Router）功能？（5 分） RIP 運作程序為何？（10 分）

假設三種演算法的複雜度函數分別為f1(n) = n2, f2(n) = 2n, f3(n) = log(n!)。將此三個函 數依複雜度的高低順序排序，其結果為何？請說明原因？假若g(n) = 1+ (1/2) + (1/22) + … + (1/2n-1)。 請問“g(n) = O(n)＂是否正確？為什麼？（註1：此題中n為正整 數，註2：O(n)表示big-O of n。）（20 分）