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 分）