Multiple Choice Multiple Choice Sections 7.1-7.2 Queues and Their Applications O
ID: 3537395 • Letter: M
Question
Multiple Choice
Multiple ChoiceSections 7.1-7.2
Queues and Their
Applications One difference between a queue and a stack is: A. Queues require linked lists, but stacks do not. B. Stacks require linked lists, but queues do not. C. Queues use two ends of the structure; stacks use only one. D. Stacks use two ends of the structure, queues use only one. 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. Math.random() < P B. Math.random() > P C. Math.random() < P * 100 D. Math.random() > P * 100 Multiple Choice Section 7.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 current capacity is 42. Where does the insert method 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 getFront method would require linear time. C. The insert method would require linear time. D. The isEmpty method would require linear time. In the linked list implementation of the queue class, where does the insert method 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, which operations require linear time for their worst-case behavior? A. getFront B. insert when the capacity has not yet been reached C. isEmpty 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. getFront B. insert C. isEmpty D. None of these operations require linear time. If data is a circular array of CAPACITY elements, and rear is an index into that array, what is the formula for the index after rear? A. (rear % 1) + CAPACITY B. rear % (1 + CAPACITY) C. (rear + 1) % CAPACITY D. rear + (1 % CAPACITY) I have implemented the queue with a circular array, keeping track of front, rear, and manyItems (the number of items in the array). Suppose front is zero, and rear is one less than the current capacity. What can you tell me about manyItems? A. manyItems must be zero. B. manyItems must be equal to the current capacity. C. count could be zero or the 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 node and a rear node with two reference variables. Which of these reference variables will change during an insertion into a NONEMPTY queue? A. Neither changes B. Only front changes. C. Only rear changes. D. Both change. I have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into an EMPTY queue? A. Neither changes B. Only front changes. C. Only rear changes. D. Both change. Multiple Choice Section 7.4 Priority Queues Suppose getFront is called on a priority queue that has exactly two entries with equal priority. How is the return value of getFront selected? A. One is chosen at random. B. The one which was inserted first. C. The one which was inserted most recently. D. This can never happen (violates the precondition) An array of queues can be used to implement a priority queue, with each possible priority corresponding to its own element in the array. When is this implementation not feasible? A. When the number of possible priorities is huge. B. When the number of possible priorities is small. C. When the queues are implemented using a linked list. D. When the queues are implemented with circular arrays. Multiple Choice
Sections 7.1-7.2
Queues and Their
Applications
Explanation / Answer
Answers:
1.
Thus, option (C) is correct. Queue uses two ends of the structure and stack uses only one.
2.
Thus, option (D) is correct.
3.
Thus, option (A) is correct. Math.random() < P.
4.
Thus, option(D) is correct.
5.
Thus, option (B) is correct.
6.
Thus, option (B) is correct.
7.
Thus, option (D) is correct.
8.
Thus, option (D) is correct.
9.
(Rear + 1) % Capacity.
Thus, option (C) is correct.
10.
Thus, option (C) is correct.
11.
Thus, option (C) is correct.
12.
Thus, option (D) is correct.
13.
Thus, option (D) is correct.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.