加載中. ..
PDF
1
0
8
年特種考試地方政府公務人員考試試題
等 別：三等考試
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號：
34280
頁次：
2
－
1
一、對下列三個程式片段，請使用 Big-O 符號，分別估計其最長執行時
間 （worst time）。程式片段中，S代表一段沒有與 n相關的迴圈
（no n-dependent loops）。
for (int i = 0; i * i < n; i++) （5分）
S
for (int i = 0; Math.sqrt (i) < n; i++) （5分）
S
int k = 1; （10 分）
for (int i = 0; i < n; i++)
k *= 2;
for (int i = 0; i < k; i++)
S
二、有下列資料元素（data elements），其數值越小則優先權（priority）越高，
請分別依序將各元素加入（add）優先佇列（priority queue）中，且分別
以下列三種資料結構實作之。
90, 10, 80, 20, 70, 50, 40, 30
用雙向鏈接串列（doubly-linked list）來實作此優先佇列，請畫出其資
料結構圖。（6分）
用紅黑樹（red-black tree）來實作此優先佇列，請畫出其資料結構圖。注
意:紅節點請標示 R，例如 20R 表示其值為 20 的紅（Red）節點；黑節
點則請標示B，例如50B 表示其值為50 的黑（Black）節點。（7分）
用最小堆積（min heap）來實作此優先佇列，請畫出其資料儲存的陣
列（array）圖。注意:陣列索引（array index）由左向右遞增。（7分）
代號：
34280
頁次：
2
－
2
三、下圖為一棵 2-3-4 樹。
請畫出對應的紅黑樹（red-black tree）。請參閱上題紅黑樹節點的標示
說明。（6分）
首先，插入（insert）33；接著，刪去（delete）78。請分別畫出對應
的 2-3-4 樹與紅黑樹。（14 分）
四、下面的無向圖（undirected graph）表示四個人的關係，如張三與李四有
關係，這二人之間有邊（edge）相連，則可走訪。括弧內為人名縮寫，
如張三（Chang San）的縮寫為 CS。若同時有兩個以上的人可處理，則
先處理人名縮寫的字母順序較小者。
由張三（CS）出發，用佇列（queue）做廣度優先搜尋（breadth-first search）
走訪所有人，請寫出走訪順序的中文人名。（10 分）
由張三（CS）出發，用堆疊（stack）做深度優先搜尋（depth-first search）
走訪所有人，請寫出走訪順序的中文人名。（10 分）
五、將下列六個鍵值:
33, 72, 71, 55, 112, 109
存入大小為 19 的雜湊表（a hash table of size 19）
雜湊函數 h為: h(key) = key mod 19
分別用下面兩種衝突處理方式（collision handler）：
間隔為 1（offset of 1）（12 分）
間隔為商（quotient-offset）（8分）
請分別寫出兩個雜湊表；並在間隔為 1的雜湊表上，標示出一次聚集
（primary clustering）。
40 62 83
10 20 31 45 55 70 78 90 92
李四(LS)
趙六(CL)
王五
(WW)
張三
(CS)