Questions Chapter 4 Flashcards
Suppose you push 10, 20, 30, and 40 onto the stack. Then you pop three items. Which one is left on the stack?
10
Which of the following is true?
a. The pop operation on a stack is considerably simpler than the remove operation on a queue.
b. The contents of a queue can wrap around, while those of a stack cannot.
c. The top of a stack corresponds to the front of a queue.
d. In both the stack and the queue, items removed in sequence are taken from increasingly high index cells in the array.
b. The contents of a queue can wrap around, while those of a stack cannot.
What do LIFO and FIFO mean?
Last In First Out, First In First Out.
True or False: A stack or a queue often serves as the underlying mechanism on which an ADT array is based.
False.
Assume an array is numbered with index 0 on the left. A queue representing a line of movie-goers, with the first to arrive numbered 1, has the ticket window on the right. Then:
a. there is no numerical correspondence between the index numbers and the movie-goer numbers
b. the array index numbers and the movie-goer numbers increase in opposite left-right directions
c. the array index numbers correspond numerically to the locations in the line of movie goers.
d. the movie-goers and the items in the array move in the same direction.
b. the array index numbers and the movie-goer numbers increase in opposite left-right directions
As other items are inserted and removed, does a particular item in a queue move along the array from lower to higher indices, or higher to lower?
Doesn’t move.
Suppose you insert 15, 25, 35, 45 into a queue. Then you remove three items. Which one is left?
45
True or False: Pushing and popping items on a stack and inserting and removing items in a queue all take O(N) time.
False
A queue might be used to hold:
a. the items to be sorted in an insertion sort
b. reports of a variety of imminent attacks on the start ship Enterprise
c. keystrokes made by a computer user writing a letter
d. symbols in algebraic expression being evaluated
c. keystrokes made by a computer user writing a letter.
Inserting an item into a typical priority queue takes what big O time?
O(N)
The term priority in a priority queue means that:
a. the highest priority items are inserted first
b. the programmer must prioritize access to the underlying array
c. the underlying array is sorted by the priority of items
d. the lowest priority items are deleted first
c. the underlying array is sorted by the priority of the items
True or False: At least one of the methods in the priorityQ.java program (Listing 4.6) uses a linear search.
True
One difference between a priority queue and an ordered array is that:
a. the lowest-priority item cannot be extracted as easily from the array as it can from the priority queue.
b. the array must be ordered while the priority queue need not be.
c. the highest priority item can be extracted easily from the priority queue but not from the array
d. all of the above.
b. the array must be ordered while the priority queue need not be.
A priority queue might be used to hold:
a. passengers to be picked up by a taxi from different parts of the city
b. keystrokes made at a computer keyboard
c. squares on a chessboard in a game program.
d. planets in a solar system simulation.
a. passengers to be picked up by a taxi from different parts of the city.
A stack allows access to the ________ item inserted.
last
