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

I think the program will never come to execute insert(Q, i) operation because the program recurse before it and as it become empty the isEmpty() becomes true and if section becomes false and it should not enter that setion and terminates.

Kindly tell me where I am wrong.

---

i also have the same doubt, initially it goes on deleting the elements from the queue and then the loop condition becomes false. So how are we executing the insert(q,i) statement...

---

@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

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

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 3

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 4

ans b)

Comments

Wrong