Solved

# url request to explain below

Posted on 2004-10-01

1. Assume you have an input stream '1 2 3 4 5 6' reading from left to right. By using (1) a queue and (2) a deque, which of the following rearrangements can be obtained for output, reading from left-to-right?

a) 1 2 3 4 5 6 b) 2 4 3 6 5 1 c) 1 5 2 4 3 6

d) 4 2 1 3 5 6 e) 1 2 6 4 5 3 f) 5 2 6 3 4 1

2. Compute log2 1000 if all you know is log2 10. Show your work and justify why it is correct.

3. Show how logs "turn" multiplication into addition, division into subtraction, and exponentiation into multiplication.

4. A fully populated binary tree has all nodes (vertices) present. Assuming a tree with one node has height 1, what is the height of a fully populated tree with n nodes? A well-behaved binary tree may not have all levels fully populated, but all leaves in the tree will be on the same or on adjacent levels. What is the height of a well-behaved binary tree with n nodes? (hint: use the floor or ceil function from the math library.)