Chapter 14 Questions
Multiple Choice
1. Which of the following is a private element of the class ListQueue?
a. listPtr
b. isEmpty()
c. peekFront()
d. enqueue(const ItemType& newEntry)
2. Which of the following methods from ListQueue throws an exception?
a. isEmpty()
b. peekFront()
c. ListQueue()
d. dequeue()
3. In the class ListQueue, which method calls the list method insert?
a. isEmpty()
b. dequeue()
c. enqueue(const ItemType& newEntry)
d. the copy constructor
4. In the class ListQueue, which method calls the list method remove?
a. isEmpty()
b. dequeue()
c. enqueue(const ItemType& newEntry)
d. the copy constructor
5. In the class ListQueue, which method besides isEmpty calls the isEmpty method from the list
class?
a. listPtr
b. isEmpty()
c. peekFront()
d. enqueue(const ItemType& newEntry)
6. Given the following diagram, a chain of linked nodes with head and tail pointers:
How does this type of a linked list help us to implement a queue?
a. able to traverse the list from back to front
b. able to easily delete the node at the back/end of the chain
c. able to keep a sorted chain
Chapter 14 Questions
d. able to easily add a node to the back/end of the chain
7. In class LinkedQueue, where does neNodePtr point?
a. the back or end of the chain
b. the front or beginning of the chain
c. nullPtr
d. the next element of the queue
8. In the class LinkedQueue, what must the peekFront method do before returning the value at
the front of the queue?
a. traverse the chain
b. check that the queue is not empty
c. remove the node at the beginning of the chain
d. establish a pointer to the beginning of the chain
9. What would be the purpose of the following lines of code?
back = (back + 1) % DEFAULT_CAPACITY;
items[back] = newEntry;
a. enables a circular linked list implementation of a queue
b. eliminates rightward drift
c. enables a circular array implementation of a queue
d. keeps a linked list from running out of memory
10. Which of the following elements of ArrayQueue is not private?
a. back
b. count
c. front
d. isEmpty()
11. How does the isEmpty method of ArrayQueue class return the proper value?
a. return count == 0;
b. return front != back
c. return front / back == 0
d. return count < DEFAULT_CAPACITY
12. The text defined a class SL_PriorityQueue. What command was used to accomplish the
enqueue method?
a. insert(newEntry);
b. insertSorted(newEntry);
c. push(newEntry);
d. addItem(newEntry);
Chapter 14 Questions
True or False
1. Both stacks and queues can have either an array-based or a link-based implementation.
2. It is not possible to use an implementation of the ADT list to define a class of queues.
3. In the implementation of class ListQueue, the constructor creates a new instance of a list.
Omitting this step leads to incorrect execution instead of a syntax error.
4. In the implementation of class ListQueue, when the destructor is called, the list’s destructor
is not called.
5. A linear linked chain can represent a queue.
6. If you use a linear chain with only a head pointer to implement a queue, the enqueue operation
will have efficiency O(1).
7. In the class LinkedQueue, the addition of an item to an empty queue is treated as a special case.
8. A circular linked chain cannot represent a queue.
9. The nodes in a circular chain have next pointers that never contain nullptr.
10. Shifting to avoid rightward drift works well and is efficient.
11. A circular array eliminates rightward drift.
12. Using a front and back pointer in a circular array will indicate whether a queue is empty or
full.
13. Using the ADT list to represent a queue is not as efficient as using a linked chain directly.
14. It is poor design to use a sorted list to contain the entries of a priority queue.
15. The enqueue and dequeue operations for a queue require efficient access to both ends of the
queue.
Chapter 14 Questions
16. If you use a circular array to implement a queue, you must be able to distinguish between the
queue-full and queue-empty conditions.
Chapter 14 Questions
Short Answer
1. What is the disadvantage stated by the text for defining a class of queues quickly using a class of
lists?
2. Given the figure at the right:
What does this represent?
3. In the implementation of class ListQueue, why does the destructor have an empty body?
4. Consider implementing a queue with a linked-list. How do we improve the efficiency of adding a
new node to the end of a chain?
5. Given the diagram below at the right.
What does this represent?
6. If you use a circular chain that has only a tail pointer,
how do you access the data in the first node?
7. What strategy results in the phenomenon of “rightward drift”?
8. Given the diagram to the right:
What concept concerning queues does
this demonstrate?
9. If you are using a circular queue, how can you detect whether a queue is full or empty?
10. What is a pro and a con of using the ADT list to represent a queue?
11. Name two ADT structures which can be used to contain the entries of a priority queue.