Question 1 |

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.

Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?

Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?

\Theta (1), \Theta (1) | |

\Theta (1), \Theta (n) | |

\Theta (n), \Theta (1) | |

\Theta (n), \Theta (n) |

Question 1 Explanation:

Question 2 |

Which of the following data structure is useful in traversing a given graph by breadth first search?

Stack | |

Queue | |

List | |

None of the above |

Question 2 Explanation:

Question 3 |

A circular queue has been implemented using a single linked list where each node consists of
a value and a single pointer pointing to the next node. We maintain exactly two external
pointers FRONT and REAR pointing to the front node and the rear node of the queue,
respectively. Which of the following statements is/are CORRECT for such a circular queue,
so that insertion and deletion operation can be performed in O (1) time ?

I. Next pointer of front node points to the rear node.

II. Next pointer of rear node points to the front node.

I. Next pointer of front node points to the rear node.

II. Next pointer of rear node points to the front node.

I only | |

II only | |

Both I and II | |

Neither I nor II |

Question 3 Explanation:

Question 4 |

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.

The maximum possible number of iterations of the while loop in the algorithm is_________.

The maximum possible number of iterations of the while loop in the algorithm is_________.

16 | |

64 | |

256 | |

1027 |

Question 4 Explanation:

Question 5 |

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)?

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 operation will be \Omega(n) | |

The worst case time complexity for both operations will be \Omega(n) | |

Worst case time complexity for both operations will be \Omega(logn) |

Question 5 Explanation:

Question 6 |

The queue data structure is to be realized by using stack. The number of stacks needed would be

It cannot be implemented | |

2 stacks | |

4 stacks | |

1 stack |

Question 6 Explanation:

Question 7 |

Consider a standard Circular Queue 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[10].

The front and rear pointers are initialized to point at q[2]. In which position will the ninth element be added?

The front and rear pointers are initialized to point at q[2]. In which position will the ninth element be added?

q[0] | |

q[1] | |

q[9] | |

q[10] |

Question 7 Explanation:

Question 8 |

Consider the following operation along with Enqueue and Dequeue operations on queues, where
k is a global parameter.

```
MultiDequeue(Q){
m = k
while (Q is not empty) and (m > 0) {
Dequeue(Q)
m = m - 1
}
}
```

What is the worst case time complexity of a sequence of n queue operations on an initially empty
queue?\Theta (n) | |

\Theta (n+k) | |

\Theta (nk) | |

\Theta (n^{2}) |

Question 8 Explanation:

Question 9 |

Suppose a circular queue of capacity (n-1) elements is implemented with an array of n elements.
Assume that the insertion and deletion operations 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

full: (REAR+1) mod n == FRONT empty: REAR == FRONT | |

full: (REAR+1) mod n == FRONT empty: (FRONT+1) mod n == REAR | |

full: REAR == FRONT empty: (REAR+1) mod n == FRONT | |

full: (FRONT+1) mod n == REAR empty: REAR == FRONT |

Question 9 Explanation:

Question 10 |

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

What operation is performed by the above function f ?

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 ?

Leaves the queue Q unchanged | |

Reverses the order of the elements in the queue Q | |

Deletes the element at the front of the queue Q and inserts it at the rear keeping the other elements in the same order | |

Empties the queue Q |

Question 10 Explanation:

There are 10 questions to complete.

Ques – 7; option A will be correct, not D. Kindly check.

Thank You chayan kumar sengupta,

We have updated the option.

Question number 7 of queue is the correct option is option A ,q[0] . Please do change