CSCI 311 Exam 2 Review Questions

• Identify the following:
  • binary tree
  • Horner's rule
  • postorder/preorder/inorder traversal
  • binary search tree
  • symbol table/dictionary
  • rotation (left, right)
  • balanced tree
  • simple uniform hashing
  • randomized binary search tree
  • red-black tree
  • hash function
  • cluster
  • counting sort
  • radix sort
  
  
  
• True or false (explain your answer): A symbol table can be efficiently implemented by a heap.

• Given a set of keys, show step by step how radix sort works on the data. Example: Show the stages in sorting the keys below using least significant digit radix sort:

  ABA
  DBB
  DDD
  ABD
  BBD
  DBA
  CAC
  CAB
  BAC
  CDA
  ADC

• Explain how a key is inserted at the root of a binary search tree. Include an example that shows multiple insertions.
  
  
• A search in an n-node red-black tree takes at most 2 lg (n+1) comparisons. True or false? Explain your answer.
  
  
• Give the definition of a red-black binary search tree.
  
  
• Grow the following binary tree (show the tree after each insertion):

     insert 15
     insert 13
     insert 8
     insert 20
     insert 19
     insert 1
     insert 6
     insert 10
     insert 5

  
  
  
• Using the keys: 19  1  6  17  16  8  24
  
  
  
  • Show the growth of the BST that results from inserting each successive key at the root (show every rotation).
    
    
  • Show the growth of a red-black tree. (Show each individual step when you fix up the tree, including rotations and color changes.)

• In addition to the requirement that it be deterministic, what are the two main desired properties of a good hash function?
  
  
• What advantages does using a prime number as the size of a hash table provide? Are all primes equally as good?
  
  
• Describe a hash function for a string. Write code or pseudocode for your answer.
  
  
• What will be the effect of a hash function returning the same value for every key when the table uses:
  
  
  
  • Chaining?
    
    
  • Open addressing using linear probing?
  
  
  
• Given a sequence of keys, show how they would be inserted into a hash table of size m using linear probing. For each key inserted, give the number of collisions it is involved in before it reaches its place in the table.
  
  
• Given a sequence of keys, show how they would be inserted into a hash table of size m using double hashing. Use
  
      h₂(k) = k % (m-1) + 1
  
  as the second hash function. For each key inserted, give the number of collisions it is involved in before it reaches its place in the table.