Queues-and-Stacks

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 _________.

A
256
B
257
C
258
D
259
Question 1 Explanation: 
The maximum possible number of iterations of the while loop in this algorithm is:
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

What is the minimum number of stacks of size n required to implement a queue of size n?

A
One
B
Two
C
Three
D
Four
Question 2 Explanation: 
Minimum number of stacks of size n required to implement a queue of size n is two. With the help of two stacks we can able to implement a queue.
Question 3

Consider the following statements:

    (i) First-in-first out types of computations are efficiently supported by STACKS.
    (ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
    (iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.
    (iv) Last-in-first-out type of computations are efficiently supported by QUEUES.

Which of the following is correct?

A
(ii) and (iii) are true
B
(i) and (ii) are true
C
(iii) and (iv) are true
D
(ii) and (iv) are true
Question 3 Explanation: 
(i) FIFO computation efficiently supported by queues.
(iv) LIFO computation efficiently supported by stacks.
Then given (i) and (iv) are false.
Answer:- A
Question 4

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.

A
Theory Explanation.
Question 5

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?

A
Theory Explanation.
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?

A
n+m ≤ x < 2n and 2m ≤ y ≤ n+m
B
n+m ≤ x< 2n and 2m ≤y ≤ 2n
C
2m ≤ x< 2n and 2m ≤ y ≤ n+m
D
2m ≤ x < 2n and 2m ≤ y ≤ 2n
Question 6 Explanation: 
Let's first consider for push, i.e., x.
Best case:
First push m elements in S1 then pop m elements from S1 and push them in S2 and then pop all m elements from S2. Now push remaining (n-m) elements to S1.
So total push operation
= m + m + (n-m)
= n+m
Worst Case:
First push all n elements in S1. Then pop n elements from S1 and push them into S2. Now pop m elements from S2.
So total push operation
= n+n
= 2n
Now lets consider for pop operation, i.e., y.
For best case:
First push m elements in S1, then pop m elements and push them in S2. Now pop that m elements from S2. Now push remaining (n-m) elements in S1.
So total pop operation
= m+m
= 2m
For worst case:
First push n elements in S1, then pop them from S1 and push them into S2. Now pop m elements fro m S2.
So total pop operation
= n+m
Therefore, option A is correct answer.
Question 7

A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented INSERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in

A
non-increasing order
B
non-decreasing order
C
strictly increasing order
D
strictly decreasing order
Question 7 Explanation: 
In stack last element pushed should be popped first. And in priority queue Q, minimum element is given the highest priority. So whenever we will call DELETEMIN(Q), it will pop the element with min value. So we can conclude that the minimum element should be inserted last or the insertion should be in decreasing order. And also it should be in strictly decreasing order, because for two elements with equal value the priority queue will pick any of one randomly which should not be the case in the stack.
Question 8

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)?

A
6
B
4
C
3
D
2
Question 8 Explanation: 
2, -3, 2, -1, 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 9
Consider the following sequence of operations on an empty stack.
          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 ________
A
86
Question 9 Explanation: 

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 10
Consider a sequence a of elements a0 = 1, a1 = 5, a2 = 7, a3 = 8, a4 = 9, and a5 = 2. The following operations are performed on a stack S and a queue Q, both of which are initially empty.
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 _____?
A
8
Question 10 Explanation: 
Given the sequence “a” of elements a0 = 1, a1 = 5, a2 = 7, a3 = 8, a4 = 9, and a5 = 2.
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 11
The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
A
A
B
B
C
C
D
D
Question 11 Explanation: 
When five items: A, B, C, D, and E are pushed in a stack: Order of stack becomes: A, B, C, D, and E (A at the bottom and E at the top.) stack is popped four items and each element is inserted in a queue: Order of queue: B, C, D, E (B at rear and E at the front) Order of stack after pop operations = A. Two elements deleted from the queue and pushed back stack: New order of stack = A, E, D(A at the bottom, D at the top) As D is on the top so when pop operation occurs D will be popped out. So, correct option is (D).
Question 12
The best data structure to check whether an arithmetic expression has balanced parenthesis is a
A
Queue
B
Stack
C
Tree
D
List
Question 12 Explanation: 
→ The stack is the best data structure to validate the arithmetic expression.
→ 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 13
Stack A has the entries a, b, c (with a on top). Stack B is empty. An entry popped out of stack A can be printed immediately or pushed to stack B. An entry popped out of the stack B can be only be printed. In this arrangement, which of the following permutations of a, b, c are not possible?
A
b a c
B
b c a
C
c a b
D
a b c
Question 13 Explanation: 
Explanation:
Option (A):
Pop a from stack A
Push a to stack B
Print b
Print a from stack B
Print c from stack A
Order = b a c
Option (B):
Pop a from stack A
Push a to stack B
Print b from stack A
Print c from stack A
Print a from stack A
Order = b c a
Option (C):
Pop a from stack A
Push a to stack B
Pop b from stack A
Push b to stack B
Print c from stack A
Now, printing a will not be possible.
Question 14
The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
A
A
B
B
C
C
D
D
Question 14 Explanation: 

Question 15
The following postfix expression with single digit operands is evaluated using a stack:
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
A
6,1
B
5,7
C
3,2
D
1,5
Question 15 Explanation: 
Expression: 8 2 3 ^ / 2 3 * + 5 1 * –
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 16
Consider a standard Circular Queue ‘q’ implementation (which has the same condition for Queue Full and Queue Empty) whose size is 11 and the elements of the queue are q[0], q[1], q[2]…..,q[10]. The front and rear pointers are initialized to point at q[2] . In which position will the ninth element be added?
A
q[0]
B
q[1]
C
q[9]
D
q[10]
Question 16 Explanation: 
A circular queue is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end.
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 17
The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
A
A
B
B
C
C
D
D
Question 17 Explanation: 
Stack representation after inserting 5 elements
Question 18
Which of the following is NOT represented in a subroutine activation record frame for a stack-based programming language?
A
Values of local variables
B
Return address
C
Heap area
D
Information needed to access non local variables
Question 18 Explanation: 
Stack is used for static memory allocation and Heap for dynamic memory allocation, both stored in the computer's RAM .
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 19
______ to evaluate an expression an execution without any embedded function calls
A
Two stacks are required
B
One stack is needed
C
Three stacks are required
D
More than three stacks are required
Question 19 Explanation: 
Applications of stack are
Converting infix expression into post/prefix expression
Evaluating post/pre-fix expression
Parenthesis matching
With one stack also we can easily evaluate the expression.
Question 20
A__ is a linear list in which insertions and deletions are made to from either end of the structure.
A
Circular queue
B
Priority queue
C
Stack
D
Dequeue
Question 20 Explanation: 
● A deque, also known as a double ended queue, is an ordered collection of items similar to the queue. It has two ends, a front and a rear, and the items remain positioned in the collection.
● 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 21
Assume that the operators +,-,x are left associative and 6 right associative. the order of precedence(from highest to lowest) is 6,x,+,-. The postfix expression corresponding to the infix expression a+bxc-d^e^f is
A
abc x+def^^-
B
abc xde^f^-
C
ab +c xd -e^f ^
D
-+ a x bc ^^def
Question 21 Explanation: 
a+bc-d^e^f
⟶ left to right
Step 1: abc+
Question 22
A priority queue is implemented as a Max-heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10,8,5,3,2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is
A
10,8,7,3,2,1,5
B
10,8,7,2,3,1,5
C
10,8,7,1,2,3,5
D
10,8,7,5,3,2,1
Question 22 Explanation: 
Max-Heap has 5 elements:
The level order traversal in this max heap final is:
10, 8, 7, 3, 2, 1, 5.
Question 23
_____ is used to convert from recursive to iterative implementation of an algorithm
A
Array
B
Tree
C
Stack
D
Queue
Question 23 Explanation: 
→ Stack is used to convert recursive to iterative implementation of an algorithm using last in first out method.
→ Stack to hold information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes.
→ The functions follow a runtime protocol between caller and callee to save arguments and return value on the stack. Stacks are an important way of supporting nested or recursive function calls.
→ This type of stack is used implicitly by the compiler to support CALL and RETURN statements (or their equivalents) and is not manipulated directly by the programmer.
Question 24
____ number of queues are needed to implement a stack
A
1
B
2
C
3
D
4
Question 24 Explanation: 
→ Implementing stack by using two queues:
push(s,x)
1) Enqueue x to q1 (assuming size of q1 is unlimited). pop(s)
1) One by one dequeue everything except the last element from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item is result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
→ Implementing queue by using two stack:
(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.
There are 24 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access