DS TRaining Day 2

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

• a) Underflow
  

• b) Empty collection
  

• c) Overflow
  

• d) Garbage Collection

1.    What is the value of the postfix expression 6 3 2 4 + – *?

• a) 1
  

• b) 40
  

• c) 74
  

• d) -18

1.    Here is an infix expression: 4 + 3*(6*3-12). Suppose that we are using the usual stack algorithm to convert the expression from infix to postfix notation. The maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?

• a) 1
  

• b) 2
  

• c) 3
  

• d) 4

1.    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)      3,2

• b)      1,5

• c)      6,1

• d)     5,7

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

• a.      abc × + def ^ ^ -

• b.      abc × + de ^ f ^ -

• c.       ab + c × d - e ^ f ^

• d.      + a × bc ^ ^ def

1.    To evaluate an expression without any embedded function calls :

 

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

• b)     One stack is enough

• c)      Two stacks are needed

• d)     A Turing machine is needed in the general case

1.    The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is

• a)      284

• b)      213

• c)      142

• d)     71

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

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

 

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

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

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

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

1.    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?

• a)            O(n logk)

• b)            O(nk)

• c)            O(n2)

• d)           O(k2)