1. Consider the following hash function, similar to hash functions discussed in class.
unsigned int
Hash( const string & key, const int h_size )
}
unsigned int value = 0;
for ( int i=0; ivalue = (value + key[i])*16;
return value % h_size;
{
(a) Is this a good hash function when h_size = 128? Why or why not?
(b) Suppose the statement in the for loop is changed to value = value*31 + key[i]; and
h_size = 131. Is this new hash function better than the above hash function or not?
Justify your answer.
2. (a) For a heap of height h, what are the smallest and largest possible values for the subscript index of the last element in the array? Assume the array index begins at 1.
(b) Use the previous result to ?nd upper and lower bounds on the height h of a binary heap with n elements.
(c) For a min heap with n elements, what are the possible array subscript locations for the third smallest value in the heap? Assume the array index begins at 1, and that all values are distinct. Justify your answer.
3. Show the array contents for the binary heap after each of the following sequences of operations.
Assume values are placed starting at array index location 1.
(i) insert 37, insert 77, insert 44, insert 63, insert 23, insert 41,
(ii) delete_max, insert 59, insert 83, insert 11, insert 19,
(iii) delete_max, delete_max
14. (a) Consider the following traversal, which we will call new-order traversal. The new-order traversal ?rst visits the root, then traverses the right subtree, and then traverses the left subtree, and uses the same order recursively. Does this traversal bear any simple relation to the three traversal methods discussed in class? Justify your answer.
(b) Suppose we are given the outputs of the preorder and inorder traversals of the nodes of a binary tree. Can the binary tree structure be constructed from these outputs? If yes,explain how. If no, explain why not. (Note: The binary tree to be constructed is not
restricted to be a binary search tree.)
(c) Can a binary search tree structure be constructed from just the preorder traversal output? (You may assume there are no repeated elements in the tree.)
5. (a) Show the contents of an initially empty AVL tree at the end of each of the following sequences of operations:
i. Insert(35); Insert(55); Insert(80);
ii. Insert(60); Insert(70); Insert(65);
iii. Insert(15); Insert(50); Remove(60);
iv. Remove(65); Remove(80); Remove(70);
(b) Find an example AVL tree such that removing a single (speci?c) value from the tree causes rebalancing to occur starting at two di?erent nodes.