加載中. ..
PDF
106年公務人員特種考試警察人員、一般警察
人員考試及106年特種考試交通事業鐵路
人員、退除役軍人轉任公務人員考試試題 代號：70770 全一張
（正面）
考試別： 鐵路人員考試
等別： 高員三級考試
類科別： 資訊處理
科目： 資料結構
考試時間 ： 2 小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
一、串列（list or sequence）是一個函數，從整數的子集合對應到另一個集合。請寫出
兩個集合 s1,s2 及一個函數 f來定義串列 [2,2,1,3]。（10 分）
分別使用 Java ArrayList 及Java LinkedList 來實作上述的串列，請分別畫出草圖
（sketch）表示之（注意：兩種資料結構的草圖上，都要註明索引 index）。（10 分）
二、對下面的圖（graph），請分別使用佇列（queue）及堆疊（stack），從 A出發，分別
進行廣度優先走訪（breadth-first traversal）及深度優先走訪（depth-first traversal），
請寫出兩種走訪結果。注意：請依字母順序（alphabetical order）處理。而且，要寫
出走訪時佇列及堆疊等資料結構的內容。（20 分）
B
A C
E D
三、請寫出下面 m1,m2,m3,m4 四個程式的 Big O 時間估算。（20 分）
public static int m1(int N) {
int x = 0;
for (int i = 0; i < N; i++)
x++;
return x;
}
public static int m2(int N) {
int x = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < i; j++)
x++;
return x;
}
public static int m3(int N) {
if (N == 0) return 0;
int x = 0;
for (int i = 0; i < N; i++)
x += m3(N-1);
return x;
}
public static int m4(int N) {
if (N == 1) return 3;
return 3 + m4(N/2);
}
106年公務人員特種考試警察人員、一般警察
人員考試及106年特種考試交通事業鐵路
人員、退除役軍人轉任公務人員考試試題 代號：70770 全一張
（背面）
考試別： 鐵路人員考試
等別： 高員三級考試
類科別： 資訊處理
科目： 資料結構
四、將下列資料 60, 30, 80, 20, 50, 70, 90, 40, 35
依序分別加入原本為空的紅黑樹（red-black tree）及 2-3-4 樹，請分別寫出結果。（20 分）
注意：紅黑樹的紅色（Red）節點，請註明 R，例如：資料 30 的節點是紅色的，則
請寫 30R。
注意：2-3-4 樹的節點要分裂（split）時，最小資料放在左子節點，最大兩個資料放
在右子節點，次小資料放在父節點。
五、將下列資料 60, 30, 80, 20, 50, 70, 90, 40, 35
依序分別加入原本為空的最小堆積（min heap）及空的陣列（array）中，請分別寫
出結果，表示資料儲存的情形。（10 分）
承題
，分別自最小堆積及陣列中刪去 30，刪除資料後，需重新建立最小堆積。
而陣列中所有在此資料右方之資料必須向左移，不可留空白，請分別寫出結果。
（10 分）