Data Structures Sample Midterm

• Given a tree with integers stored only at the leaf nodes, write a pseudocode function that fills in entries into non-leaf nodes such that the entry at each internal node is the sum of all entries in leaves of subtree rooted at that node. Make sure your pseudocode has a complexity of O(n) where n is the number of nodes in the leaf.
• Write a pseudocode for computing the depth of each node in a tree. Make sure your code runs in O(n) time where n is the depth of the tree.
• Illustrate the heap after insertion of each of the following entries:
  4, 5, 6, 15, 9, 7, 20
  
• Insert the following sequence into a binary search tree and illustrate the tree after each insertion:
  3, 4, 5, 6, 7
  
• Insert the following sequence into an AVL tree and illustrate the tree after each insertion:
  3, 4, 5, 6, 7
  
• Illustrate a skip list and the search of key 32 in the following sequence. Assume that at each level we link alternate entries from previous level.
  12 4 43 7 99 65 68 1
  
• Assume that we use the hash function h(x) = (5x + 3) mod 13 to hash into a table of size 13. Illustrate the table after the insertion of the following sequence:
  1, 7, 23, 12, 6, 5
  Assume that collisions are resolved by chaining.