QueuesandStacks
Question 1 
push(54); push(52); pop(); push(55); push(62); s=pop();
Consider the following sequence of operations on an empty queue.
enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue();
The value of s + q is ________
86 
push(54) ⇒ 54
push(52)=> 54, 52(top)
pop() ⇒ 54 (top)
push(55)==> 54, 55(top)
push(62) ⇒ 54,55,62(top)
s=pop() ⇒ 62 will store into the variable s then s=62
enqueue(21) ⇒ (front) 21(rear)
enqueue(24) ⇒ (Front)21, 24(rear)
dequeue()==> (front) 24(rear)
enqueue(28) ===> (front) 24,28 (rear)
enqueue(32)====>(front) 24,28,32 (rear)
q=dequeue() ⇒ value 24 will store into the variable “q”
q=24
S+q =62+24 =86
Question 2 
A queue Q containing n items and an empty stack S are given. It is required to transfer all the items from the queue to the stack, so that the item at the front of queue is on the top of the stack, and the order of all other items is preserved. Show how this can be done in O(n) time using only a constant amount of additional storage. Note that the only operations which can be performed on the queue and stack are Delete, Insert, Push and Pop. Do not assume any implementation of the queue or stack.
Theory Explanation. 
Question 3 
A stack is used to pass parameters to procedures in a procedure call.
(a) If a procedure P has two parameters as described in procedure definition:
procedure P (var x :integer; y: integer); and if P is called by ; P(a,b)
State precisely in a sentence what is pushed on stack for parameters a and b.
(b) In the generated code for the body of procedure P, how will the addressing of formal parameters x and y differ?
Theory Explanation. 
Question 4 
A function f defined on stacks of integers satisfies the following properties.
f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i.
If a stack S contains the integers 2, 3, 2, 1, 2 in order from bottom to top, what is f(S)?
6  
4  
3  
2 
f(Ø)=0 and f(push(S,i) = max(f(S),0) + i;
Initially stack is empty and for empty stack 0 is given.
f(push(0,2)) = max(f(Ø),0) + 2 = max(Ø,0) + 2 = 2
f(push(2,3)) = max(2,0) + (3) = 2  3 = 1
f(push(1,2)) = max(1,0) + 2 = 0 + 2 = 2
f(push(2,1)) = max(2,0)+ (1) = 2  1 = 1
f(push(1,2)) = max(1,0) + 2 = 1 + 2 = 3
So, 3 will be the answer.
∴ Option C is correct.
Question 5 
I: push the elements of a from a0 to a5 in that order into S.
II: enqueue the elements of a from a0 to a5 in that order into Q.
III: pop an element from S.
IV: dequeue an element from Q.
V: pop an element from S.
VI: dequeue an element from Q.
VII: dequeue an element from Q and push the same element into S.
VIII: Repeat operation
VII three times. IX: pop an element from S. X: pop an element from S.
The top element of S after executing the above operations is _____?
8 
I: push the elements from a0 to a5 in that order into S.
II: enqueue the elements of a from a0 to a5 in that order into Q.
III: pop an element from S.
IV: dequeue an element from Q.
V: pop an element from S.
VI: dequeue an element from Q.
VII: dequeue an element from Q and push the same element into S.
Element “7” is deleted and inserted into stack “S”
VIII: Repeat operation VII three times.
After performing the VIII operation , the elements of stack are as shown below
IX: pop an element from S.
X: pop an element from S
The top element of S after executing the above operations is 8.
Question 6 
Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below.
The maximum possible number of iterations of the while loop in the algorithm is _________.
256  
257  
258  
259 
Try to solve it for 3 numbers [1. 2, 3].
Step 1: Initially Queue contains 3 elements so after 5 while loop iterations queue contains 3, 2 and stack contains 1.
Step 2: Now after 3 more while loop iterations, Queue contains 3 and stack contains 1, 2 (TOS = 2).
Step 3: After 1 more while loop iteration, push 3 onto the stack so queue is empty and stack contains 1, 2, 3 {top = 3}.
So, total number of iterations will be 5 + 3 + 1 = 9
i.e., for 3 it is 9 iterations (3*3)
for 4 it is 16 iterations (4*4)
Given: 16 numbers, so 16 * 16 = 256
Question 7 
Leftist Heap  
Binary Heap  
AVL trees  
Red – Black trees 
Question 8 
Double Ended Queue  
Queue  
Priority Queue  
Stack 
Stack: Stack is an abstract data type that serves as a collection of elements, with two principal operations:
>push, which adds an element to the collection, and
>pop, which removes the most recently added element that was not yet removed.
Both PUSH and POP operations are done from a single end.The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out).
Queue: a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and removal from the other end of the sequence. It allows addition and deletion of items from fixed different ends.
Question 9 
PUSH ( 10 ). PUSH ( 20 ). POP. PUSH ( 10 ). PUSH ( 20 ). POP. POP. POP. PUSH ( 20 ). POPThe sequence of values popped out is
20, 10, 20, 10, 20  
20, 20, 10, 10, 20  
10, 20, 20, 10, 20  
20, 20, 10, 20, 10 
⇒ Push(20)
⇒ Pop 20
⇒ Push(10)
⇒ Push(20)
⇒ Pop 20
⇒ Pop 10
⇒ Pop 10
⇒ Push(20)
⇒ Pop 20
Question 10 
Queue  
Stack  
File  
All the above 
Question 11 
Stack  
Binary Tree  
Queue  
All of the above 
Question 12 
a+b*c  
(a+b)*c  
a* (b+c)
 
