101年 - 101 國立嘉義大學_碩士班(甲組)招生考試試題_資訊工程工程學系：資料結構#146335

1. What is the difference between the operations of Prim’s algorithm and the Dijkstra’s algorithm? (10%)

2. Given sorting problem µ convex hull，which one of the following statements can be derived ?(Choose one) (1) The Lower Bound of convex hull is W(n log n). (2) The Lower Bound of convex hull is W(n). (3) The Lower Bound of Sorting is W(n log n). (4) The Lower Bound of Sorting is W(n). Please explain how to find the lower bound by problem transformation. (20%)

3. The lower bound for any comparison sorting is W(nlogn). Why? (20%)

4. What is a hash function and what is a one-way hash function? (20%)

5. Write the postfix and prefix forms of “(A+B) * C+D/(E+A * C)+F” . (20%)

6. Give the orders of the following items by asymptotic rate: \( n^2, (3/2)^n, n \times 2^n, n \lg n, 3^{\lg n} \cdot (10\%) \)