最新發佈

國立空中大學新聞編輯與採訪 104 學年度上學期期中考試題【正參】22

國立空中大學 視覺傳播104 學年度上學期期末考試題【副參】21

國立空中大學視覺傳播 104 學年度上學期期末考試題【正參】21

國立空中大學視覺傳播 104 學年度上學期期中考試題【副參】21

國立空中大學視覺傳播 104 學年度上學期期中考試題【正參】21

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

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

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

(二)若處理 Hash Table 衝突的方法為開放定址法（Open Addressing Hashing） 中的平方探測法（Quadratic Probing）：增量函數 F（i）= i2（i 為衝突 的次數）。請依序列出每存入一個數字後的 Hash Table 的內容。接著計 算在相同機率的情況下，查找成功及查找失敗的平均查找長度（Average Search Length; ASL）。（15 分）

(一)若處理 Hash Table 衝突的方法為開放定址法（Open Addressing Hashing） 中的線性探測法（Linear Probing）：增量函數 F（i）= i（i 為衝突的次 數）。請依序列出每存入一個數字後的 Hash Table 的內容。接著計算在 相同機率的情況下，查找成功及查找失敗的平均查找長度（Average Search Length; ASL）。（15 分）

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

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

有關數位簽章（Digital Signature）的敘述，下列何者正確？

具有下列各類常見副檔名的檔案中，相對比較安全，不易含有惡意程序碼 者為何？

下列何者不是 Web 安全協定？

有關傳輸控制通訊協定（Transmission Control Protocol；TCP），下列敘述 何者錯誤？