Note: For programming exercises, first draw a UML class diagram describing all classes and their inheritance relationships and/or associations.
1.Java Concept Matching.
Match each of the following Data Structures concepts.
stack
A Last In First Out (LIFO) data structure; how you would organize dishes of the same size if you placed them or removed them one at a time.
queue
A First In First Out (FIFO) data structure; the typical way people proceed on a water slide.
static structure
a structure whose size doesn’t change during the course of execution
dynamic structure
a structure whose size can change during the course of execution.
data structure
a description or construct of how collections of data are organized
abstract data type
a description of the type(s) of data to store, and the ways manipulate the data stored
push
a stack operation for adding an element to the top of the stack
pop
a stack operation for removing an element from the top of the stack
enqueue
a queue operation adding an element to the end of the queue
dequeue
a queue operation for removing an element from the beginning of the queue.
linked list
a collection of nodes linked together, typically in a linear fashion
node
a part of a linked list that holds one piece of data and may have a link out to one or more other nodes.
Fill in the Blanks.
Fill in the blanks.
2..
An Abstract Data Type consists of two main parts: and .
3..
An object that contains a variable that refers to an object of the same class is a .
4..
One application for a is to manage the method calls and returns in a computer program.
5..
One application for a is to balance the parentheses in an arithmetic expression.
6..
A operation is one that starts at the beginning of a list and processes each element.
7..
A vector is an example of a data structure.
8..
An array is an example of a data structure.
9..
By default, the initial value of a reference variable is .
10.Remove At.
Add a removeAt() method to the List class to return the object at a certain index location in the list. This method should take an int parameter, specifying the object’s position in the list, and it should return an Object.
11.Insert At.
Add an insertAt() method to the List class that will insert an object at a certain position in the list. This method should take two parameters, the Object to be inserted, and an int to designate where to insert it. It should return a boolean to indicate whether the insertion was successful.
12.Remove All.
Add a removeAll() method to the List class. This void method should remove all the members of the list.
13.List Size.
Write an int method named size() that returns the number of elements in a List.
14.List Contains.
Write an boolean method named contains(Object o) that returns true if its Object parameter is contained in the list.
15.List Tail.
The head of a list is the first element in the list. The tail of a list consists of all the elements except the head. Write a method named tail() that returns a reference to the tail of the list. Its return value should be Node.
16.Averaging a List.
Write a program that uses the ListADT to store a list of 100 random floating-point numbers. Write methods to calculate the average of the numbers.
17.List of Students.
Write a program that uses the ListADT to store a list of Student records, using a variation of the Student class defined in Chapter 11. Write a method to calculate the mean grade point average for all students in the list.
18.Copy List.
Write a program that creates a copy of a List. It is necessary to copy each node of the list. This will require that you create new nodes that are copies of the nodes in the original list. To simplify this task, define a copy constructor for your node class and then use that to make copies of each node of the list.
19.Stack Palindrome Test.
Write a program that uses a StackADT to determine if a string is a palindrome—spelled the same way backward and forward.
20.Stack Parentheses Matching Test.
Design and write a program that uses a Stack to determine whether a parenthesized expression is well-formed. Such an expression is well formed only if there is a closing parenthesis for each opening parenthesis.
21.Stack Brackets Matching.
Design and write a program that uses Stack s to determine whether an expression involving both parentheses and square brackets is well formed.
22.Append Two Lists.
Write a program that links two lists together, appending the second list to the end of the first list.
23.ArrayList based Stack.
Design a Stack class that uses a ArrayList instead of a linked list to store its elements. This is the way Java’s Stack class is defined.
24.ArrayList Based Queue.
Design a Queue class that uses a ArrayList instead of a linked list to store its elements.
25.LinkedList Students.
Write a program that uses the List<E> and LinkedList<E> classes to store a list of Student records, using a variation of the Student class defined in Chapter 11. Write a method to calculate the mean grade point average for all students in the list.
26.Phone Tree.
Write an implementation of the insert() method of the PhoneTree class described at the end of this chapter.
27.Phone Tree Node.
Write an implementation of the insert() method of the PhoneTreeNode class described at the end of this chapter.
28.List Design.
Challenge: Design a List class, similar in functionality to the one we designed in this chapter, that uses an array to store the list’s elements. Set it up so that the middle of the array is where the first element is placed. That way you can still insert at both the front and rear of the list. One limitation of this approach is that, unlike a linked list, an array has a fixed size. Allow the user to set the initial size of the array in a constructor, but if the array becomes full, don’t allow any further insertions.
29.Resize Array.
Challenge: Add a method to the program in the previous exercise that lets the user increase the size of the array used to store the list.
30.Recursive Print and Lookup.
Challenge: Recursion is a useful technique for list processing. Write recursive versions of the print() method and the lookup-by-name method for the PhoneList. (Hint: The base case in processing a list is the empty list. The recursive case should handle the head of the list and then recurse on the tail of the list. The tail of the list is everything but the first element.) Challenge: Design an OrderedList class. An ordered list is one that keeps its elements in order. For example, if it’s an ordered list of integers, then the first integer is less than or equal to the second, the second is less than or equal to the third, and so on. If it’s an ordered list of employees, then perhaps the employees are stored in order according to their social security numbers. The OrderedList class should contain an insert(Object o) method that inserts its object in the proper order. One major challenge in this project is designing your class so that it will work for any kind of object. (Hint: Define an Orderable interface that defines an abstract precedes() method. Then define a subclass of Node that implements Orderable. This will let you compare any two Node s to see which one comes before the other.)
