1、Using figure to illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG , SEA, RUG , ROW, MOB, BOX, TAB.
2、Please write inorder, preorder and postorder tree walks of the following binary search tree.
3、Please write down the elements of dynamic programming.
4、Using a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(n/3)+T(2n/3)+cn.
5、Please give an optimal Huffman code for the following set of frequencies. a b c d e f Frequency 5 9 16 12 13 45
6、Converting the following linear program into standard form:
Minimize 2172x x +
Subject to 71=x
24321≥+x x
02≥x
03≤x
7、Solve the following linear program using SIMPLEX:
maximize 215.1218x x +
Subject to 2021≤+x x
121≤x
162≤x
0,21≥x x
8、Suppose A1 a 105⨯ matrix, A2 a 310⨯ matrix, A3 a 123⨯ matrix, A4 a 512⨯ matrix, A5 a 505⨯ matrix, A6 a 650⨯ matrix. Please give an optimal parenthesization of a matrix-chain A1A2A3A4A5A6.
9、Using a recursion tree to give an asymptotically tight solution to the recurrence T (n ) = T(n/4)+T(n/2)+ n 2.
10、Using figure to illustrate the operation of COUNTING-SORT on the array A=<6,0,2,0,1,3,4,6,1,3,2>
11、Using figure to illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG , SEA, RUG , ROW, MOB, BOX, TAB.
12、Please write inorder, preorder and postorder tree walks of the following binary search tree.
13、X=<A, E, B, D, B, C, A, E>, Y=<E, F, B, A, C, A, F, E>. Please illustrate the whole procedure for finding the longest common sequence of X and Y using dynamic programming.
14、Please give an optimal Huffman code for the following set of frequencies.
15、Please draw the result after the operation Left-Rotate(9)
.
16、X=<A, E, B, D, B, C, A, E>, Y=<E, F, B, A, C, A, F, E>. Please illustrate the whole procedure for finding the longest common sequence of X and Y using dynamic programming. 17、Please give an optimal Huffman code for the following set of frequencies. a b c d e f Frequency 15 19 6 12 13 35
18、A red-black tree (RB tree) is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK, and the red-black is a nearly balanced tree. Please prove n-node RB tree has height )(lg n O h =
19、Solve the following linear program using SIMPLEX:
maximize 215.1218x x +
Subject to 2021≤+x x
121≤x
162≤x
0,21≥x x
20、In the activity-selection problem,
}:{j k k i k ij s f s f S a S ≤≤≤∈= represents the activities that start after an activity
i a finishes and finish before one activity j a starts. Here, an activity i a occurs during period ),[i i f s , and activities are sorted by
monotonically increasing finish time. Let
Φ≠ij S , and let m a be the activity in ij S with the earliest finish time: }:min{ij k k m S a f f ∈=. Then prove m a is used in some maximum-size subset of mutually compatible activities of ij S。