Ch7 - Queues, Deques, And Priority Queues Verified Test Bank

Chapter 7 - Queues, Deques, and Priority Queues

True/False (10)

1. Queues are used in operating systems.
2. The item most recently added to a queue is at the back of the queue.
3. Unlike a stack, a queue does not restrict access to its entries.
4. The Java Class Library interface for Queue has no operation to modify the contents of the front entry.
5. You can push, pop and get items at either end of the ADT deque.
6. The Queue interface extends the Deque interface.
7. A priority queue cannot have null entries
8. The null value can be used to signal failure to remove or retrieve an entry from a priority queue when it is empty.
9. The Java Class Library ADT PriorityQueue uses the compareTo method to determine how to order entries.
10. The ArrayDeque class implements the Stack interface.

Short Answer (5)

1. Draw the contents of the queue after the following statements execute. Clearly label the front and back of the queue.
   
   QueueInterface<String> bankLine = new LinkedQueue<>();
   bankLine .enqueue(“John”);
   bankLine .enqueue(“Matthew”);
   String next = bankLine .dequeue();
   bankLine .enqueue(“Drew”);
   bankLine .enqueue(“Heather”);
   bankLine .enqueue(“David”);
   next = bankLine .dequeue();
2. Draw the contents of the queue after the following statements execute. Clearly label the front and back of the queue.
   
   QueueInterface<String> bankLine = new LinkedQueue<>();
   bankLine .enqueue(“John”);
   bankLine .enqueue(“Matthew”);
   String next = bankLine .dequeue();

next = bankLine .dequeue();
bankLine .enqueue(“Drew”);
bankLine .enqueue(“Heather”);
next = bankLine .dequeue();
bankLine .enqueue(“David”);
next = bankLine .dequeue();

1. Describe what happens when the following code is executed.

QueueInterface<String> bankLine = new LinkedQueue<>();
bankLine .enqueue(“John”);
bankLine .enqueue(“Matthew”);
String next = bankLine .dequeue();
bankLine .enqueue(“Heather”);
next = bankLine .dequeue();
next = bankLine .dequeue();
bankLine .enqueue(“Nancy”);
next = bankLine .dequeue();
next = bankLine .dequeue();

1. Draw the contents of the deque after the following statements execute. Clearly label the front and back of the deque.

DequeInterface<String> waitingLine = new LinkedDeque<>();
waitingLine.addToFront(“Jack”);
waitingLine.addToFront(“Rudy”);
waitingLine.addToBack(“Larry”);
waitingLine.addToBack(“Sam”);
String name = waitingLine.getFront();

1. Draw the contents of the deque after the following statements execute. Clearly label the front and back of the deque.
   
   DequeInterface<String> waitingLine = new LinkedDeque<>();
   waitingLine.addToBack(“Adam”);
   waitingLine.addToFront(“Rudy”);
   waitingLine.addToBack(“Larry”);
   waitingLine.addToBack(“Sam”);
   waitingLine.addtoFront(“Jack”);
   String name = waitingLine.getFront();
   name = getFront();

Multiple Choice (30) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. Which of the following real-world events could be simulated using a queue?
   1. bank line
   2. a shared network printer
   3. restaurant reservation list
   4. all of the above
2. The ____ ADT organizes its entries according to the order in which they were added.
   1. queue
   2. stack
   3. list
   4. priority queue
3. What type of behavior defines a queue?
   1. first-in first-out
   2. first-in last-out
   3. last-in first-out
   4. none of the above
4. How does a queue organize it items?
   1. according to the order in which they were added
   2. by priority
   3. alphabetically
   4. randomly
5. Where does a queue add new items?
   1. at the back
   2. at the front
   3. in the middle
   4. randomly
6. Where will you find the item added earliest to a queue?
   1. at the front
   2. at the back
   3. in the middle
   4. randomly
7. The method for adding a new item to the back of a queue is called
   1. enqueue
   2. dequeue
   3. getFront
   4. none of the above
8. The method for removing an item from the front of a queue is called
   1. dequeue
   2. enqueue
   3. getFront
   4. none of the above
9. The method for retrieving the queue’s front entry without altering the queue is called
   1. getFront
   2. enqueue
   3. dequeue
   4. none of the above
10. A common alias for the queue method enqueue is
    1. put
    2. add
    3. insert
    4. all of the above
11. A common alias for the queue method dequeue is
    1. get
    2. remove
    3. delete
    4. all of the above
12. A common alias for the queue method getFront is
    1. peek
    2. get
    3. put
    4. all of the above
13. The dequeue method
    1. throws an exception if the queue is empty
    2. returns the item at the front of the queue
    3. removes the item at the front of the queue
    4. all of the above
