CSCI 3300
Spring 2009
Additional exercises for final exam

1. If an algorithm sorts a list of n values by using comparisons, then, to within a constant factor, in the worst case, that algorithm must use at least

   1. log₂(n) comparisons.
   2. n/log₂(n) comparisons.
   3. n comparisons.
   4. n log₂(n) comparisons.
   5. n² comparisons.

   Answer

2. An efficient algorithm that implements a first-in-first-out queue uses how much time per insert or remove operation, in the worst case?

   1. O(1)
   2. O(log₂(n))
   3. O(n)
   4. O(n log₂(n))
   5. O(n²)

   Answer

3. Is it possible to create an implementation of binary search trees that is nondestructive (so that it builds new trees rather than modifying existing trees) or must every implementation of binary search trees work by making modifications to existing data structures?

   Answer