CUET Computer Science MCQs Chapter 3 Queue

Question. Following is C like pseudo-code of a function that takes a Queue as an argument, and uses a stack S to do processing.
void fun(Queue *Q)
{
Stack S; // Say it creates an empty stack S
// Run while Q is not empty
while (!isEmpty(Q))
{
// deQueue an item from Q and push the dequeued item to S
push(&S, deQueue(Q));
}
// Run while Stack S is not empty
while (!isEmpty(&S))
{
// Pop an item from S and enqueue the popped item to Q
enQueue(Q, pop(&S));
}
}
What does the above function do in general?
a) Removes the last from Q
b) Keeps the Q same as it was before the call
c) Makes Q empty
d) Reverses the Q

Answer : D

Question. Which of the following is true about linked list implementation of queue?
a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.
b) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.
c) Both of the above
d) None of the above

Answer : C

Question. Which of the following is NOT a common operation in a queue data structure?
a) Enqueue
b) Dequeue
c) Peek
d) Shuffle

Answer : D

Question. Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:
i. isEmpty (Q) — returns true if the queue is empty, false otherwise.
ii. delete (Q) — deletes the element at the front of the queue and returns its value.
iii. insert (Q, i) — inserts the integer i at the rear of the queue.
Consider the following function:
void f (queue Q) {
int i ;
if (!isEmpty(Q)) {
i = delete(Q);
f(Q);
insert(Q, i);
}
}
What operation is performed by the above function f ?
a) Leaves the queue Q unchanged
b) Reverses the order of the elements in the queue Q
c) Deletes the element at the front of the queue Q and inserts it at the rear keeping the other elements in the same order
d) Empties the queue Q

Answer : B

Question. Which one of the following is an application of Queue Data Structure?
a) When a resource is shared among multiple consumers.
b) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes
c) Load Balancing
d) All of the above

Answer : D

Question. The minimum number of stacks needed to implement a queue is
a) 3
b) 1
c) 2
d) 4

Answer : C

Question. Consider the below program, and identify what the function is doing.
void function(Node* root)
{
if (root == NULL)
return;
queue<Node*> q;
q.push(root);
while (q.empty() == false) {
Node* node = q.front();
cout << node->data << " ";
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
}
}
a) In order traversal of a tree
b) Normal traversal of a tree
c) Level order traversal of a tree
d) None

Answer : C

Question. Given a queue with a linked list implementation. the Rear pointer points to the rear node of the queue. and the front node of the queue points to the front node of the queue, Which of the following operations is impossible to do in O(1) time?
a) Delete the front item from the list.
b) Delete the rear from the list.
c) insert at the front of the list.
d) None

Answer : B

Question. 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.
a) 1
b) 2
c) 3
d) 4

Answer : B

Question. 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:
a) 10, 8, 7, 5, 3, 2, 1
b) 10, 8, 7, 2, 3, 1, 5
c) 10, 8, 7, 1, 2, 3, 5
d) 10, 8, 7, 3, 2, 1, 5

Answer : D

Question. Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?
a) A queue cannot be implemented using this stack.
b) A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.
c) A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.
d) A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

Answer : C

Question. Consider a standard Circular Queue \'q\' implementation (which has the same condition for Queue Full and Queue Empty) whose size is 11 and the elements of the queue are q[0], q[1], q[2].....,q[10]. The front and rear pointers are initialized to point at q[2] . In which position will the ninth element be added?
a) q[0]
b) q[1]
c) q[9]
d) q[10]

Answer : A

Question. 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?
a) (ii) is true
b) (i) and (ii) are true
c) (iii) is true
d) (ii) and (iv) are true

Answer : C

Question. Which of the following is/are advantages of circular Queue?
a) Memory Management
b) Traffic system
c) CPU Scheduling
d) All of the above

Answer : D

Question. What is wrong in the below code of printing Right View of a binary tree using the Queue data structure?
void printRightView(Node* root)
{
if (root == NULL)
return;
queue<Node*> q;
while (!q.empty()) {
int n = q.size();
while (n--) {
Node* x = q.front();
q.pop();
if (n == 0) {
cout << x->data << " ";
}
if (x->left)
q.push(x->left);

if (x->right)
q.push(x->right);
}
}
}
a) We have not initialized anything in the Queue
b) Queue will never be empty.
c) left and right nodes of the tree are null.
d) None

