資訊處理 111 年資料結構考古題

請回答下列Big O 的相關問題： ㈠Big O Notation，根據維基百科又稱為漸進符號，它是用於描述演算法漸 進行為的數學符號。更確切地說，它用更簡單的函式來描述一個演算法在 數量上的漸進趨勢。某個問題可採用5 個演算法A～E 求解，各演算法執 行時間的Big O 分別如下：A 為O（N2），B 為O（Nlog（log N）），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 分）

請寫出對以下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 分）

下圖是一個加權圖G=(V, E)，其中V 是點集合而E 是邊集合。 ㈠請使用相鄰矩陣（Adjacency Matrix）表示法來表示加權圖G。（5 分） ㈡不考慮權重，從節點g 開始並按照字母順序對G 進行廣度優先尋 訪（Breadth-First Search, BFS），請繪出尋訪完後所產生的BFS 樹 （BFS Tree）。（5 分） ㈢請利用Prim's 演算法，從節點d 起始，找出一個最小擴張樹（Minimum Spanning tree），請以圖示方式一步步畫出過程與結果，並說明Prim's 演算法的時間複雜度。（10 分）

利潤 40 15 60 20 45 10 55 最後期限 2 4 3 2 1 3 1 以文本（text）X=“AGTCATTCGATTC”，樣式（pattern）Y=“ATTC”兩字 串為例，請問使用暴力比較/窮舉法（exhaustive search）中的樣式前向法 （forward）及後向法（backward）各需比較幾次？（10 分） m,n N ,已知三維陣列（three-dimensional array）A[1：8, 1：9, 1：4]每一 個元素占用2 個儲存單元，並且A[1,2,1]的儲存地址為234，A[2,3,1]的儲 存地址是m，A[2,3,4]的儲存地址為n。 ㈠採用列序為主序（row major）方式儲存，則m、n 分別為何？（10 分） ㈡採用行序為主序（column major）方式儲存，則m、n 分別為何？（10 分）