加載中. ..
PDF
101
年公務人員特種考試外交領事人員外交行政人員考試、
101
年
公務人員特種考試國際經濟商務人員考試、
101
年公務人員特種考
試法務部調查局調查人員考試、
101
年公務人員特種考試國家安全
局國家安全情報人員考試、
101
年公務人員特種考試民航人員考
試、
101
年公務人員特種考試經濟部專利商標審查人員考試試題
代號：
考 試 別： 專利商標審查人員
等 別： 三等考試
類 科 組： 資訊工程
科 目： 資料結構（包括資料庫）
考試時間： 2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
全一頁
80460
一、選擇排序（selection sort）演算法常用於資料量不大的場合。試回答下列問題：
使用下列資料項說明選擇排序演算法的動作：23、15、45、12、9、3、65、11。
（5分）
假設欲排序的資料項以陣列（array）方式儲存，試寫一個函式（function）執行選
擇排序演算法。（10 分）
選擇排序演算法的時間複雜度（time complexity）為何？（5分）
二、 雙端優先權佇列（double-ended priority queue）為一個能夠支援下列運算動作的資料
結構：插入一個任何鍵值（key）的資料項、取出最小鍵值的資料項與取出最大鍵
值的資料項。今若欲以雙端的 heap（double-ended heap，稱為 deap）實現此資料結
構，試回答下列問題：（每小題 5分，共 20 分）
定義 deap 資料結構。
使用下列資料項建構一棵 deap 樹（deap tree）：1、23、12、67、54、34、19、
87、56、76、32。
說明如何將鍵值為 5的資料項插入上述 deap 樹中。
說明如何自
中的 deap 樹中刪除最小鍵值的資料項。
三、某軟體工程師欲設計一個堆疊（stack）資料結構，此堆疊需要 POP 與PUSH 兩個
函式（function）。由於先前他已經設計過排序資料陣列（sorted data array）與最小
優先權佇列（min-priority queue），因此他考慮使用這兩種資料結構之一實現需要
的堆疊資料結構。
排序資料陣列是否可以實現堆疊資料結構？若可以，請簡述如何實現 POP 與
PUSH 兩個函式及估算它們的時間複雜度。（10 分）
最小優先權佇列是否可以實現堆疊資料結構？若可以，請簡述如何實現 POP 與
PUSH 兩個函式及估算它們的時間複雜度。（10 分）
四、實體資料庫（physical database）設計為一個程序，以選取特定的檔案儲存結構及資
料庫檔案存取路徑，使能在各種不同的資料庫應用中達到優良的性能。試問在實體
資料庫設計中，必須考慮的準則（criteria）為何？（20 分）
五、 目前分散式資料管理（distributed data management）的趨勢係圍繞於網際網路（the
Internet），在這個趨勢中，雲端計算（cloud computing）與 P2P （peer-to-peer）資
料庫為兩個重要領域。
何謂雲端計算？試定義之。（10 分）
在雲端計算環境中，分散式資料管理系統的重要設計特性為何？（5分）
何謂 P2P 資料庫系統？試定義之。（5分）