104年 - 104年升官資料結構#41097

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

試卷資訊

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

選擇題 (0)

申論題 (12)

⑴在 A 所指向節點之右鏈結（rlink）插入由 B 所指向的一個新節點。分）（6

⑵刪除 A 所指向的節點，並將 A 指向其原節點之右鏈結（rlink）節點。只能使用 A 指標。分）（6

⑶刪除整個串列，完成後 A 應指向 NULL。只能使用 A 指標。（13 分）

⑴若該雜湊表有 750 桶（buckets）× 4 槽（slots），不管採用何種雜湊函數，1000 筆資料都放入雜湊表後，該表之載入密度（load factor）為何？（7 分）

⑵若要做到完整雜湊（perfect hashing），雜湊函數應該要有何特性？（8 分）

⑶假設建立雜湊表時若發生碰撞就採取線性探測法（linear probing）來放入資料，且在 1000 筆資料都放入該雜湊表後，搜尋每筆資料的平均所需查看（access）次數希望約為 2，在盡量不浪費空間的前提下，該雜湊表應該如何設計？請以「桶」（buckets）「槽」、（slots）「載入密度」、（load factor）等之數量加以敘述，並說明為何該設計符合平均查看次數之限制。（10 分）

⑴請畫出該陣列以二元搜尋法搜尋資料之二元搜尋樹（binary search tree）（5 分）。

⑵假設陣列內的資料量共有 1024 筆資料，則二元搜尋樹共會有幾層（最上層為第 1 層）？請說明。分）（5

⑶若是陣列中有兩個相鄰的數字對調位置（也就是只有此兩個數字順序錯誤），最多可能會有多少數字將無法以二元搜尋法成功找到？請說明。（15 分）

⑴找到並移除最高優先權印表工作的時間複雜度為何？排入新印表需求的時間複雜度為何？請以 Big-O 方式敘述。分）（5

⑵若所有印表機都尚未開機，而送進印表佇列的順序如後（數字代表該印表優先權）： 8, 18, 28, 38, 35, 25, 15, 5, 40, 1。請將該印表佇列以 SMMH 樹狀結構圖表示之。（15 分）

⑶承上題⑵，若 A₁ 開機，並處理了優先權最高的印表工作。請將印表佇列變化結果以 SMMH 樹狀結構圖表示之。分）（5