www.gibmonks.com

Main 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.