加載中. ..
PDF
104年公務人員升官等考試、104年關務人員升官等考試
104
年交通事業公路、港務人員升資考試試題
代號：26260 全一張
（正面）
等級： 薦任
類科（別）： 資訊處理
科目： 資料結構
考試時間： 2 小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
llink rlink llink rlink llink rlink
A
llink rlink
. . .
B
llink rlink
一、給定如下圖所示之環狀雙向鏈結串列（circular doubly linked list），並以 A指向其中
一個節點。請用類 C之虛擬語言（C-like pseudo code）完成下列動作。
在A所指向節點之右鏈結（rlink）插入由 B所指向的一個新節點。（6分）
刪除 A所指向的節點，並將 A指向其原節點之右鏈結（rlink）節點。只能使用 A
指標。（6分）
刪除整個串列，完成後 A應指向 NULL。只能使用 A指標。（13 分）
二、假設有 1000 筆資料將以雜湊法（hashing）放入雜湊表（hash table）。
若該雜湊表有 750 桶（buckets）×4槽（slots），不管採用何種雜湊函數，1000 筆
資料都放入雜湊表後，該表之載入密度（load factor）為何？（7分）
若要做到完整雜湊（perfect hashing），雜湊函數應該要有何特性？（8分）
假設建立雜湊表時若發生碰撞就採取線性探測法（linear probing）來放入資料，且
在1000 筆資料都放入該雜湊表後，搜尋每筆資料的平均所需查看（access）次數
希望約為 2，在盡量不浪費空間的前提下，該雜湊表應該如何設計？請以「桶」
（buckets）、「槽」（slots）、「載入密度」（load factor）等之數量加以敘述，並說明
為何該設計符合平均查看次數之限制。（10 分）
三、給定下列以陣列所表示之 16 筆有序數列。
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A[i] 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32
請畫出該陣列以二元搜尋法搜尋資料之二元搜尋樹（binary search tree）。（5分）
假設陣列內的資料量共有 1024 筆資料，則二元搜尋樹共會有幾層（最上層為
第1層）？請說明。（5分）
若是陣列中有兩個相鄰的數字對調位置（也就是只有此兩個數字順序錯誤），最多
可能會有多少數字將無法以二元搜尋法成功找到？請說明。（15 分）
104年公務人員升官等考試、104年關務人員升官等考試
104
年交通事業公路、港務人員升資考試試題
代號：26260 全一張
（背面）
等級： 薦任
類科（別）： 資訊處理
科目： 資料結構
四、給定 m個印表機共用一個印表佇列（printer queue）。印表機 A1, …, Ak每次都從印表
佇列選取優先權最高（優先權數字最大）的列印工作進行列印，印表機 Ak+1, …, Am
每次都選取優先權最低（優先權數字最小）的列印工作進行列印。每天需要列印工作
繁多，因此該印表佇列在選取優先權最高、最低及排入新印表需求的效率非常重要。
假設該印表佇列以對稱最小最大堆積（Symmetric min-max heap, SMMH）加以實作。
找到並移除最高優先權印表工作的時間複雜度為何？排入新印表需求的時間複雜
度為何？請以 Big-O 方式敘述。（5分）
若所有印表機都尚未開機，而送進印表佇列的順序如後（數字代表該印表優先權）：
8, 18, 28, 38, 35, 25, 15, 5, 40, 1。請將該印表佇列以 SMMH 樹狀結構圖表示之。
（15 分）
承上題
，若 A1開機，並處理了優先權最高的印表工作。請將印表佇列變化結果
以SMMH 樹狀結構圖表示之。（5分）