None of the above 
Now by traversing the tree we get the infix expression as, (a+b)*c
Question 13 
operations are defined by the following code.
push(x)
A[pos] x
pos pos+1
end push
pop()
pospos+1
Return A[pos]
end pop
Which of the following will initialize an empty stack with capacity N for the above implementation?
pos ← 1  
pos ← 0  
pos ← 1  
pos ←N1 
Now if you imagine an array of length N1, for every push the empty indices are getting decremented.
To explain in detail,
consider an empty array, so number of empty indices are N1 ......(1)
When we push one element into it, the empty indices will reduce by 1 (i.e. decreented.)
Hence, From equation 1 we can say that pos is initialised to N1
Question 14 
delete a, b; and insert e,a,f;  
insert e,a,f and delete a,b  
insert e, delete b and insert f
 
insert e,f, move a to place it between e and f, then delete b

Question 15 
θ(1) , θ(n)  
θ(n) , θ(1)  
θ(1) , θ(1)  
θ(n) , θ(n) 
ExtractMin will take θ(n) time for above conditions. The array is unsorted there is naturally no better algorithm than just linear search. Worst case performance for linear search is Θ(n)
Question 16 
If (rear == maxsize  1) rear=0; else rear = rear + 1; is required in
circular queue
 
linear queue  
stack  
deque

Question 17 
The data structure required for breadth first traversal on a graph is
queue
 
stack
 
array  
tree

The data structure required for depth first traversal on a graph is Stack.
Question 18 
Depth first search graph search algorithm uses ____ data structure for its implementation.
Stack
 
Tree  
Dequeue
 
Queue 
Whereas Breadth first search algorithm uses queue data structure for its implementation.
Question 19 
For implementation of recursion system uses ____ data structure.
Linked list
 
Deque  
Stack  
Queue

Question 20 
Queue structure is used in ____
Polynomial addition  
Recursion
 
Depth First search algorithm
 
Breadth First search algorithm

Recursion uses stack data structure.
Depth first search algorithm uses stack data structure.
Breadth first search algorithm uses queue data structure.
Question 21 
____ is First in last out kind of data structure.
Stack  
Array  
Deque
 
Queue

A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).
Question 22 
With respect to deque which of the following is true?
Insertion is done from front end
 
Insertion and deletion can be done at front and rear ends  
Deletion is done from rear end
 
Insertion is done only from rear end
