101年 - 101 國立嘉義大學_碩士班(乙組)招生考試試題_資訊管理學系：資料結構#146282

1. Suppose that there are 5 algorithms with time complexitiesO(nloglogn), O(nlog²n), O(n^２), O(n²), and O( √ｎ), respectively. Pleasediscuss their efficiencies. [6%]

(1) What is the value of f(5)? [3%]

(2) In general, what does function f compute when given integerx? [5%]

(3) Rewrite above program without using recursion. [7%]

(1) X is an array in (a) row-major (b) column-major (c)undecidable [5%]

(2) What is the address of X(3, 8)? [5%]

(3) What is the number of row of X? [5%]

(1) Translate it into prefix expression. [5%]

(2) Translate it into postfix expression. [5%]

(1) Which of the following sorts of average time complexity areO(nlog₂n)? [3%]
(A)Bubble Sort (B)Selection Sort (C)Insertion Sort(D)Merge Sort (E) Quick Sort (F)Heap Sort (G)Radix Sort

(2) Which of the following sorts in the worst case time complexityare O(n²)? [3%]
(A)Bubble Sort (B)Selection Sort (C)Insertion Sort(D)Merge Sort (E) Quick Sort (F)Radix Sort

(3) Apply Radix Sort to sort (257, 3223, 155, 219, 185, 1234, 942,2012, 5163) in ascending order. Show the action step by step.[8%]

(1) Using Kruskal’s algorithm. [5%]

(2) Using Prim’s algorithm. [5%]

7. Use Dijkstra algorithm to obtain the shortest path from vertex a toall remaining vertices in the digraph. Show the action step bystep. [10%]

(1) Construct a max-heap with linear time. Show the action stepby step. [5%]

(2) Justify that the algorithm you use is linear. [5%]