阿摩線上測驗
登入
首頁
>
公職◆資料結構
> 103年 - 103年高等資料結構(包括資料庫)#43186
103年 - 103年高等資料結構(包括資料庫)#43186
科目:
公職◆資料結構 |
年份:
103年 |
選擇題數:
0 |
申論題數:
10
試卷資訊
所屬科目:
公職◆資料結構
選擇題 (0)
申論題 (10)
⑴線性結構(linear structure)。(5 分)
⑵二元搜尋樹(binary search tree)。(5 分)
⑶最大堆積(max heap)。(5 分)
⑴試述靜態雜湊(static hashing)設計時所需考量的課題、優缺點、使用上的限制。 (10 分)
⑵試述動態雜湊(dynamic hashing)之設計及結構,並申論是否能解決上述⑴之缺 點及使用上的限制。(10 分)
⑴試以磁碟讀取寫入(disk I/O access)的次數評論排序效能與資料量 N 頁、記憶體 工作區大小 B 頁的關聯。(10 分)
⑵以資料量 N = 136 pages,記憶體工作區 B = 5 pages 為例說明。(10 分)
⑴試算內部節點的量級 m(branches 數 or order in internal node)、葉節點的量級 n (branches 數 or order in leaf node)及 B
+
- tree 的高度 H。m,n 以 b,k,p,r 等符 號表示,H 以 N,m,n 等符號表示。(12 分)
⑵請就單筆資料搜尋(search)、插入(insert)、刪除(delete)操作及範圍搜尋 (range query),評述其操作成本及效能。(13 分)
五、網際網路可視為一有方向性的圖(directed graph),網頁的 URL 是節點(node), 網頁到網頁的鍵接是邊(edge)。穿越(traversal)網頁有各種不同的瀏覽次序,試 提出二種穿越(traversal)方法可遍歷所有可瀏覽到的網頁而不重覆,並評論其時 間複雜度。如有需要額外的輔助資料結構,請說明其使用方法。(20 分)