Problem 1
Fill in the blanks in each of the following: a. A self-_____ class is used to form dynamic data structures that can grow and shrink at execution time b. The _____ operator is used to dynamically allocate memory and construct an object; this operator returns a pointer to the object. c. 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. d. 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. e. A queue is referred to as a(n)_____ data structure, because the first mnodes inserted are the first nodes removed. f. The pointer to the next node in a linked list is referred to as a(n) _____. g. The _____ operator is used to destroy an object and release dynamically allocated memory. h. 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. i. A(n) _____ is a nonlinear, two-dimensional data structure that contains nodes with two or more links. j. A stack is referred to as a(n)_____ data structure, because the last node inserted is the first node removed. k. The nodes of a(n)_____ tree contain two link members. l. The first node of a tree is the _____ node. m. Each link in a tree node points to a(n) _____ or _____ of that node. n. A tree node that has no children is called a(n) _____ node. o. The four traversal algorithms we mentioned in the text for binary search trees are _____, _____, _____ and ______.
Problem 2
What are the differences between a linked list and a stack?
Problem 3
What are the differences between a stack and a queue?
Problem 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: a. classes b. class templates c. inheritance d. private inheritance e. composition
Problem 6
Write a program that concatenates two linked list objects of characters. The program should include function concatenate, which takes references to both list objects as arguments and concatenates the second list to the first list.
Problem 7
Write a program that merges two ordered list objects of integers into a single ordered list object of integers. Function merge should receive references to each of the list objects to be merged and reference to a list object into which the merged elements will be placed.
Problem 8
Write a program that inserts 25 random integers from 0 to 100 in order in a linked list object. The program should calculate the sum of the elements and the floating-point average of the elements.
Problem 9
Write a program that creates a linked list object of 10 characters and creates a second list object containing a copy of the first list, but in reverse order.
Problem 10
Write a program that inputs a line of text and uses a stack object to print the line reversed.
Problem 11
Write a program that uses a stack object to determine if a string is a palindrome (i.e., the string is spelled identically backward and forward). The program should ignore spaces and punctuation.
