加載中. ..
PDF
106年公務人員高等考試三級考試試題 代號：26050 全一張
（正面）
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
（請接背面）
T
S
O
P
U
G
X
一、給定二元樹（binary tree）如右圖，樹高為 4且共有 7個節點。
請寫出該樹之後序遍歷（postorder traversal）結果。（5分）
若以陣列 A[1..15]實作該二元樹，請列舉陣列 A[1..15]的內容。
（5分）
若要將數值 x設為或取代 A[i]（任一 1≤i≤7）所代表的節點
之右子節點（right child node）的內容，令 x會被放入陣列中
A[j]的位置。請以 j、i表示，寫出 j位置之公式。（5分）
若要在原始的二元樹中加入一些節點使其成為完整二元樹（complete binary tree）及完滿
二元樹（full binary tree），請問最少各需加入幾個新節點？（5分）
二、遊樂園設計公司正在設計新的遊樂園，遊樂園將有 9個遊樂設施，設施名稱暫定為 A, B, C,
D, E, F, G, H, I。遊樂設施之間將透過不盡相同距離但極具特色的商店街相連。給定遊樂園
的初步規劃如表一，表內數字為兩遊樂設施之間商店街道之預計長度（每條街道長度皆不
同）。若無數字則代表兩遊樂設施之間沒有商店街道之規劃。設計公司將依不同考量來決
定實際建置那些商店街道。
表一
A B C D E F G H I
A 18 5 13 1
B 18 9 10 16 8
C 9 11 7 12 3
D 5 17 19
E 13101117 2
F 1 16 14 15
G 7 19 2 4
H 12 14 4 6
I 8 3 15 6
若要節省開發預算，在可到達所有遊樂設施的前提下，所建置的商店街道總長度需越短
越好，請問可以用那一個演算法來選擇應建置的街道？請給演算法名稱並簡單說明該演
算法特性。（5分）
請計算符合上述小題條件下，所應建置的商店街道總長度，並由小到大列舉所有應該
建置街道的長度。（10 分）
但若要規劃一條路徑，使得遊客可以從任一遊樂設施開始玩，且只要依照該路徑行走，
就可以玩遍 9項遊樂設施並回到起始的遊樂設施，遊客所需走過的商店街道總長度需越
短越好且每項遊樂設施只能到達一次。請問此問題最適合用下列那一種演算法來幫忙找
到所應開發的街道：尤拉迴路（Euler Cycle），漢密爾頓迴路（Hamiltonian Cycle），
旅行商人問題（Traveling Sales Man Problem），最短路徑（例如 Dijkstra 演算法），任
兩點最短距離（例如弗洛伊德(Floyd-Warshall)演算法）？（5分）
T
S
O
PX
G
U
106年公務人員高等考試三級考試試題 代號：26050 全一張
（背面）
類 科：資訊處理
科 目：資料結構
三、表二列出五種常見的排序演算法，請填滿該表以顯示各排序法在最佳情況、一般情況、最
壞情況下的時間複雜度、所需額外記憶體空間及是否為穩定排序法。快速排序法的各項資
料已事先填入作為範例。（(a),(b),(c),(d)各5分，共 20 分）
表二
最佳情況
（best case）一般情況
（average case）最壞情況
（worst case） 所需額外空間
是或不是
穩定排序法
（stable sor
t
）
快速排序法
（quicksort） O(n log n) O(n log n) O(n2) O(n) 不是
(a)泡沫排序法
bubble sort
(b)插入排序法
insertion sort
(c)合併排序法
merge sort
(d)堆積排序法
heap sort
四、矩陣相乘是問題解決中常見的計算，但相乘順序對於計算效能有極大的影響。給定 n個矩陣，
A1,A
2,…,A
n，且任一矩陣 Ai大小為 nii pppp ...,,, 01 ×
−皆為正整數。A1×A2×…×An實
際計算過程可以是(…((A1×A2)×A3)×…×An)、(A1×(A2×(…×(An-2 ×(An-1 ×An))…)))、或
其他合理的順序，而因矩陣相乘順序不同，所需要的乘法運算次數可能也會不同。透過動
態規劃（dynamic programming）、二維陣列的應用及遞迴程式，可以找到最少乘法運算次
數的計算順序。方法如下：令 ],[
j
im 為計算 Ai×Ai+1 ×…×Aj時所需最少乘法運算次數，
],[
j
im 可以下列遞迴公式表示之：
⎩
⎨
⎧
≥
<+++
=−
<≤ jiif
jiifpppjkmkim
jim jki
jki ,0
},],1[],[{min
],[ 1
請說明 A1×A2×…×An相乘過後的矩陣大小為何？（3分）
透過上述方法所找到的最少乘法運算次數，應為二維陣列 ],[
j
im 中的那個元素，亦即 i, j
應分別為何？（3分）
若n=4且
43210
,,,, ppppp 分別為 3, 4, 5, 4, 2，請計算並填寫出二維陣列 ],[
j
im 。（11 分）
承上小題，請說明該四矩陣相乘，A1×A2×A3×A4，最少共需有幾次乘法運算。（3分）
五、請依序將 17, 23, 36, 13, 38, 11, 52, 44, 25, 35, 2, 18, 21 儲存至下列 13 桶（buckets）×1槽
（slots）的雜湊表（hashing table）。請以各小題所設定的雜湊函式（hashing function）將資
料依序存入並顯示最後的雜湊表。
雜
湊
表
0 1 2 3 4 5 6 7 8 9 10 11 12
雜湊函式 F(x) = x mod 13，碰撞時，採取「線性探測法」（open addressing with linear
probing）來放入資料。請顯示最後的雜湊表。（5分）
雜湊函式 F(x) = x mod 13，碰撞時，採取「二次方探測法」（open addressing with quadratic
probing）來放入資料。請顯示最後的雜湊表。（5分）
雜湊函式 F1(x) = x mod 13，碰撞時，採取「雙探測法」（open addressing with double hashing）
來放入資料，第二雜湊函式為 F2(x) = 7
－
(x mod 7)。請顯示最後的雜湊表。（5分）
若雜湊表夠大（例如 slots = 2 或更大）但資料量多時，針對三種碰撞時所採取的處理方
式，請說明那一種方式較能有效率的儲存或搜尋資料？請說明那一種處理方式效率最
差？（5分）