SAMPLE EXAM 2 - ANSWERS

1. (a)          f(4)
              /      \
             /        \
           f(3)     2*f(2)
           /  \      /   \
        f(2) 2*f(1) f(1) 2*f(0)
        /  \
      f(1) 2*f(0)

                 11           f(4) = 11
              /      \
             /        \
            5         2*3
           /  \      /   \
          3  2*1    1   2*1
        /  \
       1  2*1

   (b) binary search, 30 guesses
   (c) if n==0:
           return 1
       else:
           return 3 * power3(n-1)
   (d) three concentric circles:
       one with radius 100 centered at (100,100) (touches sides of grid)
       one with radius 60 centered at (100,100)
       one with radius 20 centered at (100,100)

2. (a) 255 (one less than the next power of 2)
   (b) 11111111 --flip bits--> 00000000 --add 1--> 00000001 = 1
       so original value 1111111 is -1
   (c) D9
   (d) 1
   (e) B
   (f) green: 0x40 (hex 40) = 01000000 in binary = 64 in decimal
   (g) lossy
   (h) 11 10000 10010 0 101 = STARE
       9 letters requires 4 bits for a fixed-width code

3. (a) Bucket 1: 34
       Bucket 7: 18, 29
       Bucket 10: 98
       [ [], [34], [], [], [], [] , [], [18,29], [], [], [98] ]
       O(1)
   (b) array
       linked list
       array
   (c)                  1
           2   6     3  3  2
         5 5 7 7 42 42 42 42 21
       9 9 9 9 9  9  9  9  9  9 30
   (d) Seven edges:
       Between buildings 0 and 2, cost 3
       Between buildings 0 and 5, cost 7
       Between buildings 1 and 3, cost 4
       Between buildings 1 and 4, cost 5
       Between buildings 1 and 5, cost 1
       Between buildings 2 and 5, cost 6
       Between buildings 3 and 4, cost 2

4. (a)          73
             /      \
           31        92
             \      /
              56  80
             /  \
            42  66

   (b) minimum levels: 10 (which can accommodate up to 1023 nodes)
       maximum levels: 1000 (one node per level)
   (c)         71
              /  \
           39      43
          /  \    /  \
        28   17  12   20
       / 
      4 
   (d) left child is at index 10
       right child is at index 11
   (e) Start at the root and follow right branches until there is
       no right branch.

5. (a) 0  0  0
       0  0  0
       0  1  1
       0  1  1
       0  0  0
       1  0  1
       0  0  0
       1  0  1
   (b) Picture description (you should draw the picture using correct gates):
       A and C going into an AND gate
       A going into a NOT gate and then that and B going into an AND gate
       The outputs of the AND gates going into an OR gate
       The output of the OR gate is labeled S
   (c) 128
   (d) x <= 0 and y != 100