CHAPTER 15

Questions

1. The "B" in B-tree stands for "balanced".

2. I won't exhaust the differences here, but note that a binary tree node has at most two children, and the number of possible children on a given level is predetermined. In a B-tree, the number of children of a node varies more widely, and so does the number of nodes on a level. A binary tree can get out of balance; a B-tree cannot.

3-5. Left as an exercise.

6. A heap is a sequence of data nodes n1, n2, n3, n4, ... nmax in which ni <= n2i and ni <= n2i+1 for all i with 1 <= i <= max/2. In a heap every parent is greater than its child. A reverse heap has the opposite relationship between parents and children.

7. "Generic" means without respect to implementation. In particular, a generic data structure such as a heap can be constructed without worrying about the kind of data in the heap.

8. Left as an exercise.

9. An ARRAY OF LOC is, in a sense the most generic form of data of them all, because any other data is compatible with it when passed as a parameter. On the other hand, there are some technical limitations to this (procedure types), and type checking (why you use a high level language) is lost.

10-13. Left as an exercise.

14. This is fairly straightforward, but you will need a parameter of the type ADDRESS to serve as a pointer to the temporary location. After all, the procedure does not know the type and so cannot declare the temporary itself.

15. Left as an exercise.

16. Two that do are Java and Modula-2. A third is left as an exercise.

17. Defragmentation is the gathering together of chunks of memory so that unallocated memory is all in one contiguous chunk. Garbage collection refers to deallocating (and so making available again) chunks of memory no longer being referred to by any pointer.

18. Left as an exercise.

Problems

Note: At this stage, students should not need any problem solutions.