CPSC 220 Fall 2004
Test 2 Review Exercises

1. Describe the O(NlogN) heap construction algorithm and justify its complexity.

   
   
   
   
   
   
   
   
   
   
   

2. Describe the O(N) heap construction algorithm and justify its complexity.

   
   
   
   
   
   
   
   
   
   
   

3. Describe the heapsort algorithm and give and justify its complexity.

   
   
   
   
   
   
   
   
   
   
   

4. Give the search time for each structure below. Justify your answers, and explain any assumptions you are making.
   1. heap

      
      
      
      
      
      
      
      
      
      
      

   2. hash table/chaining

      
      
      
      
      
      
      
      
      
      
      

   3. hash table/open addressing

      
      
      
      
      
      
      
      
      
      
      

   4. binary trie (argue that search is O(1))

      
      
      
      
      
      
      
      
      
      
      

   5. binary trie (argue that search is O(log N))