CIS 671, Winter 2002
Homework 0: Partial Map, Binary Search Tree and Hash Table Review
  1. Partial Map.
    1. Define a Partial Map.
  2. Hash Table
    1. Given below is a hash table with 13 spaces. The keys 14, 28, 12, 27, 31, and 38 have been inserted in that order using the division/remainder hash function and the linear probe (next available space) collision algorithm. Insert the following keys: 34, 15, and 25.
      Address Key Collision
      0 38  
      1 14 27
      2 28  
      3 27  
      4 -  
      5 31  
      6 -  
      Address Key Collision
      7 -  
      8 -  
      9 -  
      10 -  
      11 -  
      12 12 38

  3. Binary Search Trees
    1. Given the binary search tree shown below, insert the keys "D" and "M".

    2. There are several algorithms for traversing a binary tree.
      1. Give the result of traversing the tree above in inorder.
      2. Give the result of traversing the tree above in postorder.
      3. Give the result of traversing the tree above in preorder.
    3. Which algorithm would you use to print the keys in the tree in alphabetical order? Give this traversal algorithm.

D. S. Kerr
January 2002