111年 - 111 身心障礙特種考試_三等_資訊處理：資料結構#107534

科目：公職◆資料結構 | 年份：111年 | 選擇題數：0 | 申論題數：7

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (7)

(一) Big O Notation，根據維基百科又稱為漸進符號，它是用於描述演算法漸進行為的數學符號。更確切地說，它用更簡單的函式來描述一個演算法在數量上的漸進趨勢。某個問題可採用 5 個演算法 A～E 求解，各演算法執行時間的 Big O 分別如下：A 為 O（N²），B 為 O（Nlog（log N）），C 為 O（），D 為 O（N²log（N）），E 為 O（SQRT（N））。當 N 很大時，請根據演算法的執行時間，由慢至快排序這 5 個演算法。（10 分）

(二)給定 100 萬個介於 0 到 100（含 0 及 100）的整數，請利用任一種高階程式語言寫出一個 O（N）的由大至小的排序演算法，並說明此演算法為何是 O（N）的方法。（15 分）

(一)若處理 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 分）

三、請寫出對以下 8 個數字[44, 62, 31, 5, 82, 49, 16, 7]，依序建構最小堆積樹（Min Heap Tree）的過程。為方便最小堆積樹的建構，我們通常會使用一個一維陣列來儲存堆積樹中的數字。請說明如何用一維陣列來處理最小堆積樹的建構。最小堆積樹建構完成後，請寫出如何用此樹依序將數字由小到大的排序過程。請說明此種排序法的計算複雜度 Big O 為何？（25 分）

(一)首先將圖的信息建成一個 N*N 的初始距離矩陣，其中 N 是節點的個數，矩陣的各列（Rows）代表 From Nodes，矩陣的各行（Columns）代表 To Nodes，矩陣中的值則分別代表上圖中從 From Node 到 To Node 的距離。（5 分）

(二)其次列舉從 D 到 C 的最短路徑求解過程（需輸出最短路徑的值及路徑），並說明此方法的計算複雜度 Big O 為何。（15 分）