edited by
16,120 views
41 votes
41 votes

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$
edited by

11 Answers

3 votes
3 votes

Here is traced out recursive tree.

Answer: Option B

0 votes
0 votes
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.
0 votes
0 votes
Storing an element in a recursive function before you recurse is equivalent to storing in a stack, so you are taking elements from a queue and putting them in the stack. When the queue is empty you are inserting them back into the Queue.

This is how you reverse a queue with a stack.
0 votes
0 votes

This is a recursive program let Queue contians 1,2,3,4  and we can make recursion tree as

Now Traverse this recursion tree 

insert(4) 

  4

insert(3)

   4   3

insert(2)

   4      3   2

insert(1)

    4     3    2    1

So queue got reversed

Answer(b)

Answer:

Related questions

62 votes
62 votes
11 answers
2
Ishrat Jahan asked Oct 29, 2014
28,963 views
Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collide...