Full Test Bank Ch.14 Chase Queues

Chapter 14: Queues

Multiple Choice Questions:

1) Which of the following is not a queue operation?

a) enqueue

b) dequeue

c) first

d) isEmpty

e) all of the above are queue operations

2) Which of the following methods removes an element from a queue?

a) enqueue

b) dequeue

c) first

d) pop

e) push

3) A queue is a ____________________ data structure.

a) LIFO

b) FIFO

c) link based

d) array based

e) none of the above

4) In an ideal implementations of a queue, all operations are ______________________ .

a) O(1)

b) O(n)

c) O(n log n)

d) O(n²)

e) it depends on the operation

5) In a array-based implementation of a queue that stores the front of the queue at index 0 in the array, the dequeue operation

a) is impossible to implement

b) has several special cases

c) has order O(n)

d) has order O(n²)

e) none of the above

6) The first operation of a queue is similar to the ______ operation of a stack

a) push

b) pop

c) isEmpty

d) size

e) peek

7) The queue operation that returns the element after the element at the front of the queue (that is, the second element in the queue) without removing the element at the front of the queue, is ________.

a) dequeue

b) dequeueNext

c) bypass

d) dequeueAndPeek

e) none of these is correct

8) Java provides the Queue _____ to create programs that use the queue data structure.

a) class

b) interface

c) parent

d) child

e) interface

9) One reason to define a Queue ADT (abstract data type) interface is

a) to tightly couple the data in the queue elements with the implementation of the queue data structure

b) to guide the programmer in how to implement the queue operations

c) to separate the operations from the ways that the operations can be implemented

d) both b) and c) are correct

e) none of these is correct

10) Which of the following statements is generally true about a linked list implementation of a queue?

a) Elements are added (enqueue) and removed (dequeue) at the front of the linked list.

b) Elements are added and removed at the rear of the linked list.

c) The first operation retrieves the element that was most recently added to the linked list.

d) The linked list implementation of a queue maintains references to both ends, the front and the rear, of the linked list.

e) All of the above statements are generally true about a linked list implementation of a queue.

11) Which of the following are affected by an enqueue operation?

a) the count of the number of elements in the queue

b)the reference to the rear of the queue

c) the reference to the front of the queue

d) both a) and b) are true

e) all of a), b), and c) are true

12) Which of the following should be performed first in a dequeue operation?

a) declare and initialize reference to the node to be removed from the queue

b) adjust the reference to the front of the queue

c) decrement the count of the number of elements in the queue

d) determine if the queue is empty

e) These steps can be performed in any order.

13) A circular array has 20 elements. The index (array subscript) ranges from 0 to 19. What is the subscript of the array element that follows the element with subscript 19?

a) 20

b) 0

c) 1

d) 21

e) an exception will be thrown

14) In a queue implemented using a circular array, rear refers to

a) the first available array element at the end of the queue

b) the element at the end of the queue

c) the number of elements remaining to be used at the end of the array

d) the number of elements available at the beginning of the array

e) none of the above

15) A double-ended queue allows

a) adding elements at one end and removing them from both ends

b) adding elements at both ends and removing them from one end

c) adding elements at one end, removing them from the other end, and viewing (first) elements at either end.

d) adding, removing, and viewing elements at either end.

e) none of the above

1) A queue is a FIFO structure.

2) It is only possible to implement a queue using an array-based structure.

7) In a circular array-based implementation of a queue, the elements must all be shifted when the dequeue operation is called.

4) Java provides a Queue class that implements a queue collection

5) A queue reverses the order of the elements that it processes

6) In a linked list implementation of a queue, the dequeue operation is more efficient if it removes elements from the front of the linked list than if it removes elements from the rear of the linked list.

7) In a linked list implementation of a queue, the enqueue operation compares the element to be added against the existing elements in the queue to determine the correct place to insert it.

8) The dequeue operation should throw an exception if it removes the last element in the queue.

9) In a circular array implementation of a queue, the front and rear references can change so that the value in front is greater than the value in rear.

10) In a circular array implementation of a queue, the remainder operator (%) can be used to calculate the value of the rear reference in an enqueue operation.

1) Suppose the following sequence of elements are added to a queue in the following order: 50, 26, 32, 18, 26, 51. After the elements are added, the following statement is executed three times. myQueue is the name of the queue object:

System.out.println(myQueue.dequeue());

What output is produced?

2) Write out the order of elements that are contained in a queue after the following operations are performed.

myQueue.enqueue(new Integer(8));

myQueue.enqueue(new Integer(6));

Integer num1 = myQueue.dequeue();

myQueue.enqueue(new Integer(3));

myQueue.enqueue(new Integer(4));

myQueue.enqueue(new Integer(15));

myQueue.enqueue(new Integer(12));

myQueue.enqueue(new Integer(9));

myQueue.dequeue();

myQueue.dequeue();

myQueue.dequeue();

myQueue.enqueue(new Integer(19));

3) List the five basic operations on a queue.

4) What is wrong with implementing a queue by using an array, where index 0 represents the front of the queue?

5) Explain how a queue can be implemented using an array, where the enqueue and the dequeue operations are both constant time operations (for simplicity, assume that you will never need to expand the capacity of the array).

6) Write an enqueue method for a queue implemented as a circular array. You may assume that you have access to a method called expandCapacity that will double the size of the array if necessary. The class has instance variables front and rear, which represent the indexes of the front and rear of the queue. It also has an integer variable called count that represents the number of elements in the queue, as well as an array of generic T types called queue that represents the queue.

7) Write an enqueue method for a queue implemented as a linked structure. You may assume that the class has references to LinearNode<T> objects called front and rear, which represent the front and rear of the queue respectively. You may also assume that the class has a variable called count, which represents the number of elements in the queue.

8) We maintain two reference variables for a singly linked list implementation of a queue, one for the front and the other for the rear of the queue. Efficiency considerations dictate which end should be used for the enqueue operation and which end should be used for the dequeue operation.

Are the same decisions indicated if a doubly linked list is used instead of a singly linked list?

9) The size of a queue using a linked list implementation is essentially unlimited. Is it possible to have an essentially unlimited size of a queue if an array-based implementation is used? Explain.

10) Suppose there is no count variable stored for the linked implementation of a queue. Is it still possible to implement a constant time size operation? How about if there is no count variable stored for an array based implementation of a queue?

11) Give an example of a real-life situation that can be modeled with a queue.

12) In an array-based implementation of a queue, what purpose is served by treating the array as circular? Is it required in order to have an array-based implementation of a queue?

13) Is it possible to re-use memory in an array-based implementation of a queue without treating the underlying array as circular?

14) What is gained by writing an interface to a Queue ADT (Abstract Data Type), as opposed to simply writing a Queue class, to solve a problem.

15) Write a size method for a linked list implementation of a queue that does not have a count member.