Homework 6
Document last modified: 

  1. (3) Exercise 11.1-3 Hint: Assume that a successful search can choose to return the address of any node having the matching, duplicate key.
     
  2. (4) In a hash table where chaining is used the chain list keys are maintained in sorted order. Consider the advantage of the sorted order in describing the running time for successful searches, unsuccessful searches, insertions and deletions. Give an estimate and justification of the run time for each operation.
     
  3. (3) Exercise 11.3-4     Note: h(k) = ëm*((k*A) mod 1)û
     
  4. (3) Exercise 12.1-2

     

  5. (5) Show that if a node in a binary search tree has two descendants, then its successor has no left children and its predecessor has no right child.
     
  6. (3) Write the TREE-PREDECESSOR procedure.

Turn in

  1. Cover sheet with your name, C455, date, and Homework 6.
  2. Typed or neat handwritten answers.