Test: Stacks & Queues

# Test: Stacks & Queues

Test Description

## 15 Questions MCQ Test Programming and Data Structures | Test: Stacks & Queues

Test: Stacks & Queues for Computer Science Engineering (CSE) 2023 is part of Programming and Data Structures preparation. The Test: Stacks & Queues questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Stacks & Queues MCQs are made for Computer Science Engineering (CSE) 2023 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Stacks & Queues below.
Solutions of Test: Stacks & Queues questions in English are available as part of our Programming and Data Structures for Computer Science Engineering (CSE) & Test: Stacks & Queues solutions in Hindi for Programming and Data Structures course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Stacks & Queues | 15 questions in 45 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Programming and Data Structures for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
 1 Crore+ students have signed up on EduRev. Have you?
Test: Stacks & Queues - Question 1

### Which of the following is true about linked list implementation of stack?

Detailed Solution for Test: Stacks & Queues - Question 1

To keep the Last In First Out order, a stack can be implemented using linked list in two ways:

a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from beginning.

b) In push operation, if new nodes are inserted at the end of linked list, then in pop operation, nodes must be removed from end.

Test: Stacks & Queues - Question 2

### Consider the following pseudocode that uses a stack declare a stack of characters while ( there are more characters in the word to read ) {    read a character    push the character on the stack } while ( the stack is not empty ) {    pop a character off the stack    write the character to the screen } What is output for input “geeksquiz”?

Detailed Solution for Test: Stacks & Queues - Question 2

Since the stack data structure follows LIFO order. When we pop() items from stack, they are popped in reverse order of their insertion (or push())

Test: Stacks & Queues - Question 3

### Following is an incorrect pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced: declare a character stack  while ( more input is available) {    read a character    if ( the character is a '(' )        push it on the stack    else if ( the character is a ')' and the stack is not empty )       pop a character off the stack    else       print "unbalanced" and exit  }  print "balanced" Which of these unbalanced sequences does the above code think is balanced?

Detailed Solution for Test: Stacks & Queues - Question 3

At the end of while loop, we must check whether the stack is empty or not. For input ((()), the stack doesn’t remain empty after the loop.

Test: Stacks & Queues - Question 4

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:

Detailed Solution for Test: Stacks & Queues - Question 4

The algorithm for evaluating any postfix expression is fairly straightforward:

1. While there are input tokens left
o Read the next token from input.
o If the token is a value
+ Push it onto the stack.
o Otherwise, the token is an operator
(operator here includes both operators, and functions).
* It is known a priori that the operator takes n arguments.
* If there are fewer than n values on the stack
(Error) The user has not input sufficient values in the expression.
* Else, Pop the top n values from the stack.
* Evaluate the operator, with the values as arguments.
* Push the returned results, if any, back onto the stack.
2. If there is only one value in the stack
o That value is the result of the calculation.
3. If there are more values in the stack
o (Error)  The user input has too many values.

Let us run the above algorithm for the given expression.
First three tokens are values, so they are simply pushed. After pushing 8, 2 and 3, the stack is as follows

8, 2, 3

When ^ is read, top two are popped and power(2^3) is calculated

8, 8

When / is read, top two are popped and division(8/8) is performed

1

Next two tokens are values, so they are simply pushed. After pushing 2 and 3, the stack is as follows

1, 2, 3

When * comes, top two are popped and multiplication is performed.

1, 6

Test: Stacks & Queues - Question 5

A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl< top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is

Detailed Solution for Test: Stacks & Queues - Question 5

If we are to use space efficiently then size of the any stack can be more than MAXSIZE/2.
Both stacks will grow from both ends and if any of the stack top reaches near to the other top then stacks are full. So the condition will be top1 = top2 -1 (given that top1 < top2)

Test: Stacks & Queues - Question 6

To evaluate an expression without any embedded function calls:

Detailed Solution for Test: Stacks & Queues - Question 6

Any expression can be converted into Postfix or Prefix form.

Prefix and postfix evaluation can be done using a single stack.

For example : Expression ’10 2 8 * + 3 -‘ is given.
PUSH 10 in the stack.
PUSH 2 in the stack.
PUSH 8 in the stack.
When operator ‘*’ occurs, POP 2 and 8 from the stack.
PUSH 2 * 8 = 16 in the stack.
When operator ‘+’ occurs, POP 16 and 10 from the stack.
PUSH 10 * 16 = 26 in the stack.
PUSH 3 in the stack.
When operator ‘-‘ occurs, POP 26 and 3 from the stack.
PUSH 26 – 3 = 23 in the stack.
So, 23 is the answer obtained using single stack.

Test: Stacks & Queues - Question 7

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

Detailed Solution for Test: Stacks & Queues - Question 7

f(S) = 0, max(f(S), 0) = 0, i = 2
f(S)new = max(f(S), 0) + i = 0 + 2 = 2

f(S) = 2, max(f(S), 0) = 2, i = -3
f(S)new = max(f(S), 0) + i = 2 – 3 = -1

f(S) = -1, max(f(S), 0) = 0, i = 2
f(S)new = max(f(S), 0) + i = 0 + 2 = 2

f(S) = 2, max(f(S), 0) = 2, i = -1
f(S)new = max(f(S), 0) + i = 2 – 1 = 1

f(S) = 1, max(f(S), 0) = 1, i = 2
f(S)new = max(f(S), 0) + i = 1 + 2 = 3

Thus, option (C) is correct.

Test: Stacks & Queues - Question 8

Consider the following C program:

#include
#define EOF -1
void push (int); /* push the argument on the stack */
int pop  (void); /* pop the top of the stack */
void flagError ();
int main ()
{         int c, m, n, r;
while ((c = getchar ()) != EOF)
{ if  (isdigit (c) )
push (c);
else if ((c == '+') || (c == '*'))
{          m = pop ();
n = pop ();
r = (c == '+') ? n + m : n*m;
push (r);
}
else if (c != ' ')
flagError ();
}
printf("% c", pop ());
}

What is the output of the program for the following input ?
5 2 * 3 3 2 + * +

Detailed Solution for Test: Stacks & Queues - Question 8

The function of the program is:-

1) If the current character is a digit it pushes into stack
2) Else if the current character is operator,  it pops two elements and then performs the operation.
Finally it pushes the resultant element into stack.
Initially stack s is empty. 5 2 * 3 3 2 + * +
1) 5 -> It pushes into s
2) 2 -> It pushes into s
3) * -> It pops two elements n = 2, m=5 n*m = 10 It pushes 10 into s
4) 3 -> It pushes into s
5) 3 -> It pushes into s
6) 2 -> It pushes into s
7) + -> n=2, m=3 n+m=5 It pushes 5 into s
8) * -> n=5, m=3 n*m=15 It pushes 15 into s
9) + -> n=15, m=10 n+m = 25 It pushes 25 into s.

