Exercises

4.2. Define the data structure described in the last paragraph of Section 4.2 in

4.3. Assume that a first-in-first-out queue Q with elements of type To is imple-

4.4. Assume that the records of a linked list contain a key field of type integer.

4.5. Circular lists (see Fig. 4.54) are usually set up with a so-called list header.

4.6. A bidirectional list is a list of elements that are linked in both ways. (See Fig.

4.7. Does Program 4.2 work correctly if a certain pair <x, y> occurs more than

4.9. Write a program that reads a program text, identifies all procedure (subrou-

4.10. Draw the tree constructed by Program 4.3 if the input consists of the

4.11. What are the sequences of nodes encountered when traversing the tree of

4.12, Find a composition rule for the sequence of m numbers which, if applied to

Program 4.4, yields a perfectly balanced tree.

4.14. Define a data structure to represent n-ary trees. Then write a procedure

4.15. Assume that a tree is built upon the following definition of a recursive data

structure (see Exercise 4.1).

4.16. Ina file system a catalog of all files is organized as an ordered binary tree.

4.17. Ina tree structure the frequency of access of each element is measured empir-

4.18. The method of analyzing the tree insertion algorithm described in Sect. 4.5

4.19. Draw the balanced tree with 12 nodes which has the maximum height of

4.20. Find a sequence of x insertion keys so that procedure (4.63) performs each

4.21. Find a balanced tree with keys |... and a permutation of these keys so

4.22. What is the average path length of the Fibonacci-tree T7,,?

4.23. Write a program that generates a nearly optimal tree according to the

4.24. Assume that the keys 1, 2, 3,... are inserted into an empty B-tree of order

4.25. Write a program for the search, insertion, and deletion of keys in a binary

4.26. Find a sequence of insertion keys which, starting from the empty symmetric

4.27. Write a procedure for the deletion of elements in a symmetric binary B-tree.

4.28. Compare the performances of the insertion and deletion algorithm of binary

4.29. Modify the printing algorithm of Program 4.6 in such a way that it can be

4.30. If the amount of information associated with each key is relatively large

4.31. Consider the proposal to solve the clustering problem by constructing over-

4.32. Devise a scheme that performs insertions and deletions in a hash table

4.33. The primary drawback of the hash table technique is that the size of the

4.34. Very often keys are not integers but sequences of letters. These words may