Chapter 13 Questions
Multiple Choice Questions
1. A priority queue orders its items by ______.
a. position
b. value
c. priority value
d. size
2. The first item to be removed from a priority queue is the item ______.
a. at the front of the priority queue
b. at the end the priority queue
c. with the highest value
d. with the highest priority value
3. Which data structure represents a waiting line and limits insertions to be made at the back of the data structure
and limits removals to be made from the front?
a. Stack.
b. tree.
c. Linked list
d. Queue.
4. Which of the following characterizes a stack?
a. FIFO
b. LIFO
c. FILO
d. LILO
5. Which of the following characterizes a queue?
a. FIFO
b. LIFO
c. FILO
d. LILO
6. Which of the following is not an ADT Queue operation as presented by the author?
a. test if queue is empty
b. add new entry to back of queue
c. add new entry to front of queue
d. get entry that was added earliest to the queue
7. Which of the following ADT Queue operators does not have return type specified as bool?
a. isEmpty
b. dequeue
c. peekFront
d. enqueue
8. Which of the following ADT Queue operators has a parameter?
a. isEmpty
Chapter 13 Questions
b. dequeue
c. peekFront
d. enqueue
9. Given the following queue operations on an empty existing queue called nameQueue.
nameQueue.enqueue(Sid)
nameQueue.enqueue(Sal)
nameQueue.enqueue(Sue)
nameQueue.enqueue(Sam)
nameQueue.dequeue()
display (nameQueue.peekFront())
What name is displayed?
a. Sid
b. Sal
c. Sue
d. Sam
10. Given the following queue operations on an empty existing queue called nameQueue.
nameQueue.enqueue(Bob)
nameQueue.enqueue(Bill)
nameQueue.enqueue(Bud)
nameQueue.dequeue()
nameQueue.enqueue(Boo)
What is now the contents of the queue (with front of the queue listed leftmost)?
a. Bob, Bill, Bud
b. Bob, Bud, Boo
c. Bill, Bud, Boo
d. Boo, Bud, Bill
11. Given two initially empty queues, queue1 and queue2 and the following commands.
queue1.enqueue(1)
queue1.enqueue(2)
queue2.enqueue(3)
queue2.enqueue(4)
queue1.dequeue()
queueFront = queue2.peekFront()
queue1.enqueue(queueFront)
queue1.enqueue(5)
queue2.dequeue()
queue2.enqueue(6)
What are now the contents of What is now the contents of queue1 (with front of the queue listed leftmost)?
a. 2, 3, 5
b. 5, 3, 2
c. 4, 6
d. 6, 4
12. Given two initially empty queues, queue1 and queue2 and the following commands.
queue1.enqueue(1)
queue1.enqueue(2)
Chapter 13 Questions
queue2.enqueue(3)
queue1.enqueue(4)
queue1.dequeue()
queueFront = queue1.peekFront()
queue1.enqueue(queueFront)
queue2.enqueue(5)
queue1.dequeue()
queue2.enqueue(7)
What is the sum of the contents of queue2?
a. 4
b. 15
c. 19
d. none of these
13. According to the text, the first step in simulating a system is to do what?
a. write a computer program
b. time events with a stopwatch
c. construct a mathematical model
d. hire a lawyer
14. An algorithm performing simulation of an oft repeated cycle, measuring the times and generating statistics is
called what?
a. customer loop
b. timing loop
c. statistical loop
d. event loop
15. Which of the following are not position-oriented ADTs?
a. bag
b. stack
c. list
d. queue
16. Which of the following would be an example of a value-oriented ADT?
a. bag
b. priority queue
c. list
d. stack
17. For a stack, the push method places a new item onto the stack. What method for the queue would do a similar
task?
a. dequeue
b. isEmpty
c. enqueue
d. peek
18. For a queue, the dequeue removes the first item. What method for the stack is used to remove the appropriate
item?
Chapter 13 Questions
a. peek
b. poke
c. enqueue
d. pop
19. Which ADT would be best use to model the customers at a bakery who take numbers to mark their turn?
a. queue
b. stack
c. list
d. bag
20. You are writing a simple word processor. What ADT would be best to use which would allow the typist to
correct typing errors by using the Backspace key.
a. queue
b. stack
c. list
d. sorted list
21. In an event driven simulation, how is simulated time advanced?
a. by a single time unit
b. by a stop watch
c. advanced to the time of the next event
d. by a calendar
22. You wish to model who gets to land first as airplanes arrive at a busy airport. What kind of simulation would
this be?
a. time-driven simulation
b. customer-driven simulation
c. a sorted list
d. event-driven simulation
23. Lining up to buy a movie ticket or being put on hold by a computerized phone system are both examples of
what type of ADT?
a. queue
b. stack
c. list
d. sorted list
24. Which of the following tasks would be a good application of the ADT Queue?
a. generating random numbers for a game
b. reading a string of characters
c. keeping a grocery list
d. parsing a mathematical expression such as (9 + 5) * 7^ 2
25. What ADT would be used along with a queue to determine if a string is a palindrome?
a. list
b. sorted list
c. stack
d. priority queue
Chapter 13 Questions
26. You are making a “to do” list for this week. You brainstorm all the things which need your attention, then you
arrange them from most important to least. You have just used what kind of ADT?
a. list
b. sorted list
c. stack
d. priority queue
27. An event list contains all future arrival events and what else?
a. departure events
b. event loops
c. clock time
d. externally generated events
28. Which of the following is not a similarity between a stack and a queue as described by the text?
a. both have an isEmpty method
b. both can retrieve an item from any position
c. both can insert an entry at one end of the structure
d. both can retrieve an entry from one end of the structure
29. A large corporation is facing financial troubles and finds that they must do a reduction in force (RIF). The
people who were most recently hired must be let go. This is an example of which ADT?
a. bag
b. list
c. stack
d. queue
Chapter 13 Questions
True/False Questions
1. Queue is a First-in-Last-out data structure. That is, the last element inserted into a queue is removed first.
2. Queues are important in simulating and analyzing the behavior of complex systems.
3. It is possible to use a queue in conjunction with a stack to reverse the order of occurrences of a sequence of
items.
4. If you create a queue of assignments and access the queue by due dates of the assignments this is called a
priority queue.
5. The goal of simulation is to generate reports of transactions.
6. An even driven simulation simulates the ticking of a clock.
7. The ADT bag does not order its entries.
8. The isEmpty function for a stack does a much different task than the same function for a queue.
9. You are put on hold when you call customer service. The automated system tells you an approximation of how
long a wait you will have. This is most likely being modeled by a queue.
10. You are watching old reruns of M.A.S.H. You notice that when a group of casualties arrive, the doctors and
nurses are, in effect using an ADT stack to determine who goes to the operating room first.
Chapter 13 Questions
Short Answer Questions
1. Describe how you would use a queue and a stack to evaluate if a string is a palindrome.
2. Give an example the difference between externally and internally generated events in an event-driven
simulation.
3. In a simulation, what does an event list contain?
4. What queues were required for the bank simulation algorithm as described in the text?
5. Describe the similarities of the queue and the stack.
6. List differences between the list as opposed to the stack or queue.
7. What kind of operations would be required for accessing items in a priority queue?
8. Give some examples where the importance of an object depends on criteria other than when it is placed into a
container. What is the best ADT choice for that container?
9. Give a definition of a priority queue.
10. Describe the difference between a queue and a priority queue.
11. Give some examples of a applications in computer science where a queue useful.
12. Describe how tracking your assignments can be accomplished by a special ADT.
Chapter 13 Questions
13. What is the goal of a computer simulation?
14. We are simulating customers arriving at a bank and their transactions being processed. How do we determine
when and how long these events occur?
15. Given two initially empty queues, queue1 and queue2 and the following commands.
queue1.enqueue(4)
queue1.enqueue(3)
queue2.enqueue(7)
queue1.enqueue(6)
queue1.dequeue()
queue1.enqueue(queue2.peekFront())
queue2.enqueue(queue1.peekFront())
queue1.dequeue()
queue2.enqueue(7)
List the contents of both queues with the front of the queue leftmost.