Homework 4 - Due via Electronic Turnin Friday, March 12 at 8:00 pm
61 points total
Updated Wed, March 10 at 4:30 AM - removed question 10 and made question 9
extra credit
This homework will be turned in electronically in ps or pdf format
1. (8 pts) Enqueue the following numbers in the given order into a Min Heap. Show
the heap after each enqueue. 12, 9, 21, 8, 1, 5, 4, and 2
2. (8 pts) Perform 8 dequeue operations on the final heap from question 1. Show
the heap after each dequeue,
3. (5 pts) Show that in an n-element heap there are at most
ceiling (n/(2^(h+1)) nodes at height h. (Leaves are considered to be at
height 0).
4. (6 pts) An empty table has a capacity of 100, and you insert 6 entries with keys
100, 0, 1199, 1299, 1399, and 2. Using linear probing and the basic hash
function (key mod size), where will these entries be placed in the table?
Where will they be placed with double hashing (with HF2 = 1 + (key mod 98))?
5. (6 pts) Use a hash table with size of 811 that uses seperate chaining to specify
where the following entries will be inserted. Use a basic hash function
(key mod size). Insert 811, 0, 1623, 2435, 3247, and 2.
6. (9 pts) Use a hash table of size 11 and the basic hash function (key mod size).
Insert the following items using quadratic probing, 2, 14, 21, 36, 70, 18,
47, 32, and 11.
7. (9 pts) Rehash the resulting table from problem 6 to a table size of 23.
8. (10 pts) Show the resulting 2-3 trees if we insert the elements
4, 6, 2, 9, 0, 5, 7, 3, 8, and 1 into an initially empty tree.
Insert in the order given. Show the
tree after each insert.
EXTRA CREDIT - (6 pts) Show the red-black trees that result after successively inserting the keys
in the order 41,
38, 31, 12, 19, and 8 into an initially empty red-black tree.
Show the tree after
each insert. (Be sure to include
a legend for your tree so we know which nodes are red and which are black)