Data Structure (QUEUE)

Which one of the following is an application of Queue Data Structure?

• When a resource is shared among multiple consumers.

• When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes

• Load Balancing

• All of the above

How many stacks are needed to implement a queue. Consider the situation where no other data structure like arrays, linked list is available to you.

• 1

• 2

• 3

• 4

How many queues are needed to implement a stack. Consider the situation where no other data structure like arrays, linked list is available to you.

• 1

• 2

• 3

• 4

A priority queue can efficiently implemented using which of the following data structures? Assume that the number of insert and peek (operation to see the current highest priority item) and extraction (remove the highest priority item) operations are almost same.

• Array

• Linked List

• Heap Data Structure like Binary Heap, Fibonacci Heap

• None of the above

Which of the following is true about linked list implementation of queue?

• In the push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.

• In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.

• None of the above

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below :

10, 8, 5, 3, 2

Two new elements “1” and “7” are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is :

• 10, 8, 7, 5, 3, 2, 1

• 10, 8, 7, 2, 3, 1, 5

• 10, 8, 7, 1, 2, 3, 5

• 10, 8, 7, 3, 2, 1, 5

A queue is implemented using array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue) ?

• Both operations can be performed in O(1) time

• At most one operation can be performed in O(1) time but the worst case time for the other operations will be Ω(n)

• The worst case time complexity for both operations will be Ω(n)

• Worst case time complexity for both operations will be Ω(log n)

Suppose implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which of the following statement is true with respect to this modified stack?

• A queue cannot be implemented using this stack.

• A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.

• A queue can be implemented where ENQUEUE takes a sequence of three instruction and DEQUEUE takes a single instruction.

• A queue can be implemented where both ENQUEUE and DEQUEUE takes a single instruction each

A priority queue is implemented as a max-heap. Initially, it has five elements. The level-order traversal of the heap is as follows:

20, 18, 15, 13, 12

Two new elements ‘10’ and ‘17’ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the element is:

• 20, 18, 17, 15, 13, 12, 10

• 20, 18, 17, 12, 13, 10, 15

• 20, 18, 17, 10, 12, 13, 15

• 20, 18, 17, 13, 12, 10, 15

Consider the following statements:

i. First-in-first out types of computations are efficiently supported by STACKS.

ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on

an array for almost all the basic LIST operations.

iii. Implementing QUEUES on a circular array is more efficient than implementing QUEUES

on a linear array with two indices.

iv. Last-in-first-out type of computations are efficiently supported by QUEUES.

Which of the following is correct?

• II and III

• I and II

• III and IV

• II and IV