加載中. ..
PDF
108年公務人員特種考試關務人員、身心障礙人員考試及
108年國軍上校以上軍官轉任公務人員考試試題
考試別
：
關務人員考試
等別
：
三等考試
類科
：
資訊處理
科目
：
資料結構
考試時間
：
2小時
座號：
※注意：
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
代號：
10460
頁次：
3
－
1
一、下列程式函式 doit()以C語言語法呈現，用以對雙向鏈結串列（doubly
linked list）進行處理。請依據該函式回答問題。
void doit(struct node **head){
struct node *temp = NULL;
struct node *current = *head;
while(current != NULL){
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if(temp != NULL)
*head = temp->prev;
}
若X指向一個雙向鏈結串列如下，其中 X->prev 指向 NULL，X->next
指向資料為 21 的節點。請顯示並說明 doit（&X）執行過後該串列變化
結果。（10 分）
若X指向一個雙向鏈結串列如下，其中 X->prev 指向資料為 17 的節點，
X->next 指向資料為 35 的節點。請顯示並說明 doit（&X）執行過後該
串列的變化結果。（5分）
若X指向一個環狀雙向鏈結串列（circular doubly linked list），請說明
doit（&X）是否仍能順利執行。（5分）
NULL
NULL
X
17
21
35
74
95
NULL
NULL
X
17
21
35
74
95
代號：
10460
頁次：
3
－
2
二、給定 T為一個以陣列表示的二元搜尋樹（binary search tree）。
若有一些介於 1及1,000 的正整數被儲存於 T，且要搜尋數字 364，請
說明搜尋過程是否有可能為 3, 400, 388, 220, 267, 383, 382, 279, 364？
（5分）
若有一些介於 1及1,000 的正整數被儲存於 T，且要搜尋數字 364，請
說明搜尋過程是否有可能為 926, 203, 912, 241, 913, 246, 364？（5分）
若對 T進行前序遍歷（pre-order traversal）的結果為 30, 20, 10, 15, 25, 23, 39,
35, 42。請說明若以後序遍歷（post-order traversal），結果為何。（5分）
若對T進行後序遍歷（post-order traversal）的結果為25, 20, 34, 37, 31, 49,
46, 57, 60, 52, 41。請說明若以中序遍歷（in-order traversal），結果為何。
（5分）
請說明可將二元搜尋樹 T轉換為最小堆積（min heap）的程序為何？（10 分）
三、給定以相鄰矩陣（adjacency matrix）表示的圖 G，矩陣中的數字為相鄰兩
節點間的距離，若空白則代表兩節點不相鄰。
G
a
b
c
d
e
f
g
h
j
a
1
6
5
b
1
6
c
6
6
7
3
d
5
2
10
e
7
12
f
3
2
8
g
10
7
3
h
12
8
7
8
j
3
8
圖G
請說明若以 Kruskal’s 演算法建立最小生成樹（minimum spanning tree）
的過程中，依序被加入生成樹的邊。（5分）
請說明若以 Prim’s 演算法建立最小生成樹（minimum spanning tree）的
過程中，依序被加入生成樹的邊。（5分）
請說明 Dijkstra’s 演算法的用途，並說明該演算法應用上的限制。（10 分）
請說明將圖 G從f節點開始執行 Dijkstra’s 演算法的過程並顯示節點加
入的順序。（10 分）
代號：
10460
頁次：
3
－
3
四、請將所給定數字藉由所指定雜湊函數依序置入雜湊表
若雜湊函數為 H(k) = k mod 11，並以線性探測（linear probing）解決溢
位（ overflow）問題，請顯示將 15, 23, -12, 3, -8, 8, 9, 11, -3, -5, 14, 10, 25,
12, 0, 21 依序置入 11 桶（buckets）x 2 槽（slots）雜湊表的最終結果。
（10 分）
若雜湊函數為 H(k) = k mod 7，並以平方探測（quadratic probing）解決
溢位（overflow）問題，請顯示將 15, 23, -12, 3, -8, 8, 9, 11, -3, -5, 14, 10, 25,
12 依序置入 7桶（buckets）x 2 槽（slots）雜湊表的最終結果。（10 分）
A[.]
0
1
2
3
4
…
槽1
槽2