www.gibmonks.com

Main Page




Previous Page
Next Page

[Page 1036 (continued)]

Self-Review Exercises

21.1

Fill in the blanks in each of the following:

  1. A self-_____ class is used to form dynamic data structures that can grow and shrink at execution time

  2. The _____ operator is used to dynamically allocate memory and construct an object; this operator returns a pointer to the object.

  3. A(n)_____ is a constrained version of a linked list in which nodes can be inserted and deleted only from the start of the list and node values are returned in last-in, first-out order.

  4. A function that does not alter a linked list, but looks at the list to determine whether it is empty, is an example of a(n)_____ function.

  5. A queue is referred to as a(n)_____ data structure, because the first nodes inserted are the first nodes removed.

  6. The pointer to the next node in a linked list is referred to as a(n) _____.

  7. The _____ operator is used to destroy an object and release dynamically allocated memory.

  8. A(n)_____ is a constrained version of a linked list in which nodes can be inserted only at the end of the list and deleted only from the start of the list.

  9. A(n) _____ is a nonlinear, two-dimensional data structure that contains nodes with two or more links.

  10. A stack is referred to as a(n)_____ data structure, because the last node inserted is the first node removed.

  11. The nodes of a(n)_____ tree contain two link members.

  12. The first node of a tree is the _____ node.

  13. Each link in a tree node points to a(n) _____ or _____ of that node.

  14. A tree node that has no children is called a(n) _____ node.

  15. The four traversal algorithms we mentioned in the text for binary search trees are _____, _____, _____ and ______.

21.2

What are the differences between a linked list and a stack?

21.3

What are the differences between a stack and a queue?

21.4

Perhaps a more appropriate title for this chapter would have been "Reusable Data Structures." Comment on how each of the following entities or concepts contributes to the reusability of data structures:

  1. classes

  2. class templates

  3. inheritance

  4. private inheritance

  5. composition


[Page 1037]
21.5

Manually provide the inorder, preorder and postorder traversals of the binary search tree of Fig. 21.24.

Figure 21.24. A 15-node binary search tree.



Previous Page
Next Page