The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
1.1k 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 (21.8k points) | 1.1k views
What's problem with c option ?

5 Answers

+15 votes
Best answer

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

answered by Veteran (71.7k points)
selected 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???
+5 votes
ans b)
answered by Boss (5.2k points)
+5 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 (16k 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 .
+1 vote

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 Boss (7.5k points)
0 votes
Answer: B
answered by Veteran (35.6k 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

29,961 questions
37,632 answers
96,402 comments
35,286 users