加載中. ..
PDF
113
年特種考試地方政府公務人 員及
離 島 地 區 公 務 人 員 考 試 試 題
考 試 別：地方政府公務人員、離島地區公務人員考試
等 別：三等考試
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號：
34560
51250
頁次：
3
－
1
一、考慮下面以虛擬碼（Pseudocode）表示的遞迴演算法，請回答相關問題：
Algorithm Q(n)
if n＝1
return 1
else return Q(n－1)＋2n－1
列出虛擬碼中 Q(n)的遞迴關係式，並說明此虛擬碼最終計算的是什麼？
（5分）
用遞迴函式表示此虛擬碼所使用的乘法運算次數，並用漸進式符號
Big-O 表示此遞迴函式的成長速率。（5分）
以遞迴函式表示此虛擬碼的執行時間 T(n)並說明其時間複雜度（以
Big-O 表示）。（10 分）
二、請回答下列關於二元樹（Binary Tree）的問題：
一個算術運算式（Arithmetic Expression）可以用一個二元樹表示，稱
為算術運算樹（Expression Tree），請將下列算術運算式以算術運算樹
表示。（5分）
( ( ( 5 + 1 ) 3－(7 + 2 ) ) / ( ( ( 28 ) + 5 ) / 7 ) )
請判斷下列敘述是否正確：（5分）
“一個算術運算樹是一個滿二元樹（Full Binary Tree, or Proper Binary
Tree）”
子題中的算術運算式是何種順序的運算表示式？請利用其算術運
算樹將此運算式表示為一前序表示式（Preorder Expression），並說明
其過程。（5分）
請敘述如何以子題的算術運算樹計算出算術運算式的值，並逐步表
示其過程。（10 分）
代號：
34560
51250
頁次：
3
－
2
三、在許多應用中，往往需要以物件的優先權來進行處理，為了區別物件的
優先順序，我們可以簡單地賦予物件一個鍵值（Key）來代表優先權，此
鍵值通常是一個數值可以用來區別物件前後順序。在此，我們考慮物件
的鍵值是一個數值而其值愈小，物件的優先權愈高，優先佇列（Priority
Queue）則是一種以物件的優先權來管理物件的資料結構。
請說明優先佇列的抽象資料型態（abstractdatatype,ADT）定義。（10 分）
給定一個最小二元堆積（MinimumHeap）H與一個鍵值 k，在 H中快速
地找出所有鍵值小於或等於 k的資料物件。請描述一個有效的方法，此
方法所花的時間（或運算量）與欲找出的資料物件之數量成線性比例。
（5分）
四、關於紅黑樹（Red Black Tree）與(2,4)-樹((2,4)-Tree)：
請分別說明紅黑樹與(2,4)-樹的定義。（10 分）
考慮下面的紅黑樹（實線節點代表黑色節點，虛線節點代表紅色節
點），代表節點的字元符號可視為鍵值，請說明如何將此紅黑樹轉換為
一個(2,4)-樹，並將其結果畫出。此外，請申論轉換的(2,4)-樹是否唯一。
（10 分）
請說明為何一個有 n個節點（鍵值）的紅黑樹其高度是 O(logn)。（5分）
代號：
34560
51250
頁次：
3
－
3
五、下面的矩陣 M是表示一個無向圖 G=(V,E)的相鄰矩陣（Adjacency
Matrix），V與E分別為節點與邊的集合：
a b c d e f g
a0 1 0 1 1 1 0
b1 0 1 0 1 1 0
c0 1 0 0 0 1 1
d1 0 0 0 0 0 1
e1 1 0 0 0 0 0
f1 1 1 0 0 0 1
g0 0 1 1 0 1 0
請畫出此無向圖 G。（10 分）
若以字母順序為考量對 G進行廣度優先搜尋（Breadth-First Search,
BFS），因此將由節點 a開始，請繪出尋訪完後所產生的 BF 樹（Breadth-
First (BF) Tree）。（5分）