Problem 1
Fill in the blanks in each of the following statements: a) A self- ______ class is used to form dynamic data structures that can grow and shrink at execution time. b) 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. c) A method that does not alter a linked list, but simply looks at it to determine whether it is empty, is referred to as a(n)______ method. d) A queue is referred to as a(n) ______ data structure because the first nodes inserted are the first ones removed. e) The reference to the next node in a linked list is referred to as a(n)_______ . f) Automatically reclaiming dynamically allocated memory in Java is called _______. g) 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. h) A(n)______is a nonlinear, two-dimensional data structure that contains nodes with two or more links. i) A stack is referred to as a(n)______ data structure because the last node inserted is the first node removed. j) The nodes of a(n)______ tree contain two link members. k) The first node of a tree is the______ node. l) Each link in a tree node refers to a(n)______ or______ of that node. m) A tree node that has no children is called a(n)______ node. n) The three traversal algorithms we mentioned in the text for binary search trees are ______, and______. o) Assuming that myArray contains references to Double objects________ occurs when the statement "double number = myArray[ 0 ];" executes. p) Assuming that myArray contains references to Double objects_______, occurs when the statement "myArray[ 0 ] = 1.25;" executes.
Problem 2
What are the differences between a linked list and a stack?
Problem 3
What are the differencesibetween 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) inheritance c) composition
Problem 6
Write a program that concatenates two linked list objects of characters. Class List Concatenate should include a method concatenate that 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. Method merge of class ListMerge should receive references to each of the list objects to be merged and return a reference to the merged list object.
Problem 8
Write a program that inserts 25 random integers from 0 to 100 in order into 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, then 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 words of the line in reverse order.
Problem 11
Write a program that uses a stack to determine whether a string is a palindrome (i.e., the string is spelled identically backward and forward). The program should ignore spaces and punctuation.
