QueuesandStacks
Question 1 
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 2 
A  
B  
C  
D 
Question 3 
Queue  
Stack  
Tree  
List 
→ While evaluating when left parentheses occur then it pushes into the stack when right parentheses occur pop from the stack. While at the end there is empty in the stack.
Question 4 
8 2 3 ^ / 2 3 * + 5 1 * –
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are
6,1  
5,7  
3,2  
1,5 
Rule (1): If the element is a number, Push it into stack.
Rule (2): If the element is an operator, Pop operands from the stack. Evaluate the operator operation and Push the result back into the stack.
Question 5 
A  
B  
C  
D 
Question 6 
q[0]  
q[1]  
q[9]  
q[10] 
The front and rear pointers are initialized to point at q[2] which means third element.
First element will add at q[3] , second element will add at q[4] and so on eight element will add at q[10].
Q[10] is the end of the queue which is connected to q[0]
So ninth element can be added at q[0] pointer
Question 7 
A  
B  
C  
D 
Question 8 
Values of local variables  
Return address  
Heap area  
Information needed to access non local variables 
Variables allocated on the stack are stored directly to the memory and access to this memory is very fast, and it's allocation is dealt with when the program is compiled
Variables allocated on the heap have their memory allocated at run time and accessing this memory is a bit slower, but the heap size is only limited by the size of virtual memory . Element of the heap have no dependencies with each other and can always be accessed randomly at any time
Question 9 
Circular queue  
Priority queue  
Stack  
Dequeue 
● What makes a deque different is the unrestrictive nature of adding and removing items.New items can be added at either the front or the rear.
● Likewise, existing items can be removed from either end. In a sense, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.
Question 10 
void fun(int n)
{
Stack s;//Say it creates an empty stack S
while(n>0)
{
// This line pushes the value of n%2 to
Stack S;
Push(&S,n%2);
n=n/2l
}
// Run while Stack S is not empty
while(!is Empty(&S)) Printf(%d",pop(&S));//pop an element from S and print it
}
What does the above function do in general order
Prints binary representation of n in reverse order  
prints binary representation of n  
Prints the value of Logn  
Prints the value of Logn in reverse order 
1) Let us take number 'NUM' and we want to check whether it's 0th bit is ON or OFF
bit = 2 ^ 0 (0th bit)
if NUM & bit == 1 means 0th bit is ON else 0th bit is OFF
2) Similarly if we want to check whether 5th bit is ON or OFF
bit = 2 ^ 5 (5th bit)
if NUM & bit == 1 means its 5th bit is ON else 5th bit is OFF.
Let us take unsigned integer (32 bit), which consist of 031 bits. To print binary representation of unsigned integer, start from 31th bit, check whether 31th bit is ON or OFF, if it is ON print “1” else print “0”. Now check whether 30th bit is ON or OFF, if it is ON print “1” else print “0”, do this for all bits from 31 to 0, finally we will get binary representation of number. void bin(unsigned n)
{
unsigned i;
for (i = 1 << 31; i > 0; i = i / 2)
(n & i)? printf("1"): printf("0");
}
int main(void)
{
bin(7);
printf("\n");
bin(4);
}
Question 11 
abc x+def^^  
abc xde^f^  
ab +c xd e^f ^  
+ a x bc ^^def 
⟶ left to right
Step 1: abc+
Question 12 
10,8,7,3,2,1,5  
10,8,7,2,3,1,5  
10,8,7,1,2,3,5  
10,8,7,5,3,2,1 
The level order traversal in this max heap final is:
10, 8, 7, 3, 2, 1, 5.
Question 13 
Both operations can be performed in O(1) time 
Question 14 
4 PUSH and 3 POP instructions  
5 PUSH and 4 POP instructions  
6 PUSH and 2 POP instructions  
5 PUSH and 3 POP instructions 
after converting postfix notation the notations are ab* cde /* +
Total 5 PUSH and 4 POP operations performed.
Question 15 
2,2,1,1,2  
2,2,1,2,2  
2,1,2,2,1  
2,1,2,2,2

Final Pop sequence: 22112
Question 16 
It cannot be implemented  
2 stacks  
4 stacks  
1 stack 
For this,
int x=element=stack1,pop();
stack2.push(element);
Step2: Once the complete stack1 gets copied to Stack2, then we can simply call pop() on s2, it will remove the element1.
So, A queue can be implemented using 2 stacks.
Question 17 
Considering 0address instructions machine, what will be the top of the stack after executing the following sequence of instructions?
PUSH 15, PUSH 4, PUSH 6, MULT, PUSH 30, ADD, ADD
30  
69  
54  
10 
Step1: PUSH 15,PUSH 4 and PUSH 6 from bottom to top. Now top of the stack value is 6.
Step2: Perform MULT operation. 6*4=24. Now present stack values are from bottom is 15 and 24.
Step3: Next again PUSH 30. Now top of the stack is 30.
Step4: Perform ADD operation. 30+24=54
Step5: Now present stack values are from bottom is 15 and 54. Perform ADD operation.
Step6: 15+54=69
Question 18 
O(n), O(n)  
O(n), O(1)  
O(1), O(n)  
O(1), O(1) 
Question 19 
(a) Parenthesis balancing program
(b) Process scheduling operating system
(c) Conversion of infix arithmetic expression to postfix form
(a) and (b)  
(b) and (c)  
(a) and (c)  
(a),(b) and (c) 
Question 20 
(i) (iii) (ii)
 
(ii) (i) (iii)  
(iii) (ii) (i)  
(ii) (iii) (i) 
→ Scheduling can be implemented using Queue.
→ The inorder traversal of binary search gives sorting order.
Question 21 
(a) Binary search in an array
(b) Breadth first search
(c) Implementing function calls
(d) Process scheduling
(b) and (d)  
(b) and (c)  
(a) and (c)  
(c) and (d) 
Binary search can be implemented by using recursion. So Stack is suitable for implementing function calls.
Question 22 
Front=rear=null  
Front=Rear!=null  
Front=Rear+1  
Front=Rear1 
Question 23 
Tree  
Stack  
Linked List  
Queue 
Algorithm
We have Postfix[ ] Array, Stack, Infix[ ] Array
1. Scan the given expression (Infix ) from Left to Right [ one character at a time].
2. Check Whether the given character is an operator [+, , *, /, ^ etc] or operand.
3. If it is an operand, then copy it in the Prefix Array.
4. If it is a operator then,
1. Check whether, Stack is empty or not
2. If it is empty then, push the operator in the stack and go to step
3. If Stack is not empty then compare the precedence of Top of stack with operator.
4. If the Top of Stack has higher or equal precedence then pop it and copy in the postfix array.
5. If the operator has higher precedence, push it in the stack and go to step 5.
6. If Stack is not empty go back to step 4(1).
5. Continue solving the expression in usual manner until the expression come to end.
6. Pop the remaining operand in the stack and copy it to postfix array.
Question 24 
String  
Queue  
Stack  
Linked list 
→ When the called procedure is done, it issues a return instruction, which pops the address from the top of the stack and transfers control there.
→ That’s just the basic processor mechanism that makes it easy to implement procedure calls. The actual details of identifying the parameters, placing them on the stack, executing a call instruction are up to the compiler.
→ In the called function, the compiler is responsible for ensuring any registers that may be clobbered are saved, allocating stack space for local variables, and then restoring the registers and stack prior to a return.
Question 25 
S  
P  
Q  
R 
Step2: Then we have to pop 4 elements. So, present having only one element,that is P.
Step3: 4 elements we have to insert into a Queue. Queue follows FIFO manner.
Step4: Again we have to delete two elements from queue and inserted into stack.
Step5: The inserted elements are T and S.
Step6: Final pop element is S.
Step7: Stack having only two elements. P and T.
Question 26 
If n_{A} is the number of elements in stack A and n_{B} is the number of elements in stack B, then overflow occurs when Push Operation is performed on either stack and
n_{A}=n_{B}  
n_{A}=n_{B}=n  
n_{A}+n_{B}=n  
n_{A}+n_{B}>=n 
→The sum of the n_{A} and n_{B} is equal to the number of elements there is no possibility of inserting element into stack.
Question 27 
abc*+deh/*  
ab+c*de/h*  
(a b c*)+(de/h*)  
abc*+de/h* 
=a+[bc*]d/e*h // Select highest priority operators and convert into postfix form,If same priority then go for associativity
=a+[bc*][de/]*h
=a+[bc*][de/h*]
=[abc*+][de/h*]
=abc*+de/h*
Question 28 
a) Implementation breadth first search
b) Implementation depth first search
c) Process scheduling
Which of the following is the correct option?
a and b  
a and c  
b and c  
a,b and c 
→Queue is also used for Breadth first traversal also
Question 29 
A  
B  
F  
G 
Step2: Stack is pooped five elements then stack is look like
Step3: Popped five elements are inserted into a queue then queue is look like
Step4: Two elements are deleted from the queue
Step5: deleted queue elements are pushed back onto the stack
Top of the stack is B.
Question 30 
S1: A queue can be implemented using two stacks.
S2: A stack can be implemented using two queues.
Which of the following is correct?
S 1 is correct and S 2 is not correct.  
S 1 is not correct and S 2 is correct.  
Both S 1 and S 2 are correct.  
Both S 1 and S 2 are incorrect. 
(1) When calling the enqueue method, simply push the elements into the stack 1.
(2) If the dequeue method is called, push all the elements from stack 1 into stack 2, which reverses the order of the elements. Now pop from stack 2.
→ A stack can be implemented using two queues
Question 31 
Underflow occurs  
Stack operations are performed smoothly  
Overflow occurs  
None of the above 
Question 32 
Implementation of recursion  
Evaluation of a postfix expression  
Job scheduling  
Reverse a string 
1. Implementation of recursion
2. Evaluation of a postfix expression
3. Expression evaluation and syntax parsing
4. Backtracking
5. Compile time memory management
6. Reverse a string
Question 33 
15  
14  
13  
12 
Step1: Total number of letters/operands with duplication is 5.
Step3: To find total number of ways, we have catalan formula.
Here, n=5
Catalan number = (2n)! / (n! * (n+1)!)
= (2*5)! / (5! * (5+1)!)
= 10! / (5! * 6!)
= 14
Note: We used catalan formula because they given in fully parenthesized to yield an infix expression.
Question 34 
2 deletions, 3 additions  
3 deletions, 2 additions  
3 deletions, 4 additions  
3 deletions, 3 additions 
Step1: Delete ‘a’ from queue. The deletion operation performs First In First Out.We will perform the deletion at front end
After deleting queue will become
Step3: Delete ‘b’ from queue. The deletion operation performs First In First Out.
After deleting queue will become
Step3: Delete ‘c’ from queue. The deletion operation performs First In First Out.
After deleting queue will become
Step4: Insert the element “c” into the queue, We will perform the insertion at rear end
The elements of queue after inserting the element ”c” are
Step5: Insert the element “b” into the queue,then the elements of queue after inserting the element ”b” are
step6: Insert the element “a” into the queue,then the elements of queue after inserting the element ”a” are
→ Step1,step2 and step3 are deletion operations and step4,step5 and step6 are deletions operations.
→ So total 3 deletions and 3 insertions are required to get required configuration.
Question 35 
O (log _{2} n)  
O (n)  
O (n log _{2} n)  
O (1) 
Question 36 
(A(B+C))*D  
((AB)+C)*D  
((A+B)C)*D  
(A+(BC))*D 
Question 37 
O (log _{2} n)  
O (n)  
O (n log _{2} n)  
O (1) 
Worst case in linked list:
Question 38 
defbc/++*  
def+/bc+*  
def+/bc *+  
None of these 
Postfix expression: d ef + / bc * +
Question 39 
(A(B+C))*D  
((AB)+C)*D  
((A+B)C)*D  
(A+(BC)*D) 
Question 40 
Level wise printing of tree  
Implementation of priority queues  
Function call implementation  
Depth first search in a graph 
Applications:
1.Bandwidth management
2.Discrete event simulation
3.Dijkstra's algorithm
4.Huffman coding
5.Bestfirst search algorithms
6.ROAM triangulation algorithm
7.Prim's algorithm for minimum spanning tree
Question 41 
2  
3  
4  
5 
i.e.., Maximum 3 parenthesis that will appear on the stack at any one time for parenthesis expression.
Question 42 
4  
3  
2  
1 
Question 43 
a b c d + – ∗ (where a = 8, b = 4, c = 2 and d = 5)
–3/8  
–8/3  
24  
–24 
Question 44 
stack  
tree  
queue  
linked list 
Question 45 
8 3 4 + – 3 8 2 / + * 2 $ 3 + is
17  
131  
64  
52 
Question 46 
S1 : It is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations.
S2 : The elements of a priority queue may be complex structures that are ordered on one or several fields.
Which of the following is correct ?
Both S1 and S2 are incorrect.  
S1 is correct and S2 is incorrect.  
S1 is incorrect and S2 is correct.  
Both S1 and S2 are correct 
S2: TRUE: The elements of a priority queue may be complex structures that are ordered on one or several fields.
Question 47 
ABC  
CBA  
BAC  
CAB 
OptionA: According to constraint,
Push(A) then Pop(A)
Push(B) then Pop(B)
Push(C) then Pop(C)
Then the possible pop sequence is ABC. So, it is TRUE
OptionB: According to given constraint, Push(A),Push(B) and Push(C) then Pop(C),
Pop(B) and Pop(A). The possible Pop sequence is CBA. So, it is TRUE
OptionC: According to given constraint, Push(A) and Push(B) then Pop(B) and Pop(A)
then push(C) and Pop(C). The possible Pop sequence is BAC. So, it is TRUE
OptionD: This is not possible.
Question 48 
Heap  
Circular array  
Linked list  
Binary tree 
→ In a priority queue, an element with high priority is served before an element with low priority.
→ In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.
→ While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map".
→ just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.
Question 49 
LIFO  
LILO  
FILO  
FIFO 
Question 50 
An array  
A stack  
A queue  
A linked list 
Question 51 
Circular Queue  
Linear Queue  
Stack  
Deque 
There are three scenario of inserting an element in a queue.
If (rear + 1)%maxsize = front, the queue is full. In that case, overflow occurs and therefore, insertion can not be performed in the queue.
If rear != max  1, then rear will be incremented to the mod(maxsize) and the new value will be inserted at the rear end of the queue.
If front != 0 and rear = max  1, then it means that queue is not full therefore, set the value of rear to 0 and insert the new element there.
Algorithm to insert an element in circular queue
Step 1: IF (REAR+1)%MAX = FRONT
Write " OVERFLOW "
Goto step 4
[End OF IF]
Step 2: IF FRONT = 1 and REAR = 1
SET FRONT = REAR = 0
ELSE IF REAR = MAX  1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: EXIT
Question 52 
Linked list  
Stack  
Array  
Tree 
Question 53 
Arrays
 
Stacks  
Queues  
Linked lists 
→ Recursion is one the application of stack. It supports many applications.
Applications:
1. Expression Evaluation
2. Expression Conversion
3. Syntax Parsing
4. Backtracking
5. Parenthesis Checking
6. String Reversal
Question 54 
defbc/+ +  
def+/bc+*  
def+/bc*+  
None of these 
Question 55 
Level wise printing of tree.  
Implementation of priority queues.  
Function call implementation  
Depth first search in a graph 
1. CPU scheduling
2. Disk Scheduling
3. synchronization(IO Buffers, pipes, file IO, etc.)
4. Breadth First search
5. Implementation of priority queues.
Question 56 
θ(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 57 
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 58 
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 59 
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 60 
If (rear == maxsize  1) rear=0; else rear = rear + 1; is required in
circular queue
 
linear queue  
stack  
deque

Question 61 
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 62 
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 63 
For implementation of recursion system uses ____ data structure.
Linked list
 
Deque  
Stack  
Queue

Question 64 
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 65 
____ 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 66 
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

Question 67 
Queue  
Stack  
File  
All the above 
Question 68 
Stack  
Binary Tree  
Queue  
All of the above 
Question 69 
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 70 
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 71 
Leftist Heap  
Binary Heap  
AVL trees  
Red – Black trees 