Computer Science 2:
Solutions for final
Tuesday, December 15, 2003
bool Graph::sparse ()
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (edges [i][j])
return (10*count < n*n);
- CountingSort ALWAYS SAME
- HeapSort NOT ALWAYS SAME
- BucketSort NOT ALWAYS SAME
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
bool Node::binary ()
if (nChildren > 2)
for (int c = 0; c < nChildren; c++)
if (!child->binary ())
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?
- ... there must have been one or more deletions?
- ... there must have been two or more collisions?
- ... there must have been two or more deletions?
- ... at least two of the four entries shown ended up at their
hash index (i.e., did not get bumped further down)?
© 2003 Karl Winklmann
3:08 PM, Tuesday, December 16, 2003