中原大學九十三學年度碩士班入學招生考試
93年3月27日　14:00~15:30　資訊工程學系　 誠實是我們珍視的美德，
我們喜愛「拒絕作弊，堅守正直」的你！
科目：資料結構與演算法  
  注意: 請按題號順序作答
I. 簡答題 (共40%)
1. Use a stack to evaluate the postfix expression AB+C* , where A=5, B=3, and C=4. Show the stack at each step. (2%)
   
2. Draw an expression tree for this algebraic expression: A+B/(C+D). (2%)
   
3. What is the maximum number of elements in a 2-3 tree of height h?
(A tree with one need is a tree of height 1) (2%)
   
4. Some heaps may not be complete binary trees. True or false? (2%)
   
5. If two programs perform the same tasks, it is no longer true that the faster one is necessarily better. Explain this statement. (2%)
   
6. What is the major source of run-time error? (2%)
   
7. In C++, given the declaration
 
    dataType * ptr;
  What is the effect of the following statement?
      ptr = new dataType; (2%)
   
8. Why do we need "HASHING" (key-to-address transformation)? (2%)
   
9. What is the recursive strategy for printing the data in a linked list in the reverse order of appearance? (4%)
   
10. The following four methods are typically used for designing algorithms: (1) divide-and-conquer; (2) back-tracking; (3) greedy method; and (4) dynamic programming. For each of the following algorithms, pick the method that the algorithm uses.
  (a) Kruskal's algorithm for minimum-spanning-trees; (2%)
  (b) Dijkstra's algorithm for shortest-paths; (2%)
  (c) Huffman's algorithm for the Huffman code; (2%)
  (d) Strassen's algorithm for matrix multiplication. (2%)
     
11. For the following graph,
 
  (a) Find the clique of maximum size; (2%)
  (b) Find the vertex cover of minimum size. (2%)
   
12. For the following graphs, determine the number of different spanning trees. (4%)
  (a)                   (b)
 
   
13. For the following binomial heap, show the result after extracting the node with minimum key. (4%)
 
   
II. 問答及計算題 (共60%)
1. (a) Compute the average number of comparisons for the retrieval of the following binary search tree. The probability next to the node is its retrieval probability. (3%)
  (b) Redraw it as an optimal binary search tree. (7%)
 
   
2. Let N(h) denote the minimum number of nodes in an AVL tree with height of h.
(eg. N(1)=1, N(2)=2)
  (a) N(5) = ? (3%)
  (b) Write a recursive function (in C++) which can return
the minimum number of nodes in an AVL tree given height of h. (7%)
   
3. (a) Give an example to show that "quick sort" is an unstable sort. (3%)
  (b) Do quick sort for the following data:
    8 1 2 7 15 14 3
  Show the changes of the array as you go along (Use first item as the pivot). (7%)
   
4. For the following recurrences, give tight asymptotic bounds in -notation. (8%)
  (a)
  (b)
  (c)
  (d)
  where c is a constant and lg is log of base 2.
   
5. Given a sequence of matrix <A1, A2, A3, A4>, where their dimensions are given in the following table. Because matrix multiplication is associative, there are distinct ways of parenthesizations (e.g., (A1(A2(A3A4)))). The matrix-chain multiplication problem is to find a way that minimizes the number of scalar multiplications. (12%)
 
  (a) If the brute force method is used, how many distinct ways of parenthesizations for the 4 matrices are compared?
  (b) Use the dynamic programming to find the optimal parenthesization, show your work step by step.
   
6. Describe the Floyd-Warshall algorithm for finding the all-pairs shortest-paths problems. Then, for the following directed graph, demonstrate the algorithm on the graph step by step. (10%)
 
 
~ End ~