Test: Stacks & Queues - Question 9

A priority queue Q is used to implement a stack S that stores characters. PUSH(C) is implemented as 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

Detailed Solution for Test: Stacks & Queues - Question 9

We are implementing a STACK using Priority Queue. Note that Stack implementation is always last in first out (LIFO) order.

As given “POP is implemented as DELETEMIN(Q)” that means Stack returns minimum element always.

So, we need to implement PUSH(C) using INSERT(Q, C, K) where K is key chosen from strictly-decreasing order(only this order will ensure stack will return minimum element when we POP an element). That will satify Last In First Out (LIFO) property of stack.

That is answer, option (D) is true.

Option (A) non-increasing order can not be true because two same (identical) numbers can not have same priority as priority should be distinguishable for each number.

Test: Stacks & Queues - Question 10

The seven elements A, B, C, D, E, F and G are pushed onto a stack in reverse order, i.e., starting from G. The stack is popped five times and each element is inserted into a queue.Two elements are deleted from the queue and pushed back onto the stack. Now, one element is popped from the stack. The popped item is ________.

Detailed Solution for Test: Stacks & Queues - Question 10 In fig:-1 elements are inserted into a stack then in fig:-2 top 5 elements are popped and these 5 elements are inserted into a queue which is shown in fig:-3, now first two elements are deleted from queue and pushed into stack one by one which is shown in fig:-5.
At top of the stack element B is presented.
So, option (B) is correct.

Test: Stacks & Queues - Question 11

If the sequence of operations – push (1), push (2), pop, push (1), push (2), pop, pop, pop, push (2), pop are performed on a stack, the sequence of popped out values

Detailed Solution for Test: Stacks & Queues - Question 11

The pop sequence can be seen from the following table: Test: Stacks & Queues - Question 12

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

Detailed Solution for Test: Stacks & Queues - Question 12

Let’s construct an empty stack and do the operations. Stack follows LIFO order.

1.Push(54) // (54)
2.Push(52) // (54,52)
3.Pop() // (54)
4.Push(55) //(54,55)
5.Push(62) //(54,55,62)
6.s=pop() // (54,55)
s=62;

Let’s construct an empty queue and do the operations. Queue follows FIFO order.

1.Enqueue(21) // 
2.Enqueue(24) // [21,24]
3.Dequeue() // 
4.Enqueue(28) // [24,28]
5.Enqueue(32) // [24,28,32]
6.q=Dequeue() // [28,32]
q=24;

s+q=62+24

So, s+q=86 .

Test: Stacks & Queues - Question 13

Convert the following infix expression into its equivalent post fix expression (A + B^ D) / (E – F) + G

Detailed Solution for Test: Stacks & Queues - Question 13

(A + B^ D) / (E – F) + G
= (A + B^ D)(E – F)/ + G
= (A + B^ D)(E – F)/G+
= A + BD^(E – F)/G+
= ABD^+EF-/G+
So, option (A) is correct.

Test: Stacks & Queues - 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

Detailed Solution for Test: Stacks & Queues - Question 14

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 on the 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).

Test: Stacks & Queues - Question 15

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?

Detailed Solution for Test: Stacks & Queues - Question 15

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.
So, option (C) is incorrect.

## Programming and Data Structures

71 docs|29 tests
 Use Code STAYHOME200 and get INR 200 additional OFF Use Coupon Code
Information about Test: Stacks & Queues Page
In this test you can find the Exam questions for Test: Stacks & Queues solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Stacks & Queues, EduRev gives you an ample number of Online tests for practice

71 docs|29 tests