1. Justify all the entries of Table 9.1 for the priority queue implementations.
2. Write two functions to insert and delete, respectively, records from a priority queue implemented as a heap.
3. a. Build a hash table for the twenty-seven names of the nametable of Chapter 6. Do not store duplicates. The table will be of size 31. Assign to each letter of this alphabet the integer corresponding to its position in the alphabet. For example A is assigned 1, E is assigned 5. Add the integers corresponding to every letter of a name and divide the sum by 31. The remainder is then the hash address of the name. For example, Jimmy Carter has the sum (10 + 9 + 13 + 13 + 25 + 3 + 1 + 18 + 20 + 5 + 18) = 135. Its hash address is 11. Use linear probing when a collision occurs.
b. How many probes were needed to insert each name?
4. Criticize the choice of hash function in Exercise 3.
5. Search the hash table of Exercise 3 for John Smith, and write down the probe addresses needed.
6. Show the state of hash tables (a) through (g) of Section 9.3 when key 019 is deleled.
7. Suppose that the eighteen keys are entered into the hash table of Section 9.3 in order, from largest to smallest. As you search for a key, you conclude that it is not in the table whenever you encounter a key value smaller than the search key as you trace out the linear probe path. Convince yourself that this is true, and that it will result in fewer probes for an unsuccessful search.
8. Write a function to build a hash table for each of the open-addressing and chaining techniques of Section 9.3.
9. Run each function of Exercise 8 with the input data and hash function of Exercise 3.
10. What is the maximum number of probes for an unsuccessful search of each of the hash tables (a)-(g) of Figures 9.4, 9.5, and 9.6?
11. Can you find a way to build a hash table as in Exercise 7 so that the sorted search can be done even if the input was not actually in sorted order?
12. How might the average number of probes be studied for a given hash function as in Exercise 3?
13. For m = 107, generate n random key values between 000 and 999 and build (by executing a program) hash tables (a) to (g) of Figures 9.4, 9.5, and 9.6 for these keys. Do this twenty-five times for each n and output the average number of probes to insert the n keys over the twenty-five samples. Do this repeatedly for a series of n values corresponding to usage ratios of approximately 0.50, 0.55, 0.60, . . ., 0.90. 0.95. Compare results of this simulation to your expectations.
14. Take the nametable names of Chapter 6 and grow a simple binary search tree (as in Section 9.4) when the names are input in the order in which they appear in that figure. The order is determined alphabetically by last name, first name, and then middle initial. Thus Robert Evans precedes Harry Truman. If a duplicate name occurs, do not enter it again in the tree.
15. Delete Paulina Koch from the binary search tree of Exercise 14, using the simple deletion algorithm of Section 9.4.
16. Discuss the advantages and disadvantages of storing the nametable entries of Chapter 6 in a sorted array, sorted chain, binary search tree, AVL tree, and hash table.
17. Write a function, search, with parameters keyvalue, p, and t, a pointer to the root node of a binary search tree. Search is to return with p pointing to the node of t in which keyvalue equals p?/FONT>key. If no such node exists, p should return with its value null.
18. Write a function, insertbst, with parameters keyvalue and t. It is to insert a node with keyvalue into the simple binary search tree t if no node exists with that key.
19. Write a function, de1etebst, with parameters keyvalue and t. It is to delete a node whose key equals keyvalue in the simple binary search tree t, if such a node exists.
20. Should a linked or sequential implementation be used for binary search trees grown "simply" when they will contain fifty integers picked at random from the first 1,000 integers? Why?
21. What is the minimum depth of a binary search tree storing 137 entries, and how may it be constructed in time O(n) for n entries?
22. Should a linked or sequential implementation be used for a binary search tree grown as an AVL tree when it will contain 50 integers picked at random from the first 1,000 integers? Why? (Cf. Exercise 20.)
23. Follow the same directions as in Exercise 14, but grow a binary search tree that is an AVL tree. It should be the same AVL tree that would result if it were grown by invoking insertavl of Section 9.4.6 for each input name.
24. Create a binary search tree, with the names of Exercise 23 in it, which has minimum possible depth.
25. Delete the rightmost node of the AVL tree grown in Exercise 23, using the recursive deletion algorithm of Section 9.4.6.
26. Modify the nonrecursive function insertavl so that indexing can be done as described in Section 9.4.6.
27. Modify the recursive function insertavl so that indexing can be done as described in Section 9.4.6.
28. Why does growing and then inorder traversing an AVL tree correspond to an O(n lg n) sort?
29. Write a function search, with parameters indexvalue, p, and t. It is to return with p pointing to the node, if it exists, in the AVL tree t, whose index field is equal to indexvalue. P should be null if there is no such node.
30. How might we estimate the relation between the average depth of a simple binary search tree grown randomly and n, the number of inputs?
31. Suppose AVL trees are grown randomly. That is, each of the n ! arrangements of n distinct inputs is equally likely to occur. Starting with the null tree, insertavl is invoked for each input. How might the average depth of such AVL trees be estimated as a function of n?