1. Suppose a function reads in each record of Example 10.4 and creates a file consisting of every other prime number on the file. Show the state of the input and output files and their file pointers after the fourth record of the output file has been written.
2. Write a function to create the output file of Exercise 1.
3. Write a function to create reversedprime of Example 10.4, assuming the array a may only be of length 10 while reversedprime may contain many more entries.
4. How many writes and reads will be executed by the function merge if file 1 and file 2 are, respectively,
5. Write a function to create a sequential file that is the same as file 1, except that all records on file 1 that are also on file 2 do not appear.
a. Assume file 1 and file 2 records appear in sorted order based on the key field.
b. Assume file 1 and file 2 are not sorted, and you do not know how to sort a file.
6. Write a function to produce a new file that is the same as an input file except that all blanks have been deleted from it.
7. Write a function that takes two sequential files and appends the second file to the first.
8. Why are the sort procedures of Chapter 8 inappropriate for files?
9. Why does the number of passes required by a straight sort not depend on any initial ordering among records?
10. Write a function for the straight merge.
11. Modify the merge function of Section 10.3 so that it merges two runs embedded in files.
12. Write a function to distribute records as required by the natural merge.
13. Write a function for the natural merge.
14. Simulate the behavior of replacement-selection to verify that the average length run produced is 2m.
15. Why must Fibbonacci numbers govern the number of initial runs for three tapes in the polyphase sort?
16. a. If four tapes are used in a polyphase sort, what is the relation determining the initial distribution of runs?
b. Can you generalize to n tapes?
17. Write a function for the polyphase sort using three tapes.
18. Why do the movable read/write heads and surfaces act as tabs for a disk?
19. Suppose the master index of Section 10.7.3 does not fit on one cylinder. How may another directory level be created to serve as an index to the master index?
20. Why do B-trees allow more flexible use of a disk than directories implemented using prime and overflow areas?
21. Create a B-tree of order 4 to store the nametable records of Chapter 6. The records are to be ordered alphabetically so that the B-tree can be searched with the name field as key.
22. Write a function to insert a record into a B-tree of order m that is stored in internal memory.
23. Can you write the function of Exercise 22 so that it is independent of whether the B-tree is stored in internal or external memory? If so, write it. If not, explain why not.
24. Write a function to delete a record from a B-tree of order m that is stored in internal memory.
25. Why does the chaining of lowest-level nodes discussed in Section 10.7.4 allow more efficient traversal through a file?
26. Write a function to create a B-tree stored in internal memory.
27. Suppose we want to store variable length records in a B-tree. How may this be done?
28. Why is it not feasible to store all records in the root node of a B-tree so that only one seek is required?
29. A B-tree of order 3 is called a 2-3 tree, since each node has two or three successors.Although not useful for external storage, such a tree may rival AVL trees for an internal memory structure in which to store records. Compare its search, insertion, and deletion algorithms and its time requirements with those for AVL trees.
30. Write a search function for a B-tree of order m.
31. Write a function to traverse through the records of a B-tree in order by key value.
32. Suppose the individual records of Figure 6.5 are to be stored on a disk with the recordptr field of the nametable pointing to the address of an individual record on the disk. The address is a cylinder and surface specification. What is a reasonable way to allocate disk storage to the individual records?
33. Suppose records of a file were stored in a hash table, with buckets for random access by key, and linked in sequential order by pointers for sequential access. Compare the insertion and retrieval times of such an implementation with the use of B-trees.
1 2 8 10 13 15 40
3 7 10 12 17 20 45 50 60