Questions
1. What does the "B" in B-tree stand for?
2. Explain all differences between B-trees and binary trees.
3. Devise a formula that takes as input the order of a B-tree and the number of levels it has, and produces the maximum storage capacity of the tree.
4. If a B-tree of order 2 has been employed to contain n items, what is the maximum number of levels (depth) that need to be searched to find an item?
5. Suppose the B-tree is changed to order three. Trace by hand what the data provided for testing should produce with each insertion and deletion, then recompile and relink run the test program with this change made and check your predictions
6. Define a heap. Define a reverse heap.
7. What does the word "generic" mean in the contest of this book so far, and why should software be written generically?
8. Outline the three methods detailed thus far for making software generic.
9. What are the major advantages and disadvantages of using ARRAY OF LOC or ADDRESS instead of the actual data type in a structure?
10. The cardinal data 23, 54, 2, 98, 34, 17, 9, 27,31, 3, 78, 9, 54, 12 arrives at a B-tree of order two. Show how the data is entreed.
11. The same data as in question 10 arrives at a B-tree of order three. Show how the data is entreed.
12. The same data as in question 10 arrives at a heap and is enheaped as it arrives. Show the result after each step.
13. The same data as in question 10 is in an array and is then heapsorted using the two step process detailed in the chapter. Show the transformations of the array one step at a time as the heap is first constructed and then sorted.
14. Write a generic swap routine that uses only the addresses of the items to be swapped. What additional parameter will be needed?
15. Look up and then detail here how your implementation deals with handles, if at all.
16. Some languages have built in garbage collections. Find at least three that do.
17. What is the difference between garbage collection and defragmentation?
18. Explain the comment (* don't care about right *) in the unused procedure IsLeaf found in the Heap implementation in section 15.4.
Problems
19. Add and test routines to traverse the supplied B-tree in a variety of ways, in the same manner as provided for in the Heap structure.
20. Revise the code for inserting an item in a B-tree so that it does not insert in the heap when an identical item is found there.
21. Alternately (it makes no sense to do both) revise the code for deletion from a B-tree so that it deletes all items with the same key.
22. Create a searchable database to store information on a collection. (Stamps, coins or sports cards will do.) Store the information for searching in the B-tree as it was implemented in this chapter.
23. Implement a B-tree ADT with linked lists of pointers and data nodes. Do the Init routine so that it takes a parameter that is the order of the B-tree.
24. Implement a B-tree that entrees a type ARRAY OF LOC, rather than a specific imported data type.
25. Implement a B-tree that entrees only the addresses of the data, not the data itself.
26. In the section on testing the Heap, a small routine to print out a heap in a manner resembling an actual tree was set up. Do the same for a B-tree and test it. (The tree view routine supplied in the chapter is rather primitive.)
27. Revise the code for inserting an item in a Heap so that it does not insert in the heap when an identical item is found there.
28. Alternately (it makes no sense to do both) revise the code for deletion from a Heap so that it deletes all items with the same key.
29. Implement a Heap that entrees an ARRAY OF LOC, rather than a specific imported data type.
30. Implement a Heap that entrees only the addresses of the data, not the data itself.
31. Implement a priority queue based on a heap as suggested in section 15.5.2.
32. Implement the same heap definition module given in section 15.3.1 as an array rather than as a tree.
33. Re-implement the binary tree of Chapter 14 with all the traverse methods shown in this chapter for the Heap.
34. Implement a structure such as the queue or the stack that operates on ARRAY OF LOC rather than on a specific imported data type.
35. Implement a forward (increasing) heapsort. Keep the same parameters for the heapsort itself, but add a procedure to set the direction of sorting as increasing or decreasing. Encapsulate the whole thing in a library module, making it reasonably generic in the process (use one of the three methods in the chapter) and then test it with two different data types.
36. Heapsort was implemented with a sift down procedure only. Re-do this with either a sift up procedure only or both a sift up and sift down procedure.
37. Test Heapsort against Quicksort on data sets of various sizes and determine which is better for random data and for already sorted data.
38. One might hypothesize that a simple sort is more efficient than a Heapsort for small data sets (as seemed to be the case for Quicksort.) Test Heapsort against Insert Sort on data sets of various sizes and determine at what point (if any) it makes sense to switch between the two.
39. Test the supplied generic list type using the ARRAY OF LOC using a data type that is a record and has a key field.
40. Implement the generic list type so that only addresses are enlisted, using the definition module in section 15.9.
41. Implement and test the module pSorting in section 15.10.1.
42. Conduct a test of sorting records based on a key field and determine whether it really is better to hold only the addresses in an array as opposed to the entire data structure.