加載中. ..
PDF
104年特種考試地方政府公務人員考試試題 代號：34380 全一頁
等別： 三等考試
類科： 資訊處理
科目： 資料結構
考試時間 ： 2 小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
一、二元搜尋法（binary search）使用 divide-and-conquer（分而治之）演算法技巧，對一
個已排序（sorted）且長度為 n的陣列 A[0:n−1]，進行資料搜尋，其最差時間複雜度
（worst case time complexity）可降到 Θ(log n)。
請使用 C或Java 語言，修改此二元搜尋法，使其能對未排序（unsorted）且長度為
n的陣列 A[0:n−1]，以 divide-and-conquer 技巧，進行二元化搜尋。（15 分）
請分析修改後的二元搜尋法其最差時間複雜度（worst case time complexity）以 order Θ
的方式表示。（5分）
（注意：不可將此陣列數值進行排序，請加註解說明程式碼作法）
二、請使用 C或Java 語言寫一副程式 void merge(int [] A, int [] B, int [] C, int n)，此副程式
將對兩個長度為 n且已依小到大排序的整數陣列 A與B，合併至長度為 2n 且依小到
大排序的整數陣列 C，此副程式的時間複雜度需為 Θ(n)。（20 分）
（注意：請加註解說明程式碼作法）
三、請說明使用何種資料結構及其演算法，可有效判斷一運算式（expression）中的巢
狀（nested）括號是否正確配對（matched）。（10 分）
請以兩個運算式實例{A*[B−(C+D)+8]−16}及{A+[B−(C+5])}，分別說明此演算法判
斷的過程及結果。（10 分）
（注意：未說明判斷的過程，不予計分）
四、一運算式（expression）為：–a+(z+f)/y–b*a/c+d，請依運算元優先順序，繪出其
二元樹（binary tree）。（10 分）
請列出此二元樹的前序走訪（preorder traversal）。（5分）
請列出此二元樹的廣度優先走訪（breadth-first search traversal）。（5分）
五、一個圖形（Graph）包含五個頂點（vertex），V1, V2, …, V5
，其相鄰矩陣（adjacency
matrix）A=
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
∞
∞
∞∞
0426
4051
25011
67103
130
。
請使用 Floyd 的方法，計算此圖形的最短路徑長度矩陣（shortest path length matrix），
表示任兩頂點間最短路徑長度。請依序列出最短路徑長度矩陣變化過程。（15 分）
請使用 Kruskal 的方法，依序繪出加入此圖形的最小成本擴張樹（minimum cost
spanning tree）每一邊的過程。（5分）