中原大學九十一學年度碩士班入學招生考試

91年4月12日　11:00~12:30　資工系 誠實是我們珍視的美德，
我們喜愛「拒絕作弊，堅守正直」的你！
科目： 資料結構與演算法  

I.  
1.
 Which data structure is the most suitable for implementing: (8%)

(1) A complete binary tree and why?
(2) Priority queue and why?
 

2.

 

 A binary tree with n nodes ( we assume that the height is 1 if with only
one node): (4%)
(1) the maximum height of the tree would be _______
(2) the minimum height of the tree would be _______
 
3.
 Draw a complete graph with 5 vertices. (2%)
 
4.
 
 Differentiate between a syntax error and a semantic (logical) error in a program. (4%)
When is each type of error likely to be found? (2%)
   
 
II. ( 3% for each answer )
1.
 There are m data. Their range is from 1 to K. If counting sort is applied to sort the data in the time complexity of O (m). Then what is the order of K ?
 

2.

 

 The length of two words are m , n . If we apply dynamic programming to find their longest-common-subsequence, then
(a) what is the order of the maximum depth of the tree?
(b) what is the number of distinct sub-problems?
 
3.
In the worst case, what is the lower bound of any comparison based sorting algorithm?
 

4.

 

 If all edge weights of a connected, undirected graph are distinct, then the minimum spanning tree of the graph is unique. (True/False)?
5.
 Using adjacency matrix representations for graph G = (V, E), what is the space complexity?
 
 
III. ( 10 % for each of the question )

1.

 

 Write a recursive function ( in C or C++) for counting ways of choosing k objects from n objects. (Objects are distinct.)
And point out your base case(s) and general case.
　　　C(n, k) = C(n-1, k-1) + C(n-1, k)
 

2.

 

 Prove that permutation of n objects obtainable by a stack is
　　　Cat(n) = C(2n, n) - C(2n, n-1)
3.
 Write a pseudocode function that can visit all items in a binary search tree that have a key value in the range Low..High.
 
   
IV.  

1.

 

 Let G be a weighted graph where each edge weight is non-negative. Describe how to modify Dijkstra's algorithm to find a shortest path P from s to each vertex w in G such that P has the fewest number of edges over all shortest paths from s to w in G. Your modification must keep the time complexity unchanged. Also, prove that your modification works correctly. ( 10% )
 
2.
 The following is a divide-and-conquer algorithm for finding the maximum value in an array S[1..n]. The main body of the algorithm consists of a call to maximum(1, n).
　　　　　　
(a)
 Write down a recurrence relation for the worst-case number of comparisons used by maximum(1, n). Solve this recurrence relation. You may assume that n is a power of 2. ( 8% )
(b)
 What is the running time of maximum(1, n)? Explain your answer. ( 4% )
 
3.
 A graph is bipartite if the vertex set V(G) of G can be partitioned into two nonempty disjoint sets A and B such that every edge has an endpoint in A and an endpoint in B.

(a)

 

 

Explicitly write a bipartition V(G) =A∪B of the following graph that proves that the graph is bipartite. ( 3% )

(b)

 

 Given a connected graph, give an algorithm to test if G is bipartite. Write a pseudocode for an algorithm that either gives a bipartition of the vertices V(G) if G is bipartite or else terminate and state "G is not bipartite". What is the running time of your algorithm? ( 7% )
 
　　　　　--- END---