Data Structures Sample Midterm
NOTE: Unless otherwise indicated, all trees are binary.

Given a tree with integers stored only at the leaf nodes, write a pseudocode
function that fills in entries into nonleaf 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.