Stacks and Queues Quiz

In a stack, if a user tries to remove an element from an empty stack it is called _________

• Underflow

• Empty collection

• Overflow

• Garbage Collection

What is the value of the postfix expression 6 3 2 4 + - *?

• 1

• 40

• 74

• -18

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:

• 3,2

• 1,5

• 6,1

• 5,7

Assume that the operators +, -, × are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, x , +, -. The postfix expression corresponding to the infix expression a + b × c - d ^ e ^ f is

• abc × + def ^ ^ -

• abc × + de ^ f ^ -

• ab + c × d - e ^ f ^

• + a × bc ^ ^ def

To evaluate an expression without any embedded function calls : As many stacks as the height of the expression tree are needed One stack is enough Two stacks are needed A Turing machine is needed in the general case

• As many stacks as the height of the expression tree are needed

• One stack is enough

• Two stacks are needed

• A Turing machine is needed in the general case

The result evaluating the postfix expression 10 5 + 60 6 / * 8 - is

• 284

• 213

• 142

• 71

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

Suppose a stack is to be implemented with a linked list instead of an array. What would be the effect on the time complexity of the push and pop operations of the stack implemented using linked list (Assuming stack is implemented efficiently)?

• O(1) for insertion and O(n) for deletion

• O(1) for insertion and O(1) for deletion

• O(n) for insertion and O(1) for deletion

• O(n) for insertion and O(n) for deletion

Consider n elements that are equally distributed in k stacks. In each stack, elements of it are arranged in ascending order (min is at the top in each of the stack and then increasing downwards). Given a queue of size n in which we have to put all n elements in increasing order. What will be the time complexity of the best known algorithm?

• O(n logk)

• O(nk)

• O(n2)

• O(k2)

If the elements "A", "B", "C" and "D" are placed in a queue and are deleted one at a time, in what order will they be removed?

• ABCD

• DCBA

• DCAB

• ABDC