加載中. ..
PDF
114年公務人員高等考試三級考試試題
類 科
：
資訊處理
科 目
：
資料結構
考試時間
：
2
小時
座號
：
※注意：禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號：
27750
頁次：
2
－
1
一、一棵空的階數為 3的B-Tree（B-Tree of order 3）。由左而右依序插入下列
鍵值（keyvalue）：10,80,2,9,45,62。請問插入完畢後，根節點中的鍵值
有那些？請依序由小到大列出，用逗號分隔，並請說明樹節點的變化。
（10 分）有一棵階數為 5的B-Tree（B-Tree of order 5），其高度（height）
為3，請問這棵樹中最多可以儲存多少個鍵值？(10 分)
二、有一個三維整數陣列 A[3][6][8]，每個元素占用 4個記憶體空間，每個記
憶體空間均有位址。該陣列在儲存至記憶體時，會先被轉換為一維陣列
的形式儲存。下列位址皆為十進位，已知 A[0][1][2]的記憶體位址為
2040，A[1][4][5]的位址為 2340。請問陣列 A在記憶體中的儲存方式為
何？是以列為主（row-major）還是以行為主（column-major）？（10 分）
請計算 A[1][5][3]在記憶體中的位址為何？（10 分）
三、假設 G為一個無方向連通加權圖（Undirected connected weighted graph），
包含五個節點：A、B、C、D、E。各節點間相連情形如下，邊權（邊的
權重）為正整數，代表邊的成本。
A與B相連，邊權為 16；
A與C相連，邊權為 18；
A與D相連，邊權為 14；
B與C相連，邊權為 15；
C與D相連，邊權為 13；
D與E相連，邊權為 12；
C與E相連，邊權為 17；
請使用 Sollin’s 演算法，寫出最終形成的最小成本擴展樹的邊集合與總
成本，請寫出每一步的演算法與該步驟形成的擴展樹。每一合併過程，
列出選中的邊與合併的組成（component）。（20 分）
代號：
27750
頁次：
2
－
2
四、根據下列的虛擬碼，若 n = 21 則傳回的答案為何？請說明。其中 floor()
為數學上的地板函數（floor function）。（20 分）
function splitSum(n: integer) returns integer
if n <= 1 then
return 1
a←floor(n / 2)
b←floor(n / 3)
return splitSum(a) + splitSum(b)
五、下列虛擬碼是利用某演算法對陣列 A的元素進行處理，請說明該法是進
行何種處理並請寫出其名稱和在最壞情況下時間複雜度為何？（10 分）
若陣列 A = [29, 10, 14, 37, 13]，請寫出該虛擬碼的處理過程：請列出陣
列在每一輪（每次外層迴圈執行完後）的內容變化情形。請特別標示出
最終結果為何？（10 分）
doingSomething(A)
begin
n←陣列 A的元素個數
for i ← 0 to n − 2 do
theIndex ←i
for j ← i + 1 to n − 1 do
if A[j] < A[theIndex] then
theIndex ←j
end for
if theIndex <> i then
temp = A[i]
A[i] = A[theIndex]
A[theIndex] = temp
end if
end for
end