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

4月28日　　第3節 　　　資工系 誠實是我們珍視的美德，
我們喜愛「拒絕作弊，堅守正直」的你！
科目： 資料結構與演算法 （共3頁 第1頁）

I (44%) Answer the following questions.

1. Consider the following 4-digit employee numbers:
9614, 1825
Find the 2-digit hash address of each number using
(a) the division method, with m = 97
(b) the midsquare method
(c) the folding method without reversing (shift folding)
(d) the folding method with reversing (folding at boundaries)

2.

Given the array, DATA, containing the elements

19 23 2 4 99 1
[0]
[1]
[2]
[3]
[4]
[5]

determine which sort produced the results shown below. (Iteration refers to the execution of the outer loop.)
(a) 1 2 23 4 99 19 (after 2nd iteration)
(b) 1 19 23 2 4 99 (after 1st iteration)
(c) 2 19 23 4 99 1 (after 2nd iteration)
3. A 2-3 tree has 63 nodes. This tree must have height no greater than _______.
4. Name any two of the graph representations:_________, _________.
5. Suppose we have four nodes with keys 1,2,3,4 in a binary search tree. How
many distinct binary trees could be represented with these nodes:________
6. An unsorted array of n elements.
If use Insertion sort algorithm to sort the array, the time complexity is __(a)___.
If use Merge sort algorithm to sort the array, the time complexity is ___(b)___.
7. For any asymptotically nonnegative function f(n), we have f(n) + o(f(n)) = O(f(n).) (True or False)?
8. The problem of determining an optimal order for multiplying a chain of matrices can be solved by a greedy algorithm, since it displays the optimal substructure and overlapping subproblems properties (True or False)?
9. The topological sort of an arbitrary directed graph G = (V, E) can be computed in linear time.( True or False)?
10.

The transitive closure of a directed graph G = (V, E) can be computed in O(V3) time by the Floyd-Warshall algorithm, which uses dynamic programming and repeatedly squares the adjacency matrix of G (True or False).?
11. Any NP-complete problem is also an NP-hard problem ? (True or False)


II. (Total 56%)
1. (6 %) List the functions below from lowest to highest order. If any two (or more) are of the same order, indicate which. (You do not have to formally justify each relation.) n ; n-2n3 + 5n5 ; sqrt(6n) ; lglg n ; O(1); 2n!
2. (10%) A binary tree T has 9 nodes. The inorder and preorder traversals of T yield the following sequences of nodes:
Inorder: E A C K F H D B G
Preorder: F A E K C D H G B
Draw the tree T.
3. (10%) The Ackermann function is a function with two arguments each of which can be assigned any nonnegative integer: 0, 1, 2,... . This function is defined as follows:
(1) If m=0, then A(m,n) = n+1
(2) If m>0 but n=0, then A(m,n) = A(m-1,1)
(3) If m>0 and n>0, then A(m,n) = A(m-1,A(m,n-1))
(a) Find the result of A(1,3)
(b) Write a recursive procedure which can compute the value of A(m,n) in C language.

4.

(10%) A d-ary heap is like a binary heap, but instead of 2 children, nodes have d children.
(a) What is the height of a d-ary heap of n elements in terms of n and d?
(b) An element, Key , is inserted in to the array, the heap array is A, the size of the
heap array is heap_size[A] before the insertion. Write pseudo code of an efficient
implementation of Insert operation. Analyze its running time in terms of d and n.
5.

(10%) Suppose that you are given a sorted sequence of distinct integers
A = (a1 , a2,..., an).
Give a divide-and-conquer O(lgn) algorithm in pseudocode to determine if there exists an index i such that ai = i. For example, in (-10,-3, 3, 5, 9), a3 = 3. In (2,3,4,6,7) there is no such i.
6. (10%) A one-way railway has n stops. Suppose that for all i< j, the price of the ticket from the ith stop to jth stop is known, and denoted cost(i,j). ( There is no traffic in the reverse direction since the railway is one-way.) Apply the dynamic programming technique to design your algorithm that outputs the minimum travel cost from stop 1 to stop n, and all the intermediate stops that the travel takes. What is the time complexity of your algorithm.

　　　　　--- END---