加載中. ..
PDF
112年公務人員特種考試關務人員、身心障礙人員考試及
112年國 軍 上 校 以 上軍 官 轉 任 公 務人 員 考 試 試 題
考 試 別
：
關務人員考試
等 別
：
三等考試
類 科
：
資訊處理
科 目
：
資料結構
考試時間：2小時 座號：
※注意：禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號
：
10460
頁次
：
2
－
1
一、將中序運算式轉換成後序運算式演算法常使用堆疊資料結構，如相同
問題，改成使用二元樹資料結構來儲存一中序運算式，以中序運算式
A/B－C+D＊E－A＊C為例，畫出表示此中序運算式的二元樹，並依前
序（Preorder）與後序（Postorder）列出拜訪（Visit）此二元樹的順序。
（25 分）
二、用G = (V, E)表示一個無方向性圖形，其中 V是點的集合，E是一組節點
（Vertices）形成邊的集合。今有一圖形 G = (V, E)，V(G) = {T, W, X, Y, Z},
E(G) = {(T, W),(T, Y),(T, Z),(W, X),(W, Z),(X, Z)}，每一個邊對應的權重值
分別為 2, 1, 7, 4, 3, 6，請用相鄰矩陣（Adjacency Matrix）與相鄰串列
（Adjacency List）表示此圖形，並使用 Prim’s 演算法，計算最小成本擴張
樹（Minimum Cost Spanning Tree），依序寫出從點 X加入邊的順序，最小
成本擴張樹的權重總和為何？（25 分）
三、給予一串資料 60, 70, 50, 10, 20, 80, 95, 90，依序畫出產生 2-3 樹（Order 3
的B-Tree）的過程，之後依序畫出刪除 50、20 與80 的2-3 樹。（25 分）
代號：
10460
頁次：
2
－
2
四、給予如下程式片段，假設 x[] = [25, 57, 48, 37, 12, 92, 86, 33]，請只用下述
C語言宣告的變數及兩個 for 迴圈，完成下面的選擇排序（Selection Sort），
假設有 n個資料要由小排到大，每一外迴圈將最大值放在第 n-1 個位置，
然後第二大的資料放在第 n-2 個位置，依此類推，將資料放到適當的位置，
執行後陣列 x[]內容由小排至大。（25 分）
Selectsort(x, n)
int x[], n;
{int i, index, j, large;
for (i = n－1; i > 0; i－－){
for (j = 1; j <= i; j++){
}
}
}