(111.04.23) ~「身心(三等)特考」~「資料結構」

請回答下列 Big O 的相關問題： (一) Big O Notation，根據維基百科又稱為漸進符號，它是用於描述演算法漸 進行為的數學符號。更確切地說，它用更簡單的函式來描述一個演算法在 數量上的漸進趨勢。某個問題可採用 5 個演算法 A～E 求解，各演算法執 行時間的 Big O 分別如下：A 為 O（N²），B 為 O（Nlog（log N）），C 為 O（N¹.⁵），D 為 O（N²log（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）= i²（i 為衝突 的次數）。請依序列出每存入一個數字後的 Hash Table 的內容。接著計 算在相同機率的情況下，查找成功及查找失敗的平²查找長度（Average Search Length; ASL）。（15 分）

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

下圖中有 4 個城市 8 條公路，公路上的數字表示這條公路的長短。請注意 這些公路是單向的。若使用 Floyd Warshall 的動態規劃法求解從任意兩個 城市之間的最短路徑，請回答下列問題： (一)首先將圖的信息建成一個 N*N 的初始距離矩陣，其中 N 是節點的個 數，矩陣的各列（Rows）代表 From Nodes，矩陣的各行（Columns） 代表 To Nodes，矩陣中的值則分別代表上圖中從 From Node 到 To Node 的距離。（5 分） (二)其次列舉從 D 到 C 的最短路徑求解過程（需輸出最短路徑的值及路徑）， 並說明此方法的計算複雜度 Big O 為何。（15 分）