阿摩線上測驗 登入

95年 - 095年專門資料結構（包括資料庫）#49506

科目：公職◆資料結構 | 年份：95年 | 選擇題數：0 | 申論題數：8

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (8)

一、請使用 C 語言寫出求任何兩數 m 與 n 之最大公因數（Greatest Common Divisor, GCD） 的 Recursive 與 Non-recursive 演算法。（20 分）
【已刪除】二、求下列程式片斷中，函數 A（i, j, k）的執行次數。（20 分）
【已刪除】三、請分別使用 Prim’s 演算法與 Kruskal’s 演算法，將下列網路簡化成最小成本的擴張 樹（Minimum cost spanning tree）。（20 分）
四、資料庫管理的檔案相當大時，根據這個檔案所建立的索引也會相當大，為了減少進 出輔助儲存體的次數，必須將索引根據層次（Layers）來建立，現在有一棵 B-Tree ，其階度為 m，要儲存 n 個鍵值（Key），最多需要多少個層次？如果要尋找一個 鍵值，請問最多需要進出儲存體多少次？（20 分）
⑴說明 Static data structures 與 Dynamic data structures 的優缺點各為何。
⑵使用遞迴（Recursive）演算法，解決河內塔（Tower of Hanoi）問題。
⑶針對一個高度為 h 的 m-ary 樹（假設 root 節點的 height=1），求出其節點數目的 最大值。
⑷舉例解釋在資料庫管理系統中，序列化排程（serial schedule）與非序列化排程 （non-serial schedule）的不同，對於資料庫的一致性有何影響。