Answer : A

Question. Which of the following operations on a queue data structure has a time complexity of O(1)?
A) Enqueue
B) Dequeue
C) Peek
D) Clear
a) A and B
b) B only
c) C only
d) A and D

Answer : B

Question. An implementation of a queue Q, using two stacks S1 and S2, is given below:
void insert(Q, x) {
push (S1, x);
}
void delete(Q){
if(stack-empty(S2)) then
if(stack-empty(S1)) then {
print(“Q is empty”);
return;
}
else while (!(stack-empty(S1))){
x=pop(S1);
push(S2,x);
}
x=pop(S2);
}
Let n insert and m (<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?
a) n+m <= x < 2n and 2m <= y <= n+m
b) n+m <= x < 2n and 2m<= y <= 2n
c) 2m <= x < 2n and 2m <= y <= n+m
d) 2m <= x <2n and 2m <= y <= 2n

Answer : A

Question. A queue is implemented using an 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)?
a) Both operations can be performed in O(1) time
b) At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
c) The worst case time complexity for both operations will be Ω(n)
d) Worst case time complexity for both operations will be Ω(log n)

Answer : A

Question. A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let \'enqueue\' be implemented by inserting a new node at the head, and \'dequeue\' be implemented by deletion of a node from the tail.
head->1->2->3->tail.
Which one of the following is the time complexity of the most time-efficient implementation of \'enqueue\' and \'dequeue, respectively, for this data structure?
a) Θ(1), Θ(1)
b) Θ(1), Θ(n)
c) Θ(n), Θ(1)
d) Θ(n), Θ(n)

Answer : B

Question. The deque which stores elements in strictly increasing order or in strictly decreasing order is called ------.
a) Priority Queue
b) Double ended Queue
c) Monotonic Deque
d) None

Answer : C

Question. Which of the following is the type of priority Queue?
a) Ascending Order Priority Queue
b) Descending order Priority Queue
c) Deque
d) Both A and B.

Answer : D

Question. 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.
a) Array
b) Linked List
c) Heap Data Structures like Binary Heap, Fibonacci Heap
d) None of the above

Answer : C

Question. Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below. \"gtcs7\" The maximum possible number of iterations of the while loop in the algorithm is______ [This Question was originally a Fill-in-the-Blanks question]
a) 16
b) 32
c) 256
d) 64

Answer : C

Question. Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are
a) Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT
b) Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR
c) Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT
d) Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT

Answer : A

Question. which data structure is used to implement deque?
a) Stack
b) Doubly linked list
c) circular array
d) Both B and C

Answer : D

Question. Consider the following pseudo code. Assume that IntQueue is an integer queue. What does the function fun do?
void fun(int n)
{
IntQueue q = new IntQueue();
q.enqueue(0);
q.enqueue(1);
for (int i = 0; i < n; i++)
{
int a = q.dequeue();
int b = q.dequeue();
q.enqueue(b);
q.enqueue(a + b);
print(a);
}
}
a) Prints numbers from 0 to n-1
b) Prints numbers from n-1 to 0
c) Prints first n Fibonacci numbers
d) Prints first n Fibonacci numbers in reverse order.

Answer : C

Question. Circular queue is also called -----.
a) Ring Buffer
b) Rectangular Buffer
c) Square Buffer
d) None

Answer : A

Question. Which of the following option is not correct?
a) If the queue is implemented with a linked list, keeping track of a front pointer, Only rear pointer s will change during an insertion into an non-empty queue.
b) Queue data structure can be used to implement least recently used (LRU) page fault algorithm and Quick short algorithm.
c) Queue data structure can be used to implement Quick short algorithm but not least recently used (LRU) page fault algorithm.
d) Both (A) and (C)

Answer : C

Question. Which data structure is commonly used to implement the event-driven simulation of complex systems, such as in computer network simulations or traffic simulations?
a) Stack
b) Tree
c) Array
d) Queue

Answer : D