Assigned: November 28th, 2001
Due: December 4th, 2001, in class
1. Binary trees
a. What is the maximum possible height of a tree with n nodes?
b. What is the minimum possible height of a tree with n nodes?
c. What is the maximum possible number of nodes in a binary tree of height h?
d. What is the minimum possible number of nodes in a binary tree of height h?
2. Show the result of traversing the following tree
6
/ \
2 7
/ \
1
4
/ \
3 5
a. Preorder
b. Inorder
c. Posorder
3. Binary search trees
a. Insert the following numbers into a binary search tree, in this order:
12, 4, 8, 6, 2, 9, 14, 16, 13, 15, 7, 5
b. Show the tree after deleting 16
c. Show the tree after deleting 4
4. Heaps
a. Perform the following operations on an initially empty min-Heap (parent data smaller than children data). Show all steps.
Insert(2), Insert(3), Insert(4), Insert(1), Insert(9), DeleteMin(), Insert(7), Insert(6), DeleteMin(),DeleteMin().
b. Below is the code for building a heap from an array of numbers
for (int i = Heap[0]/2; i >1; i--)
BubbleDown(Heap, i);
Where BubbleDown() takes a semiheap rooted at i and moves the item in index i down to its correct position by swapping with the smaller of its children, repeating the process until either both children are larger or there are no children (this function is called RebuildHeap() in your book).
Show the result of building a heap from the following array:
10, 13, 16, 14, 15, 1, 8, 7, 3, 9, 10
Do not forget that Heap[0] is the number of items in the heap.
5. Hash tables
Given the
hash function h(key) = key % tablesize, show the result of hashing {64, 73, 55, 28, 19, 37} into
tables of size 6, 7, and 9. For
each table size, show the result of hashing into an open hash table (chaining),
a closed hash table with linear probing, and a closed hash table with quadratic
probing.