112年 - 112 關務特種考試_三等_資訊處理：資料結構#113897

試卷資訊

選擇題 (0)

申論題 (4)

一、將中序運算式轉換成後序運算式演算法常使用堆疊資料結構，如相同問題，改成使用二元樹資料結構來儲存一中序運算式，以中序運算式 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樹（Order3 的B-Tree）的過程，之後依序畫出刪除50、20與80的2-3樹。（25分）

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