加載中. ..
PDF
111年公務人員特種考試關務人員、身心障礙人員考試及
111年國 軍 上 校 以 上軍 官 轉 任 公 務人 員 考 試 試 題
考 試 別
：
身心障礙人員考試
等 別
：
三等考試
類 科
：
資訊處理
科 目
：
資料結構
考試時間：2小時 座號：
※注意： 可以使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本
試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號
：
30860
頁次
：
2
－
1
一、請回答下列 Big O 的相關問題：
Big O Notation，根據維基百科又稱為漸進符號，它是用於描述演算法漸
進行為的數學符號。更確切地說，它用更簡單的函式來描述一個演算法在
數量上的漸進趨勢。某個問題可採用 5個演算法 A～E求解，各演算法執
行時間的 BigO 分別如下：A為O（N2），B為O（Nlog（logN）），C
為O（N1.5），D為O（N2log（N）），E為O（SQRT（N））。當 N很
大時，請根據演算法的執行時間，由慢至快排序這5個演算法。（10 分）
給定 100 萬個介於 0到100（含 0及100）的整數，請利用任一種高階
程式語言寫出一個 O（N）的由大至小的排序演算法，並說明此演算法
為何是 O（N）的方法。（15 分）
二、以下 7個數字[21, 1, 16, 11, 25, 9, 35]，要儲存到 Hash Table 中，Hash Table
的儲存空間是一個索引從 0開始的一維陣列（Array）。假設 Hash 函數為
H（Key）=（Key * 3）mod 7，裝填因子（Load Factor）為 0.7。
若處理 Hash Table 衝突的方法為開放定址法（Open Addressing Hashing）
中的線性探測法（Linear Probing）：增量函數 F（i）= i（i為衝突的次
數）。請依序列出每存入一個數字後的 Hash Table 的內容。接著計算在
相同機率的情況下，查找成功及查找失敗的平均查找長度（Average
Search Length; ASL）。（15 分）
若處理 Hash Table 衝突的方法為開放定址法（Open Addressing Hashing）
中的平方探測法（Quadratic Probing）：增量函數 F（i）= i2（i為衝突
的次數）。請依序列出每存入一個數字後的 Hash Table 的內容。接著計
算在相同機率的情況下，查找成功及查找失敗的平均查找長度（Average
Search Length; ASL）。（15 分）
代號：
3086
0
頁次：
2
－
2
三、請寫出對以下 8個數字[44, 62, 31, 5, 82, 49, 16, 7]，依序建構最小堆積樹
（Min Heap Tree）的過程。為方便最小堆積樹的建構，我們通常會使用一
個一維陣列來儲存堆積樹中的數字。請說明如何用一維陣列來處理最小堆
積樹的建構。最小堆積樹建構完成後，請寫出如何用此樹依序將數字由小
到大的排序過程。請說明此種排序法的計算複雜度 Big O 為何？（25 分）
四、下圖中有 4個城市 8條公路，公路上的數字表示這條公路的長短。請注意
這些公路是單向的。若使用 Floyd Warshall 的動態規劃法求解從任意兩個
城市之間的最短路徑，請回答下列問題：
首先將圖的信息建成一個 N*N 的初始距離矩陣，其中 N是節點的個
數，矩陣的各列（Rows）代表 From Nodes，矩陣的各行（Columns）
代表 To Nodes，矩陣中的值則分別代表上圖中從 From Node 到To Node
的距離。（5分）
其次列舉從D到C的最短路徑求解過程（需輸出最短路徑的值及路徑），
並說明此方法的計算複雜度 Big O 為何。（15 分）