Time Left - 15:00 mins

GATE 2019 - P&DS Quiz-5 (Queue )

Attempt now to get your rank among 638 students!

Question 1

Consider the following function.
Void gradeup(int n)
{
enqueue(Q,0);
enqueue(Q,1);
for (i=0;i<n;i++)
{
x = dequeue(Q);
y = dequeue(Q);
enqueue(Q,y);
enqueue(Q,x+y);
print(x);
}
}
What is the functionality of above function gradeup?

Question 2

we have a stack of integer s and a queue of integer q. Draw a picture of satck queue after the following operations:
pushstack (s, 3)
pushstack (s, 12)
enqueue (q, 5)
enqueue (q, 8)
popstack (s, x)
pushstack (s, 2)
enqueue (q, x)
dequeue (q, y)
pushstack (s, x)
pushstack (s, y)

Question 3

Consider the following code
void funto(Queue *Q1)
{
Stack S1;
While (! isEmpty (Q1) )
{
Push(&S, deQueue (Q1) );
}
While (! isEmpty(&S) )
{
enQueue (Q, POP (&s));
}
}

Question 4

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:
10, 8, 5, 3, 2
Two new elements ‘1’ and ‘7’ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is

Question 5

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.

What is the worst case time complexity of a sequence of n queue operations on an initially empty queue?

Question 6

An implementation of a queue Q, using two stacks S1 and S2, is given below:
void insert (Q, x) {
push (S1, x);
}
void delete (Q) {
if (stack-empty(S2)) then
if (stack-empty(S1)) then {
print(“Q is empty”);
return;
}
else while (!(stack-empty(S1))){
x=pop(S1);
push(S2,x);
}
x=pop(S2);
}
Let n insert and m(≤n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?

638 attempts
3 upvotes
10 comments

Tags :

GATE & PSU CS Programming and Data Structures

Apr 2GATE & PSU CS