Java Reference
In-Depth Information
c) For each simulated minute of the day, consider the following:
If the next customer arrives, proceed as follows:
Say so.
Enqueue the customer.
Schedule the arrival time of the next customer.
If service was completed for the last customer, do the following:
Say so.
Dequeue next customer to be serviced.
Determine customer's service completion time (random integer from 1 to 4
added to the current time).
Now run your simulation for 720 minutes and answer each of the following:
a)
What is the maximum number of customers in the queue at any time?
b)
What is the longest wait any one customer experiences?
c)
What happens if the arrival interval is changed from 1 to 4 minutes to 1 to 3 minutes?
21.16
(Allowing Duplicates in a Binary Tree)
Modify Figs. 21.17 and 21.18 to allow the binary
tree to contain duplicates.
21.17
(Processing a Binary Search Tree of
String
s)
Write a program based on the program of
Figs. 21.17 and 21.18 that inputs a line of text, tokenizes it into separate words, inserts the words
in a binary search tree and prints the inorder, preorder and postorder traversals of the tree.
21.18
(Duplicate Elimination)
In this chapter, we saw that duplicate elimination is straightfor-
ward when creating a binary search tree. Describe how you'd perform duplicate elimination when
using only a one-dimensional array. Compare the performance of array-based duplicate elimination
with the performance of binary-search-tree-based duplicate elimination.
21.19
(Depth of a Binary Tree)
Modify Figs. 21.17 and 21.18 so the
Tree
class provides a method
getDepth
that determines how many levels are in the tree. Test the method in an application that
inserts 20 random integers in a
Tree
.
21.20
(Recursively Print a List Backward)
Modify the
List<T>
class of Fig. 21.3 to include meth-
od
printListBackward
that recursively outputs the items in a linked-list object in reverse order.
Write a test program that creates a list of integers and prints the list in reverse order.
21.21
(Recursively Search a List)
Modify the
List<T>
class of Fig. 21.3 to include method
search
that recursively searches a linked-list object for a specified value. The method should return a refer-
ence to the value if it's found; otherwise, it should return
null
. Use your method in a test program
that creates a list of integers. The program should prompt the user for a value to locate in the list.
21.22
(Binary Tree Delete)
In this exercise, we discuss deleting items from binary search trees. The
deletion algorithm is not as straightforward as the insertion algorithm. Three cases are encountered
when deleting an item—the item is contained in a leaf node (i.e., it has no children), or in a node
that has one child or in a node that has two children.
If the item to be deleted is contained in a leaf node, the node is deleted and the reference in
the parent node is set to null.
If the item to be deleted is contained in a node with one child, the reference in the parent
node is set to reference the child node and the node containing the data item is deleted. This causes
the child node to take the place of the deleted node in the tree.
The last case is the most difficult. When a node with two children is deleted, another node in
the tree must take its place. However, the reference in the parent node cannot simply be assigned to
reference one of the children of the node to be deleted. In most cases, the resulting binary search
