1. a. Consider the Suggested Assignments of Chapter 11. Suppose only 200 memory elements are available for lists to store successors. Given an example of a problem with fewer than twenty objects for which the implementation of Assignment 1 will work but the implementation of Assignment 2 will fail. Assume count and succ have length 20, the lists array of (1) has length 200, and the lists array of (2) is 20 ?10.
b. Can you find such an example for which Assignment 2 works but Assignment 1 fails?
2. a. Consider two implementations. First, a total of 50 memory elements in an array are to be dynamically allocated and reclaimed so that a binary tree (in linked representation) as well as a stack may be stored in the array. Second, an array of length 35 is to hold the binary tree, and another array of length 15 is to implement the stack. Each array is dynamically managed. The binary tree is to be preorder traversed using the stack. Give an example of a binary tree, with fewer than 35 nodes, that may be successfully traversed with the first implementation but not the second.
b. Suppose that after a node is accessed and processed, its storage may be reclaimed. Give an example of a binary tree with fewer than 35 nodes that may be successfully traversed with the first implementation but not the second.
3. In Exercise 1, the lists array of (1) functioned as a heap. Why was its storage management so simple?
4. In Exercise 2, the arrays functioned as heaps. Why was the first implementation able to do traversals that the second could not do?
5. In the first implementation of Exercise 2(b), suppose that, after a node is accessed and processed, it is simply put onto the available space list.
a. Is the head of the tree a dangling reference?
b. Are fixed-size or variable-size nodes being dealt with?
c. After your answer to Exercise 2(b) is traversed, what will be garbage, and what will be on the list of available space?
6. This is the same as Exercise 5, except that, after a node is accessed and processed, it is not put onto the available space list. After the binary tree has been traversed, the head of the tree is set to null.
7. Why is compaction not necessary with fixed-size nodes?
8. Suppose Example 13.3 deals with three binary trees. Each node has an integer valued info, leftptr, and rightptr field. The stack needs elements that are also integer valued. An integer array of length l is used as a heap in which nodes of the binary trees and the stack are stored. Assume one additional field is used for each node to indicate its length. Design a storage allocation scheme and write an appropriate avail function.
9. a. Suppose in Exercise 8 that when a node of a binary tree is deleted, its predecessor node will be changed to point to the left successor of the deleted node. Write a function delete that carries out this deletion and also returns the storage used by the deleted node to a list of available space.
b. How would the delete function change if reference counters were used as a reclamation scheme?
10. Write avail for the two-way circular list implementation for
a. Randomly ordered list entries.
b. List entries in order by size
c. List entries in order by address
11. Write avail for the buddy system implementation.
12. Write a reclaim function for the buddy system.
13. Why will garbage collection take a longer time when many nodes are in use and a shorter time when few nodes are in use?
14. What are the disadvantages of reference counters compared to garbage collection?
15. Write a function to traverse a list-structure with shared sublists to reclaim storage of a sublist whose reference count has gone to zero.
16. Write a function to insert a node in a threaded binary tree t. The node is to be inserted as the node accessed next in an inorder traversal of t after node.pred is accessed.
17. Write a function to delete a node in a threaded binary tree t. The deleted node is to be node.p.
18. Write a function to return a pointer to the predecessor of node.p in a threaded binary tree t.
19. Write a function to read information into the info fields of a binary tree t, implemented using pointer variables. The info fields will contain character strings of up to twenty characters. The input is given in the order that the info fields would be accessed in a preorder traversal of t.
20. How will your solution to Exercise 19 change if the binary tree t is implemented as a threaded tree?
21. Implement the transformation of Section 7.6.1 using a list implementation for the stack. The binary tree is implemented using pointer variables as a threaded tree. Assume the general tree is given by a two-dimensional array of size 50 ?50. If the [i,j] entry of the array is 1, then node j is a successor of node i; if the [i,j] entry is 0, then node j is not a successor of node i.
22. This is the same as Exercise 21 except that the general tree will be given by a list of successors for each node. These lists should be pointed to by pointer variables, one for each node of the general tree. The binary tree should be a link-inversion tree.
23. Suppose input, representing a general tree, is given as a sequence of pairs. A pair i, j implies that node j is a successor of node i. A sentinel pair has its i, j values equal. For example, the general tree of Figure 7.13 might be input as B,F A,C D,J I,K I,L C,H B,E I,M A,D D,I A,B B,G X,X. Write a function that will create the successor lists of Exercise 22.
24. Simulate the preorder traversal implementation for the link-inversion traversal of the binary tree of Figure 13.10.
25. Simulate the preorder traversal implementation for the Robson traversal of the binary tree of Figure 13.10.
26. Why will there always be enough storage in the binary tree, during a Robson traversal, for the stack of root nodes whose left subtrees are nonnull, whose traversal has been completed, and whose right subtrees are being traversed?
27. What purpose does the stack of Exercise 26 serve in the Robson traversal?
28. Write a function to do an inorder traversal of a threaded binary tree t.
29. Write a function to do a link-inversion traversal of a binary tree t assuming the tree is implemented using pointer variables.
30. Write a function to do a Robson traversal of a binary tree t assuming the tree is implemented using pointer variables.