GATE IT 2007 | Question: 30

Question

Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:

1. $\text{isEmpty (Q)}$ — returns true if the queue is empty, false otherwise.
2. $\text{delete (Q)}$ — deletes the element at the front of the queue and returns its value.
3. $\text{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$

Comments

@Anand Mundhe

According to me,

implementing using arrays : call by reference is default.

implementing using linked list : you are sending a pointer of the queue, which is also call by reference.

So I think we don’t have to worry about call by value here

---

This exact concept is repeated in GATE 2022 question where elements of Queue are reversed in place.(Using No additional storage)

https://gateoverflow.in/371884/gate-cse-2022-question-52

---

 

\[ \begin{array}{l} \textcolor{blue}{\text{Procedure}}~ f(Q): \\ \quad \vert\ \textcolor{blue}{\text{if}}~ Q ~\text{is not empty then} \\ \quad \vert\quad \vert\ i \leftarrow \text{delete}(Q) \\ \quad \vert\quad \vert\ f(Q) \\ \quad \vert\quad \vert\ \text{insert } i \text{into } Q \\ \quad \vert\ \textcolor{blue}{\text{end if}} \\ \textcolor{blue}{\text{end procedure}} \end{array} \]

\[ \begin{array}{rl} Q &= [1, 2, 3] \\ (\text{front} &= 1,~ \text{rear} = 3) \end{array} \]

 

\[ \begin{array}{rl} \textbf{Call: } & f(Q) \\[4pt] \text{First call:} & i = \text{delete}(Q) \Rightarrow Q = [2, 3] \\ & f(Q) \\ & \boxed{i = 1} \\[4pt] \text{Second call:} & i = \text{delete}(Q) \Rightarrow Q = [3] \\ & f(Q) \\ & \boxed{i = 2} \\[4pt] \text{Third call:} & i = \text{delete}(Q) \Rightarrow Q = [] \\ & f(Q) \\ & \boxed{i = 3} \\[4pt] \text{Fourth call:} & Q \text{ is empty } \Rightarrow \text{returns} \end{array} \]

\[ \begin{array}{l} \textbf{Now recursion starts returning:} \\[4pt] \text{From third call: } \text{insert}(Q, 3) \Rightarrow Q = [3] \\[4pt] \text{From second call: } \text{insert}(Q, 2) \Rightarrow Q = [3, 2] \\[4pt] \text{From first call: } \text{insert}(Q, 1) \Rightarrow Q = [3, 2, 1] \\[8pt] \textcolor{green}{\text{Final Queue:}}~ Q = [3, 2, 1] \end{array} \]

Answer 1

 

$insert()$ will inserts the values in reverse order.

Correct Answer: $B-$ Reverses the order of the elements in the queue $Q.$

Comments

any reference ? I donot think call by reference or call by value will make any problem here.

---

The above answer will be alright if we consider it to be global so that all invocations will be able to make changes to the same Queue. Have you considered it to be global???

---

Arrays  in C are passes as reference so it shouldn't be a problem. Ofcourse I'm making an assumption that Queue is implemented using array.

Answer 2

Here is traced out recursive tree.

Answer: Option B

Answer 3

answer will be b.

explanation...

assume a queue of element 1 2 3 4 5...

now as Q is not empty it will delete 1 and 1 will be sored in i and den again f(Q) will be called which contains element 23456...but the trace (activation of inset (Q,1)) remains.it continues till 5 is deleted and again activation is executed by inserting q(5)...to q(1),,,thus reversing the queue

Comments

is ny other better approach to understand it ?

---

why it is saved... it is not declared as static and default everything is in activation record please explain this point .

---

Call by value.....

---

But it is clearly mentioned that
insert(Q,i) — inserts the integer i at the rear of the queue.
Hence we have to insert the elements at rear , like 5 will be inserted at rear , then 4 , then 3 , then 2 then 1
Hence correct option should be option A .

But it is also a fact that , in the question , it is no where mentioned that how rear will be decreamented after each function ends .

Answer 4

Answer should be B because Deletion operation is performed until all elements are deleted and any insert function not invoked until all deletion operation completed when it is completed function returns and insert operation is called then element pushed into the queue in this way we get reverse of the elements of the queue Q 

option B is correct

Comments

Only happens if call by reference..... can u see & anywhere?

Answer 5

ans b)

Comments

Wrong

Answer 6

In this recursion, queue is being deleted by one element every time and getting saved in i. And again the function calls itself. When queue becomes empty, the last element will be inserted first in the queue. This will be for all the elements present. Thus, it reverses the order of elements in the queue.