DS QUIZ 4 CSE D

1. If the MAX_SIZE is the size of the array used in the implementation of circular queue. How is rear manipulated while inserting an element in the queue?

Rear=(Rear%1)+MAX_SIZE

Rear=Rear%(MAX_SIZE+1)

Rear=(Rear+1)%MAX_SIZE

Rear=Rear+(1%MAX_SIZE)

The correct answer is Rear=(Rear+1)%MAX_SIZE. This is because when inserting an element in a circular queue, the rear pointer needs to be incremented to point to the next available position in the queue. However, if the rear pointer reaches the end of the array (MAX_SIZE), it needs to wrap around to the beginning of the array. The expression (Rear+1)%MAX_SIZE achieves this by incrementing the rear pointer by 1 and then taking the modulus of MAX_SIZE to ensure it stays within the bounds of the array.

Explanation

The correct answer is Rear=(Rear+1)%MAX_SIZE. This is because when inserting an element in a circular queue, the rear pointer needs to be incremented to point to the next available position in the queue. However, if the rear pointer reaches the end of the array (MAX_SIZE), it needs to wrap around to the beginning of the array. The expression (Rear+1)%MAX_SIZE achieves this by incrementing the rear pointer by 1 and then taking the modulus of MAX_SIZE to ensure it stays within the bounds of the array.

2. Which of the following is a collection of items into which items can be inserted arbitrarily and from which only the smallest item can be removed?

FIFO queue

Deque

Decreasing order priority queue

Increasing order priority queue

An increasing order priority queue is a collection of items where items can be inserted arbitrarily, but only the smallest item can be removed. This means that when inserting items into the priority queue, they are arranged in increasing order based on their priority. The item with the highest priority (smallest value) will always be at the front of the queue and can be removed. Other items can only be removed once they reach the front of the queue and become the smallest item.

Explanation

An increasing order priority queue is a collection of items where items can be inserted arbitrarily, but only the smallest item can be removed. This means that when inserting items into the priority queue, they are arranged in increasing order based on their priority. The item with the highest priority (smallest value) will always be at the front of the queue and can be removed. Other items can only be removed once they reach the front of the queue and become the smallest item.

3. Suppose a circular queue of capacity 10 elements is implemented with an array of dimension 10. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, FRONT = 1 and REAR = 5

A

B

C

D

E

What will be position of FRONT and REAR, after performing the following operations on the queue?ADD F, DELETE TWO LETTERS, ADD G, ADD H, DELETE FOUR LETTERS, ADD I

FRONT = 8 and REAR = 0

FRONT = 8 and REAR = 1

FRONT = 7 and REAR = 0

FRONT = 7 and REAR = 9

After performing the given operations on the circular queue, the position of FRONT will be 7 and the position of REAR will be 9. This is because the initial positions of FRONT and REAR were 1 and 5 respectively. The operations ADD F and DELETE TWO LETTERS do not change the positions of FRONT and REAR. Then, ADD G and ADD H increment the REAR position by 1 each time. DELETE FOUR LETTERS decreases the REAR position by 4. Finally, ADD I increments the REAR position by 1. Thus, the final positions of FRONT and REAR are 7 and 9 respectively.

Explanation

After performing the given operations on the circular queue, the position of FRONT will be 7 and the position of REAR will be 9. This is because the initial positions of FRONT and REAR were 1 and 5 respectively. The operations ADD F and DELETE TWO LETTERS do not change the positions of FRONT and REAR. Then, ADD G and ADD H increment the REAR position by 1 each time. DELETE FOUR LETTERS decreases the REAR position by 4. Finally, ADD I increments the REAR position by 1. Thus, the final positions of FRONT and REAR are 7 and 9 respectively.

4. Consider a dequeue of capacity 10 elements is implemented with an array of dimension 10. The insertion and deletion operation can be carried out at either of LEFT and RIGHT end. Initially, LEFT = 1 and RIGHT = 5.

A

B

C

D

E

What will be status of LEFT and RIGHT, after performing the following operations on the queue?Add F on the left, Add G on the right, Add H on the right, Delete two letters from the left, Add I on the right, Add J on the left, Delete two letters from left.

LEFT = 1 and RIGHT = 5

LEFT = 2 and RIGHT = 6

LEFT = 0 and RIGHT = 6

None

not-available-via-ai

Explanation

not-available-via-ai

5. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into a NONEMPTY queue?

Only front pointer

Only rear pointer

Both front and rear pointer

None of the front and rear pointer

In a linked list implementation of a queue, the front pointer always points to the first element in the queue, while the rear pointer points to the last element. During an insertion into a nonempty queue, only the rear pointer will change because a new element is added to the end of the queue. The front pointer remains unchanged as it still points to the first element in the queue.

Explanation

In a linked list implementation of a queue, the front pointer always points to the first element in the queue, while the rear pointer points to the last element. During an insertion into a nonempty queue, only the rear pointer will change because a new element is added to the end of the queue. The front pointer remains unchanged as it still points to the first element in the queue.

6. The initial configuration of a queue is a, b, c, d, e ('a' is in the front end). To get the configuration e, d, c, b, a, one needs a minimum of :

3 deletion and 4 additions

4 deletion and 3 additions

4 deletion and 5 additions

None

not-available-via-ai

Explanation

not-available-via-ai

7. Suppose a circular queue of capacity n 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 = -1. The conditions to detect queue full and queue empty are:

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: FRONT= =REAR=-1

Full: (REAR+1) mod n = = FRONT, empty: REAR = = FRONT= -1

The correct answer is Full: (REAR+1) mod n = = FRONT, empty: REAR = = FRONT= -1. This answer correctly represents the conditions to detect a full and empty queue in a circular queue implemented with an array. The condition for a full queue is when the next position after REAR is equal to FRONT, and the condition for an empty queue is when both REAR and FRONT are equal to -1.

Explanation

The correct answer is Full: (REAR+1) mod n = = FRONT, empty: REAR = = FRONT= -1. This answer correctly represents the conditions to detect a full and empty queue in a circular queue implemented with an array. The condition for a full queue is when the next position after REAR is equal to FRONT, and the condition for an empty queue is when both REAR and FRONT are equal to -1.

8. Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:isEmpty(Q) – returns true if the queue is empty, false otherwise.delete(Q) – deletes the element at the front of the queue and returns its value.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

Reverse the order of elements in the queue Q

Empties the queue Q

The given function f recursively deletes the element at the front of the queue Q and inserts it at the rear, effectively reversing the order of elements in the queue. This is because the function first deletes the front element and stores it in variable i, then calls itself recursively on the remaining queue, and finally inserts the stored element i at the rear of the queue. This process is repeated until the queue becomes empty, resulting in the reversal of elements in the queue.

Explanation

The given function f recursively deletes the element at the front of the queue Q and inserts it at the rear, effectively reversing the order of elements in the queue. This is because the function first deletes the front element and stores it in variable i, then calls itself recursively on the remaining queue, and finally inserts the stored element i at the rear of the queue. This process is repeated until the queue becomes empty, resulting in the reversal of elements in the queue.

9. Which representation of priority queue is more time and more space efficient, respectively.

Ordinary Array for Each Priority and Linked List

Linked List and Ordinary Array for Each Priority

Circular Array for Each Priority and Linked List

Linked List and Circular Array for Each Priority

A circular array for each priority and linked list is more time efficient because it allows for constant time access to the highest priority element in the queue. The circular array ensures that the elements with the highest priority are always at the front of the queue, making it easy to retrieve them. On the other hand, using a linked list for each priority allows for efficient insertion and removal of elements, which makes it more space efficient. This is because the linked list only requires memory for the elements that are actually in the queue, whereas the circular array needs memory for the maximum possible number of elements.

Explanation

A circular array for each priority and linked list is more time efficient because it allows for constant time access to the highest priority element in the queue. The circular array ensures that the elements with the highest priority are always at the front of the queue, making it easy to retrieve them. On the other hand, using a linked list for each priority allows for efficient insertion and removal of elements, which makes it more space efficient. This is because the linked list only requires memory for the elements that are actually in the queue, whereas the circular array needs memory for the maximum possible number of elements.

10. If the MAX_SIZE is the size of the array used in the implementation of circular queue, array index start with 0, Front point to the first element in the queue, and Rear point to the last element in the queue. Which of the following condition specify that circular queue is FULL?

Front=Rear= -1

Front=(Rear+1)%MAX_SIZE

Rear=Front+1

Rear=(Front+1)%MAX_SIZE

not-available-via-ai

Explanation

not-available-via-ai

Ds Quiz 4 Cse D