QUEUES

Multiple Choice

1. One difference between a queue and a stack is:
1.  Queues require dynamic memory, but stacks do not.
2.  Stacks require dynamic memory, but queues do not.
3.  Queues use two ends of the structure; stacks use only one.
4.  Stacks use two ends of the structure, queues use only one.

Ans : c, Because queues are double in ending while stacks do not, they have only one end.

2. 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?
1.  ABCD
2.  ABDC
3.  DCAB
4.  DCBA

Ans : d, Queue works on the idea of first in last out, so the order is reversed.

3. 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?
1.  data[1]
2.  data[2]
3.  data[11]
4.  data[12]

Ans. : d since it is in an array implementation, data will be stored in the next free index, i.e. 12^th.

4. 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).
1.  The constructor would require linear time.
2.  The get_front function would require linear time.
3.  The insert function would require linear time.
4.  The is_empty function would require linear time.

Ans. :c,  The insert function will require linear time, because the deletion has always to happen from the front and to maintain the front on data[0].

5. In the circular array version of the queue (with a fixed-sized array), which operations require linear time for their worst-case behavior?
1.  front
2.  push
3.  empty
4.  None of these operations require linear time.

Ans. : b, Since it is a circular queue, it will first check whether the queue is actually empty, which might not be the case always.

6. 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?
1.  (last % 1) + CAPACITY
2.  last % (1 + CAPACITY)
3.  (last + 1) % CAPACITY
4.  last + (1 % CAPACITY)

Ans. : c, This expression will point to the field after last that will be the first field.

7. 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?
1.  count must be zero.
2.  count must be CAPACITY.
3.  count could be zero or CAPACITY, but no other values could occur.
4.  None of the above.

Ans. : b, count is nothing but indicates CAPACITY, i.e. it has CAPACITY nos. of elements.

8. 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?
1.  Neither changes
2.  Only front_ptr changes.
3.  Only rear_ptr changes.
4.  Both change.

Ans. : c, since in a queue the entry is made from only the rear end, on insertion of an element the rear pointer will move forward.

9. 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?
1.  Neither changes
2.  Only front_ptr changes.
3.  Only rear_ptr changes.
4.  Both change.

Ans. : d, Since it is an empty queue the front and rear are initialized to -1, so on insertion both the pointers will change and will point to 0.

10. Suppose top is called on a priority queue that has exactly two entries with equal priority. How is the return value of top selected?
1.  The implementation gets to choose either one.
2.  The one which was inserted first.
3.  The one which was inserted most recently.
4.  This can never happen (violates the precondition)

Ans. :  d, A priority queue is created keeping the fact in mind that two elements should not have the same priority.

11.  Which of the following is/are not (a) valid queue application(s)?

(a) When printing jobs are submitted to printer

(b) Lines at tickets counters

(c) Evaluating a mathematical expression

(d) Calls to large companies, when all lines are busy

(e) When there are many network set-ups of personal computers in which the disk is allocated to one machine, known as the file server and users on the other machine are given access to the file.

Ans) C

12.   A queue in which we can insert or delete elements from both ends is called

1. Circular Queue
2. Deque
3. Double
4. single

Ans)B

13.   In which queue we can utilize location of deleted element again is called

1. Circular Queue
2. Tree
3. Stack
4. None

Ans)A

14.   The time complexity of adding an element to a queue of n elements is?

1. O(1)
2. O(n)
3. O(n+1)
4. None

Ans)A

15.    The time complexity of Deleting an element from a queue of n elements is?

1. O(1)
2. O(n)
3. O(n*n)
4. None

Ans)B

16.   A Queue can be implemented by using the following ?
1) Tree
2) Array
3) Single Linked list

1. 1 and 2
2. 2 and 3
3. 1 and 3
4. All

Ans)C

17.   Pick the appropriate match for the  Queue form the following options

1. Can be created by setting up an ordinary contiguous array to hold the items
2. Can take care of delete operation automatically
3. Need a pointer to handle addition  and deletion of an item
4. None.

Ans)C

18.    A Circular queue is empty if?

1. front=rear-1
2. rear=front-1
3. front=rear+1
4. rear=front

Ans)D

19.  A queue is empty if?

1. front=rear-1
2. rear=front-1
3. front=rear
4. front=rear=0

Ans)A

20.   In which of the following types a priority queue can be constructed
1)Ascending priority queue
2)Descending priority queue
3)Top-Down priority queue

1. 2 and 3
2. 1 and 2
3. 1 and 3
4. All

Ans)B

21.          Suppose u opened a notepad, a music player, an excel sheet, and also u are doing your data structure programming simultaneously. Your Windows-XP implements ______ data structure for it

1. tree
2. stack
3. linked list
4. QUEUE

Ans)D

22)What happens when wraparound is implemented for a queue?

(a) If Front advances past the last array position, it is reset to the first array position.

(b) If Rear advances past the last array position, it is reset to the first array position.

(c) Both (a) and (b)

(d) Neither (a) nor (b)

Ans) C

23)Consider the following queue with the indicated initial states and series of queue operations

If the above series of operations is performed, what is the final status of the queue?

Ans) D