Deck 7: Queues and Deques

Question 1

A queue is a LIFO (last-in, first-out) list.

Answer 1

False

Question 2

The last element placed in a queue is the only visible item.

Answer 2

False

Question 3

Which of the following functions represents an operation that is specified in a Queue ADT?

A) sort
B) top
C) front
D) merge

Answer 3

front

Question 4

Consider the following set of operations performed against a string type queue called my_queue.
Which string is output?

A) First
B) First Come
C) First Serve
D) Serve

Question 5

If exercised first, which of the following choices in the Maintain_Queue program will cause a run-time error?

A) pop
B) push
C) front
D) size

Question 6

A queue is similar to a(n) __________ in that you can insert an item at one end and remove it from the other.

Question 7

The standard library defines the queue as a(n) __________ class that takes any of the sequential containers as a template parameter.

Question 8

Insertions are at the __________ of a queue, and removals are from the front.

Question 9

The number of elements in an instance of Linked_Queue.tc is changed by functions push and __________.

A) empty
B) size
C) front
D) pop

Question 10

A complete definition and implementation of the queue class would include a copy constructor, assignment operator, swap function, and __________ as required by the "rule of three."

Question 11

Shifting the elements in a queue based on a linear array is an __________ operation.

A) O(1)
B) O(n)
C) O(n²)
D) O(n!)

Question 12

Suppose my_queue contains the symbols % $ @ ! #in order from front to rear. After three pop operations, which symbol is at the front of the queue?

A) $
B) @
C) !
D)#

Question 13

Suppose that circular_queue, which is based on a circular array, stores the items 1, 1, 2, 3, 5, 8 in order from front to rear. If the first two items are deleted, which element does the rear marker point to?

A) 2
B) 3
C) 5
D) 8

Question 14

In the Array_Queue.tc, the cost of reallocating is __________ across each insert operation.

Question 15

All three implementations of the Queue ADT are comparable in terms of computation time.

Question 16

C++ stores a copy of the data for a queue element in each node in addition to the links.

Question 17

A(n) __________ is an abstract data type that combines the features of a stack and a queue.

Question 18

The std::deque supports random-access __________ (not supported by either the stack or the queue).

Question 19

The current capacity of the deque is defined by the size of the circular array times the size of a(n) __________ block.

Question 20

Which of the following is the critical line missing from the dequeu class pop_front () function?

A) deleter[] num_items;
B) delete[] the_data.front();
C) delete[] offset;
D) delete(the data_front());

Question 21

__________ is a technique used to study the performance of a physical system by using a physical, mathematical, or computer model of the system.

Question 22

In the context of serving airline passengers, a(n) "__________" strategy would be to serve any frequent flyer waiting in line before serving the regular passengers.

A) democratic
B) global
C) elitist
D) biased

Question 23

To run a computer simulation, we must keep track of the current time by maintaining a clock that is set to an initial time of __________.

Question 24

In the simulation for serving airline customers, the queue data structure is utilized to store Agent objects.

Question 25

In object-oriented design, when one object sends a __________ to another, the receiving object should have a function that sends a response.

A) frame
B) datagram
C) packet
D) message