The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
1.4k views

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

  1. Leaves the queue $Q$ unchanged
  2. Reverses the order of the elements in the queue $Q$
  3. Deletes the element at the front of the queue $Q$ and inserts it at the rear keeping the other elements in the same order
  4. Empties the queue $Q$
asked in DS by Veteran (22k points)
edited by | 1.4k views
What's problem with c option ?
Recursive. Hmm good... so you think c do call by reference? I'm surprised ....
Its call by value... so fuction will not reverse.....
First call will take element at last and put to first and sends deleted copy to next recursion

Suppose queue contain. 1,2,3
execution start
Now first check if empty
Q=1,2,3
Not empty so in
i=1
Q=2,3
Call it self Q=2,3
Check if empty
Not empty in
i=2
Q=3
Call it self Q=3
Check if empty
Not empty in
i=3
Q=empty
Call itself Q=empty
Check if Q empty
Is empty return
Enqueue(i)
Q=3
Return
enqueue(i)
Q=3,2
Return
enqueue(i)
Q=2,3,1
Return
Exit

So now you see only first element go to last .... so please fix it... if someone write wrong answer in gate.. they will be mad at you guys..... so ... let me know if something wrong here

So correct answer should be(must be) c..
C. Delets element at front of queue and insert it to tail keeping other elements sequence as it is

And sorry for bad language... I'm not good in english but I can code...
The question never said C language. We should follow the terminology in question and not think about any implementation.

Well then tell me, dear if this is not a program,

Quote/Moto from my Idle:

So when a question of programming is given, one should compile it in the brain and execute it, line by line to get an accurate answer.

If you do not think of implementation, then you are doing it wrong.

Most of the times your answer will be wrong in exams.

so about the language, it is not a c language then c++, but c++ require & to show references...

if java(Same goes for C#) then according to recommendation class name should start with a capital, So we cannot say 'queue' is a user defined class. if it is a class then - bro how can it be in gate exam... are the gate examiners don't have programming knowledge..

This one is a tricky question, so a perfect programmer will put 'B', and marks get reduced. But the programmers who still work after perfection will see the answer as 'C'...

 

I'm not an expert in it or something... it just I confirmed it from many programmers. And all of them say 'C'.

Forget to mention

question is: "Suppose you are given an [<implementation>] of a queue of integers"

how can you say: "and not think about any implementation."
Good to know that you're a perfect programmer :)

And no where in the question it asks to tie the implementation to any particular language. Be confident; but not be overconfident.
@Anand Mundhe

why are you behaving like a nerd ?

5 Answers

+22 votes
Best answer

$insert()$ will inserts the value in just reverse order.

answered by Veteran (81.1k points)
edited by
@ shreshta I have a doubt i.e as Q is not a global structure or static so how various invocation can work on the same queue q. As every invocation will work on their local copies so how an inner invocation can change the value of the queue of the calling function(or outer function).So I think the answer must be c because only the outermost function will have an impact on the original queue.
Can we not do push, push , pop in one stack? then in case of poping only one element is popped. Then why same will not happen in queue?
Because every function invocation will be doing changes to their own local copies which are provided by their parent function and not on the same queue because it is not called by reference but call by value. That's why only the changes made by the outermost invocation i.e the parent or root will be done on the original queue.
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???
+8 votes
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
answered by Veteran (17.7k points)
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.....
+4 votes

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

answered by Veteran (11.2k points)
Only happens if call by reference..... can u see & anywhere?
+2 votes
ans b)
answered by Boss (5.1k points)
Wrong
–2 votes
Answer: B
answered by Veteran (36.4k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,620 questions
40,170 answers
114,128 comments
38,554 users