加載中. ..
PDF
102年特種考試地方政府公務人員考試試題 代號：34180
等 別： 三等考試
類 科： 資訊處理
科 目： 資料結構
考試時間： 2 小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
全三頁
第
一
頁
一、請參考圖 1：
由a點出發，做 depth-first traversal（深度優先拜訪），請問那些節點（node）不
會被訪問到？（3分）
由a點出發，做 breadth-first traversal（寬度優先拜訪），請問那些節點（node）
不會被訪問到？（2分）
假設圖 1代表 heap 上各個節點（node）及其相互指向的關係。p、q、r三節點代
表全域變數（global variables），其他的節點代表 heap 上的記憶體區塊。如果
p→a的指標被消除，那些節點會變成無用的垃圾節點？你必須詳細描述尋找垃圾
節點的方法及所需之資料結構。你的演算法只能從 a節點出發，它必須指出所有
的垃圾節點，並且你的演算法只能在每一個節點儲存很少量的資料。請問你的演
算法必須在每一個節點儲存那些資料？（15 分）
二、定義如下的函數 F：
如果 x是偶數，則 F(x) = x/2;
否則 F(x) = F(F(3x + 1))
請問 F(11) =？（5分）
請證明對於任何正整數 w，我們都可以在有限時間內計算 F(w)。（提示：每個奇
數可以寫成(2i + 1)2k – 1 的形式，再採用數學歸納法來證明。）（15 分）
（請接第二頁）
圖
1
一個有向圖
（a directed graph）
a
p
b
d
c
x
q
kl
j
g
ef
m
n
r
h
102年特種考試地方政府公務人員考試試題 代號：34180
等 別： 三等考試
類 科： 資訊處理
科 目： 資料結構
全三頁
第
二
頁
三、Knuth，Morris 及Pratt 發明了一個快速的字串比對方法（string pattern matching）。
他們的方法採用一個失敗函數（failure function）。失敗函數其實就是一個輔助的資
料結構，用來加速比對。請依他們的方法計算下列字串的失敗函數。你必須說明失
敗函數的定義為何，以及失敗函數如何加速比對。（15 分）
index 0 1 2 3 4 5 6 7 8 9
pattern a b b a b c a b b a
failure ？ ？ ？ ？ ？ ？ ？ ？ ？ ？
四、請參考圖 2。每一條線段上的數字代表兩節點間的距離。請找出 a節點到 k節點的
最短路徑的長度。並請說明你的方法如何應用在非常大型的圖裡。（15 分）
五、請參考圖 3。圖 3是一個 activity-on-edge 網路。在 activity-on-edge 網路中，一項計
畫可以分成很多件工作，每一件工作由一條線段代表，線段上的數字代表該工作所
需的時間（以工作日為單位），線段的箭頭代表工作的先後關係。例如在圖 3中，
ab 及db 線段代表的工作完成之後，bc、be、及 bf 線段代表的工作才可以開始進行，
其他的先後關係依此類推。a節點是起點，k節點是全部工作的完成點。請找出 k
節點的最早完成時間及關鍵路線（critical path）。並請說明你的方法如何應用在非
常大型的圖裡。（15 分）
（請接第三頁）
圖
3 Activity-on-edge
網路
圖
2
最短路徑
a
22 21
11
11
21
12
12 21
13
13
19 27 23
23
5
14
b
c
d
e
f
gh
k
a
b
c
d
e
f
gh
k
16 11
12
13
17
23
27
21
41
10
26
49
4
53735
14
37
102年特種考試地方政府公務人員考試試題 代號：34180
等 別： 三等考試
類 科： 資訊處理
科 目： 資料結構
全三頁
第
三
頁
六、在一個二元樹裡有許多節點（nodes）。假設每一個節點的資料結構如下圖：
其中 DATA 欄位為該節點的資料。LEFT 欄位為指向左方子樹的指標變數。RIGHT
欄位為指向右方子樹的指標變數。
如果節點 p沒有左方子樹，其 LEFT 欄位為空指標（null pointer）。同理，如果節
點p沒有右方子樹，其 RIGHT 欄位為空指標（null pointer）。
如果一個二元樹有 n個節點，那麼它有幾個空指標？（5分）
我們可以利用原本是空指標的欄位來儲存引線（threads）。二元樹加上引線的結
果稱為引線樹（threaded trees）。當然我們必須在各節點再加上兩個欄位 LTAG
及RTAG，共 5個欄位，如下圖所示：
如果 LEFT 欄位代表一般的節點指標，則 LTAG = 0。如果 LEFT 欄位代表引線指標，
則LTAG = 1。同理，如果 RIGHT 欄位代表一般的節點指標，則 RTAG = 0。如果
RIGHT 欄位代表引線指標，則 RTAG = 1。
請將下圖的二元樹加上適當的引線指標，讓它變成引線樹，並請繪圖標出 A到I共
9個節點中所有引線指標指向的節點。（10 分）
LEFT DATA RIGHT
L
TAG LEFT DATA RIGHT RTAG
A
BC
DE
FGH
I