CSCI 2270 Computer Science 2: Data Structures
Fall 2003
Karl Winklmann

 


1.        bool Graph::sparse ()
          {
               int count = 0;
               for (int i = 0; i < n; i++)
                   for (int j = 0; j < n; j++)
                       if (edges [i][j])
                             count++;
   
               return (10*count < n*n);
          }
   

    
    
   
2. • CountingSort ALWAYS SAME
   • HeapSort NOT ALWAYS SAME
   • BucketSort NOT ALWAYS SAME
    
    
   
3. If the same 100 numbers are inserted into two heaps but in a different order, do we know that ...  
    
   
   • the same value is in the root in both heaps? YES
   • the same value is in the left child of the root in both heaps? NO
   • the same value is in the leftmost leaf in both heaps? NO
    
    
   

4.     bool Node::binary ()
       {
           if (nChildren > 2)
               return false;
   
           for (int c = 0; c < nChildren; c++)
               if (!child->binary ())
                   return false;
   
           return true;
       }
   

    
    
   
5. Note: This problem was not meant to be about "double hashing," in which case the answers change. But the problem statement did not say so, hence you get credit if your answers are correct for double hashing.
   • ... there must have been one or more collisions, i.e., entries whose hash function value was the subscript of an occupied position? Yes
   • ... there must have been one or more deletions? Yes
   • ... there must have been two or more collisions? No
   • ... there must have been two or more deletions? Yes
   • ... at least two of the four entries shown ended up at their hash index (i.e., did not get bumped further down)? No
    

   ---

   © 2003 Karl Winklmann

   3:08 PM, Tuesday, December 16, 2003