| 92年3月21日 11:00~12:30 資訊工程學系 | 誠實是我們珍視的美德， 我們喜愛「拒絕作弊，堅守正直」的你！ |
| 科目：資 料 結 構 與 演 算 法 |
| 1. | (6 points) | |
| (a) | A binary search tree on n integer keys in the range from 1 to n2 can be constructed in O(n) worst-case time. (True or False)_____ | |
| (b) | In a network, the value of any flow is _________the capacity of any cut. (Compare the values) | |
| (c) | If any NP-complete problem can be solved in polynomial time then all NP problems could be solved in polynomial time as well. (True or False)_________ | |
| 2. | (5 points) A recursion tree is plotted below. | |
 |
||
| (a) | Write the recursive function for the tree T(n). | |
| (b) | Derive the asymptotic tight bound of T(n). | |
| 3. | (5 points) Rank the following functions by order of growth. Order them from small to large. If two functions are the same use"="sign. | |
 |
||
| 4. | (5 points) Given a set of m numbers, we wish to find the j largest in sorted order using a comparison-based algorithm. Name the algorithm that sorts the numbers,and list the j largest numbers with the best asymptotic worst-case running time, and analyze the running times of the algorithms in terms of m and j | |
| 5. | (9 points) Use the following piece of dynamic programming code. | |
| Input: Array A of size n Set x = 0 and set y = 0 For i = 1 to n do x = max(x+A[i],0) y = max(x,y) Print A[i], x, and y Return y |
||
| (a) | Trace the above algorithm on the input A[1],...,A[6] = (-2,2,-1,3,-6,1), printing out the values of A[i], x and y whenever the line "Print A[i], x, and y" occurs. Do this in a table with columns labeled by values of i, and rows labeled by A[i], x, and y. | |
| (b) | Briefly describe what this algorithm does on a general array of integers. | |
| (c) | interpret the value printed for y when i = 2. | |
| 6. | (10 points) Professor Chen decides to extend the idea of a binary heap to a k-ary heap. Thus, each node in the heap now has k children instead of just two. | |
| (a) | If the heap is represented by an array A, describe how to find the parent and the (at most) k children of element A[i] | |
| (b) | The worst-case number of comparisons T(n.k)
performed by HEAPSORT is 
(nhk),where h = (logkn)
is the height of the heap. Solve for k so that T(n,k)is
minimized. |
|
| 7. | (10 points) Professor Lee wants to construct the tallest tower
possible out of building blocks. She has n types of blocks, and an
unlimited supply of blocks of each type. Each type-i block is a rectangular
solid with linear dimensions(xi,yi, zi).
A block can be oriented so that any two of its three dimensions determine
the dimensions of a base and the other dimension is the height. In building
a tower, one block may be placed on top of another block as long as the
two dimensions of the base of the upper block are each strictly smaller
than the corresponding base dimensions of the lower block. (Thus, for example,
blocks oriented to have equal-sized bases cannot be stacked.) Use
gragh model to design an efficient algorithm to determine the tallest tower
that the professor can build. Analyze the run time complexity. |
|
| 8. | (10 points) The following has to do with a binary search tree. | |
| (a) | Suppose that the tree is initially empty. What does the tree looks like after we insert 'Mary', 'has', 'a', 'little', 'lamb', 'and', 'so', 'does', 'Joe' onto the tree? | |
| (b) | Write an algorithm for Find(s). Find(s) takes a string s as its input and returns true (alternatively, false) if s is on (alternatively, not on) the tree. You can assume that strings can be compared directly. | |
| 9. | (20 points) Use C, C++, Java,or Pascal(but use only one of these languages) to implement the concept of "a stack of integers". Specifically, you must | |
| (a) | declare (and use) an array as the underlying date structure, | |
| (b) | implement Reset(), IsEmpty(), IsFull(), Push(i), Pop(i), where Reset() will appropriately"reset" the stack and IsEmpty() and IsFull() are two Boolean functions, and |* Be sure to appropriately document your code !*| | |
| (c) | briefly explain how you manage to "hide" your implementation detail from any code that calls (and uses) Reset(), IsEmpty(), IsFull(), Push(i), and Pop(i). | |
| 10. | (20 points) Use C, C++, Java,or Pascal(but use only one of these languages) to implement the concept of "a stack of integers'. Specifically, you must | |
| (a) | declare (and use) a linked list structure as the underlying data structure, | |
| (b) | implement Reset(), Push(i), Pop(i), where Reset() will appropriately "reset" the stack, and |* Be sure to appropriately document your code !*| | |
| (c) | briefly explain how you manage to "hide" your implementation detail from any code that calls (and uses) Reset(), Push(i),and Pop(i). | |
|
--- END ---
|
||