If the characters 'D', 'C', 'B', 'A' are placed in a queue (in that
order), and then
removed one at a time, in what order will they be removed?
- A. ABCD
- B. ABDC
- C. DCAB
- D. DCBA
Which of the following expressions evaluates to true
with approximate probability equal to P? (P is double and
0 <= P <= 1).
- A.
rand() < P
- B.
rand() > P
- C.
rand() < P * RAND_MAX
- D.
rand() > P * RAND_MAX
Multiple Choice Section 8.3 Implementations of the Queue ADT
|
Suppose we have a circular array implementation of the queue class, with ten
items in the queue stored at data[2] through data[11]. The CAPACITY
is 42. Where does
the push member function place the new entry in the array?
- A. data[1]
- B. data[2]
- C. data[11]
- D. data[12]
Consider the implementation of the queue using a circular array.
What goes wrong if we try to keep all the items at the front of
a partially-filled array (so that data[0] is always the front).
- A.
The constructor would require linear time.
- B.
The get_front function would require linear time.
- C.
The insert function would require linear time.
- D.
The is_empty function would require linear time.
In the linked list implementation of the queue class, where does
the push member function place the new entry on the linked list?
- A. At the head
- B. At the tail
- C. After all other entries that are greater than the new entry.
- D. After all other entries that are smaller than the new entry.
In the circular array version
of the queue class (with a fixed-sized array), which operations
require linear time for their worst-case behavior?
- A. front
- B. push
- C. empty
- D. None of these operations require linear time.
In the linked-list version
of the queue class, which operations
require linear time for their worst-case behavior?
- A. front
- B. push
- C. empty
- D. None of these operations require linear time.
If data is a circular array of CAPACITY elements, and last is an
index into that array, what is the formula for the index after last?
- A. (last % 1) + CAPACITY
- B. last % (1 + CAPACITY)
- C. (last + 1) % CAPACITY
- D. last + (1 % CAPACITY)
I have implemented the queue with a circular array, keeping track
of first, last, and count (the number of items in the array).
Suppose first is zero, and last is CAPACITY-1. What can you tell me about
count?
- A. count must be zero.
- B. count must be CAPACITY.
- C.
count could be zero or CAPACITY, but no other values could occur.
- D. None of the above.
I have implemented the queue with a linked list, keeping track
of a front pointer and a rear pointer. Which of these pointers will
change during an insertion into a NONEMPTY queue?
- A. Neither changes
- B. Only front_ptr changes.
- C. Only rear_ptr changes.
- D. Both change.
I have implemented the queue with a linked list, keeping track
of a front pointer and a rear pointer. Which of these pointers will
change during an insertion into an EMPTY queue?
- A. Neither changes
- B. Only front_ptr changes.
- C. Only rear_ptr changes.
- D. Both change.
Multiple Choice Section 8.4 Priority Queues
|
Suppose top is called on a priority queue that has exactly
two entries with equal priority.
How is the return value of top selected?
- A.
The implementation gets to choose either one.
- B.
The one which was inserted first.
- C.
The one which was inserted most recently.
- D.
This can never happen (violates the precondition)