阿摩線上測驗
登入
首頁
>
公職◆資料結構
> 95年 - 095年專門資料結構(包括資料庫)#49506
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)的不同,對於資料庫的一致性有何影響。