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

將中序運算式轉換成後序運算式演算法常使用堆疊資料結構，如相同 問題，改成使用二元樹資料結構來儲存一中序運算式，以中序運算式 A/B－C+D＊E－A＊C 為例，畫出表示此中序運算式的二元樹，並依前 序（Preorder）與後序（Postorder）列出拜訪（Visit）此二元樹的順序。 （25 分）

用G = (V, E)表示一個無方向性圖形，其中V 是點的集合，E 是一組節點 （Vertices）形成邊的集合。今有一圖形G = (V, E)，V(G) = {T, W, X, Y, Z}, E(G) = {(T, W),(T, Y),(T, Z),(W, X),(W, Z),(X, Z)}，每一個邊對應的權重值 分別為2, 1, 7, 4, 3, 6，請用相鄰矩陣（Adjacency Matrix）與相鄰串列 （Adjacency List）表示此圖形，並使用Prim’s 演算法，計算最小成本擴張 樹（Minimum Cost Spanning Tree），依序寫出從點X 加入邊的順序，最小 成本擴張樹的權重總和為何？（25 分）

給予一串資料60, 70, 50, 10, 20, 80, 95, 90，依序畫出產生2-3 樹（Order 3 的B-Tree）的過程，之後依序畫出刪除50、20 與80 的2-3 樹。（25 分）

給予如下程式片段，假設x[] = [25, 57, 48, 37, 12, 92, 86, 33]，請只用下述 C 語言宣告的變數及兩個for 迴圈，完成下面的選擇排序（Selection Sort）， 假設有n 個資料要由小排到大，每一外迴圈將最大值放在第n-1 個位置， 然後第二大的資料放在第n-2 個位置，依此類推，將資料放到適當的位置， 執行後陣列x[]內容由小排至大。（25 分） Selectsort(x, n) int x[], n; { int i, index, j, large; for (i = n－1; i > 0; i－－){ for (j = 1; j <= i; j++){ } } }

請完成下列表格有關排序演算法的time complexity（假設排序資料有n 個，資料位數有d 個）、是否為In−Space 演算法、是否為Stable 演算法 及範例數列50, 46, 37, 28, 19 進行降冪排列時所需的比較次數。（30 分） 排序演算法 Time Complexity In−Space （Yes/No） Stable （Yes/No） 降冪比較次數 Best Worst 50, 46, 37, 28, 19 Bubble Insertion Merge（奇數時， 後半段多1） Quick（第一個當 pivot） Radix（base 10） Selection

假定一個整數序列：3, 12, 11, 13, 10, 8, 1, 4, 9, 15, 2, 6, 7, 14, 5, 16，請使 用合併排序（Merge Sort）從小到大進行排序及整理，並且一步步寫出過 程。（20 分） 3 a b c f e d