14. After the following statements execute, what item is at the front of the queue?
    QueueInterface<String> zooDelivery = new LinkedQueue<>();
    zooDelivery .enqueue(“lion”);
    zooDelivery .enqueue(“tiger”);
    zooDelivery .enqueue(“cheetah”);
    String next = zooDelivery .dequeue();
    next = zooDelivery .dequeue();
    zooDelivery .enqueue(“jaguar”);
    1. “cheetah”
    2. “jaguar”
    3. “tiger”
    4. “lion”
15. After the following statements execute, what item is at the back of the queue?
    QueueInterface<String> zooDelivery = new LinkedQueue<>();
    zooDelivery .enqueue(“lion”);
    zooDelivery .enqueue(“tiger”);
    zooDelivery .enqueue(“cheetah”);
    String next = zooDelivery .dequeue();
    next = zooDelivery .dequeue();
    zooDelivery .enqueue(“jaguar”);
    1. “jaguar”
    2. “cheetah”
    3. “tiger”
    4. “lion”
16. When a counter enumerates simulated time units, it is called a(n)
    1. time-driven simulation
    2. clock simulation
    3. event-driven simulation
    4. all of the above
       
17. In order to modify the front entry of a queue
    1. you need a set method defined
    2. you need to dequeue the front entry, modify the contents, and then use the requeue method to place it back on the front of the queue
    3. you cannot modify it under any circumstances
    4. none of the above
18. The Java Class Library interface Queue method to put an entry on the back of a queue that throws an exception if the method fails is
    1. add
    2. offer
    3. put
    4. poll
19. The Java Class Library interface Queue method to put an entry on the back of a queue that returns false if the method fails is
    1. offer
    2. add
    3. put
    4. poll
20. The Java Class Library interface Queue method that retrieves and removes the entry at the front of a queue and throws a NoSuchElementException if the queue was empty is
    1. remove
    2. poll
    3. retrieve
    4. get
21. The Java Class Library interface Queue method that retrieves and removes the entry at the front of a queue and returns null if the queue was empty is
    1. poll
    2. remove
    3. retrieve
    4. get
22. The Java Class Library interface Queue method that retrieves the entry at the front of a queue but throws a NoSuchElementException if the queue was empty is
    1. element
    2. peek
    3. poke
    4. look
23. The Java Class Library interface Queue method that retrieves the entry at the front of a queue but returns null if the queue was empty is
    1. peek
    2. empty
    3. poke
    4. look
24. A deque ADT behaves
    1. like a queue
    2. like a stack
    3. both a & b
    4. none of the above
25. What item is at the front of the list after these statements are executed?
    
    DequeInterface<String> waitingLine = new LinkedDeque<>();
    waitingLine.addToFront(“Jack”);
    waitingLine.addToFront(“Rudy”);
    waitingLine.addToBack(“Larry”);
    waitingLine.addToBack(“Sam”);
    String name = waitingLine.getFront();
    1. Rudy
    2. Jack
    3. Larry
    4. Sam
26. What item is at the front of the list after these statements are executed?
    
    DequeInterface<String> waitingLine = new LinkedDeque<>();
    waitingLine.addToFront(“Jack”);
    waitingLine.addToFront(“Rudy”);
    waitingLine.addToBack(“Larry”);
    waitingLine.addToBack(“Sam”);
    String name = waitingLine.getBack();
    1. Rudy
    2. Jack
    3. Larry
    4. Sam
27. The ADT priority queue organizes objects
    1. according to priority of the objects
    2. alphabetically
    3. from front to back
    4. from back to front
28. What item is at the front of the list after these statements are executed?
    
    DequeInterface<String> waitingLine = new LinkedDeque<>();
    waitingLine.addToFront(“Jack”);
    waitingLine.addToBack(“Rudy”);
    waitingLine.addToBack(“Larry”);
    waitingLine.addToFront(“Sam”);
    String name = waitingLine.getFront();
    name = getBack();
    waitingLine.addtoBack(“Adam”);
    1. Sam
    2. Rudy
    3. Adam
    4. Jack
29. What item is at the front of the list after these statements are executed?
    
    DequeInterface<String> waitingLine = new LinkedDeque<>();
    waitingLine.addToBack(“Adam”);
    waitingLine.addToFront(“Rudy”);
    waitingLine.addToBack(“Larry”);
    waitingLine.addToBack(“Sam”);
    waitingLine.addtoFront(“Jack”);
    String name = waitingLine.getFront();
    name = getFront();
    1. Jack
    2. Rudy
    3. Adam
    4. Sam
30. The _____ ADT that has operations to add, remove, or retrieve entries at both the front and back of a queue is called a
    1. deque
    2. reversible queue
    3. reversible stack
    4. all of the above