所屬科目：研究所、轉學考(插大)◆資料結構與演算法
1. (15分) Run the Prim's algorithm to generate a minimum spanning tree for the following graph. It is required that the initial vertex is s. Run the algorithm step by step to generate your tree. What is the tree weight?
2. (15 分) Given a file, we found that it consists of seven symbols a,b,c,d,e,f,g and their frequencies are as follows. Use Huffman coding to encode these 7 symbols to achieve the minimum file size.
3. (5分) Give an asymptotic upper bound for the function \( \mathrm{T}(\mathfrak{n}) \) where \( \mathrm{T}(\mathfrak{n}) \) satisfies the recurrent equation \( \mathrm{T}(\mathfrak{n}) = 5\mathrm{T}(\mathfrak{n} / 4) + \mathfrak{n} \).
4. (15分) Let \( k \) be \( O(n) \). Describe an \( O(n) \)-time algorithm that, given a set \( S \subseteq \{1, \ldots, k\} \) of \( n \) integers and another integer \( x \), determines whether or not there exist two elements in \( S \) whose product is exactly \( x \).
5. (5分) (A)使用quick sort排序數列60804523698114752897563.7。並且說明每次移動數字時，所使用的條件和基準。
(5分) (B)將此inorder statement: \( A^{*}(B + C) + E^{*}F - H / I \) 轉為 postorder，並畫出它的二元樹。
(10分) (C)設計一個算法使用 stack 來實現上述 inorder 轉 postorder，需解釋如何處理括號和運算式的優先權。
6. (10分)使用linked list運用C語言實作stack：
7. (20分)使用stack運用C語言實作老鼠走迷宮問題 (Maze path search)：
阿摩線上測驗
登入
阿摩線上測驗
登入
Use Huffman coding to encode these 7 symbols to achieve the minimum file size.
