Review Problems for AP CS Test

- Under what circumstances does a hash (Set, Map, Tree, or any other thing
that can be hashed) NOT take O(1) time? Explain.

- If quicksort is applied to a sorted array of n elements, how many comparisons
will it need to make? (Try this by hand; if you get stuck, take a look at
the JavaSort.exe program by Tony Wang. Use some number of elements that will
make the math fairly intuitive.)

- Thinking about problem #2, above, to what other sorting routine did quicksort
essentially degenerate? Explain.

- Suppose 35 million students take a test. You want to find the top 10 scores.
Which sorting algorithm would you choose?

- Now suppose that all you really care about are 10 tests with scores in descending
order. Which algorithm would you choose now?

- Suppose you have a max-heap that is sorted as follows: 12, 11, 10, 9, 7,
6, 5, 4, 3, 2, 1, 0. Now you wish to add 8 to the heap and sort it. What is
the the order of growth for producing the freshly sorted heap?

- For problem 6, suppose the numbers are in an ArrayList and that you are
using quicksort. Once again, you want to add the number 8 and sort. What is
the order of growth for this process?

- Suppose you have the following method:

public static void thing(int[] a) { int low = 0; int high = a.length - 1; while (high > low) { for (int i = low; i < high; i++) { if (a[i] > a[i+1]) { swap(a, i, i+1); } } high--; for (int i = high; i > low; i--) { if (a[i] < a[i-1]) { swap(a, i, i-1); } } low++; } }

If a contains n elements, what is Big-Oh of this sorting algorithm? (Do you know what this algorithm is called?)

- Suppose you have the numbers 1..10000 in random order. You insert them into
a binary search tree. What is the largest depth possible? The smallest depth?
The average depth?
- What is the difference between a complete tree and a full tree?
- Suppose we have the following expression tree:
* / \ 6 - / \ 5 2

- If evaluated as an expression, what would the value of this tree be?
- What would the preorder printing of this tree be? This is called prefix
notation and is what is used in Scheme.
- What would the inorder printing of this tree be? This is called infix
notation and is what we typically use when we write out mathematics.
- What would the postorder printing of this tree be? This is called postorder
notation and was used on old HP calculators.

- If evaluated as an expression, what would the value of this tree be?
- Translate the binary number 1011011 into decimal.
- Translate the decimal number 177 into binary.
- Translate the hexadecimal number 0xe5 into binary.
- Translate the binary number 1011101101 into hexadecimal.
- Translate the IP address 255.255.255.255 into hexadecimal.
- Consider the following code:
public class Main { public static void main(String[] args) { System.out.println(mystery(2,12)); } public static long mystery(long a, long b) { return mysteryHelper(a, b, 1); } public static long mysteryHelper(long a, long b, long n) { if (b == 0) { return n; } else if (isEven(b)) { return mysteryHelper(a*a, b/2, n); } else { return mysteryHelper(a, b-1, a*n); } } public static boolean isEven(long b) { return (b%2 == 0); } }

- What does the function mystery do?
- What is the loop invariant for mysteryHelper function?

- What does the function mystery do?
- Which comes first, the casting operator or the dot operator? How can
you prove it?