101年公務人員普通考試四級 資料處理概要

假設資料庫運算的兩個交易，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）？又在什麼情況下是允許並行
處理？除了敘述緣由外，請分別舉例說明。

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

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

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

假設三種演算法的複雜度函數分別為2
f₁(n) = n² , f₂ (n) = 2ⁿ , f₃ (n) = log(n!)。將
此三個函數依複雜度的高低順序排序，其結果為何？請說明原因？假若
g(n) =1+ (1/ 2) + (1/ 2² ) +L+ (1/ 2ⁿ⁻¹)。請問“g(n) = O(n)”是否正確？為什麼？
（註1：此題中n 為正整數，註2：O(n)表示big-O of n。）