Review Problems for AP CS Test

1. Under what circumstances does a hash (Set, Map, Tree, or any other thing that can be hashed) NOT take O(1) time? Explain.
   
   
   
   
2. 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.)
   
   
   
   
3. Thinking about problem #2, above, to what other sorting routine did quicksort essentially degenerate? Explain.
   
   
   
   
4. Suppose 35 million students take a test. You want to find the top 10 scores. Which sorting algorithm would you choose?
   
   
   
   
5. Now suppose that all you really care about are 10 tests with scores in descending order. Which algorithm would you choose now?
   
   
   
   
6. 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?
   
   
   
   
7. 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?
   
   
   
   
8. 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?)
   
   
   
   
9. 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?
   
   
10. What is the difference between a complete tree and a full tree?
    
    
11. Suppose we have the following expression tree:

          *
           / \
         6   -
            / \
           5   2
        

    1. If evaluated as an expression, what would the value of this tree be?
       
       
    2. What would the preorder printing of this tree be? This is called prefix notation and is what is used in Scheme.
       
       
    3. 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.
       
       
    4. What would the postorder printing of this tree be? This is called postorder notation and was used on old HP calculators.
       
       
    
    
    
12. Translate the binary number 1011011 into decimal.
    
    
13. Translate the decimal number 177 into binary.
    
    
14. Translate the hexadecimal number 0xe5 into binary.
    
    
15. Translate the binary number 1011101101 into hexadecimal.
    
    
16. Translate the IP address 255.255.255.255 into hexadecimal.
    
    
17. 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);
        }
    }
    

    1. What does the function mystery do?
       
       
    2. What is the loop invariant for mysteryHelper function?
       
       
18. Which comes first, the casting operator or the dot operator? How can you prove it?