Stack

Questions on Stack

1.          A Stack is a _______ DS

a.       LIFO

b.      FIFO

c.       LILO

d.      FILO

Ans. : a, d : A Stack is a Data Structure behaving Last in And First out or First In and Last Out.. They are one and the Same...

2.          In a Stack the elements are entered from ________.

a.       End

b.      Top

c.       Random

d.      Bottom

Ans. :  b. , The elements are entered and deleted from the stack from the top only.

3.          The basic Operations on the Stack are

a.       Push & Pop

b.      Insert & Delete

c.       Enter & Remove

d.      Add & Subtract

Ans. : a, Push and Pop are the terminologies used in use of the stack.

4.          Condition Checked before Pushing

a.       Stack Overflow

b.      Stack Underflow

c.       No Condition to be checked

d.      Both the conditions

Ans . :  a.  : Check Stack Overflow before pushing.

5.          Condition Checked before Poping

a.       Stack Overflow

b.      Stack Underflow

c.       No Condition to be checked

d.      Both the conditions

Ans . :  b.  : Check Stack Underflow before poping.

6.          The total nos of pair of brackets in an expression is called _______

a.       Open Scopes

b.      To be closed Scopes

c.       Nesting Depth

d.      Depth Sequence

Ans.   : c  Nesting Depth is the total nos. of open brackets in an expression at any time to be closed.

7.          Stacks are implemented using _________.

a.       Arrays

b.      Linked Lists

c.       Static Variables

d.      Register Variables

Ans.   :    a, b, Stack are implemented using arrays as well as linked list.

8.          Recursive function call uses _________ Data Structure.

a.       Stacks

b.      Queues

c.       Linked Lists

d.      Trees

Ans. :  a, Recursive Function Calls uses Stacks.

9. Entries in a stack are "ordered". What is the meaning of this statement?

1. A collection of stacks can be sorted.
2. Stack entries may be compared with the '<' operation.
3. The entries must be stored in a linked list.
4. There is a first entry, a second entry, and so on.

Ans. :  b, That is the reason it is used by infix and prefix expressions.

10. The operation for adding an entry to a stack is traditionally called:

a.       add

b.      append

c.       insert

d.      push

Ans. : d, Push is the operation traditionally used.

11. The operation for removing an entry from a stack is traditionally called:
1. delete
2. peek
3. pop
4. remove

Ans.  :  c, pop is the operation used for removing an entry.

12. Which of the following stack operations could result in stack underflow?
1. is empty
2. Continuously poping
3. Continuously pushing
4. This can never happen

Ans. : b,  Continuously poping can result in stack underflow.

13. Which of the following applications may use a stack?
1. A parentheses balancing program.
2. Keeping track of local variables at run time.
3. Syntax analyzer for a compiler.
4. All of the above.

Ans. : d, All of the above use a stack because they need kinda ordering.

14. Consider the following pseudo code:

  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 )

   {

      write the stack's top character to the screen

      pop a character off the stack

   }

What is written to the screen for the input "carpets"?

1. serc
2. carpets
3. steprac
4. ccaarrppeettss

Ans. : c, After working out it comes out to be “steprac” since stack is a last in first out system.

15. Here is an INCORRECT pseudo code 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?

1. ((( ))
2. ( ))(( )
3. (( )( )))
4. (( )))( )

Ans. : a, (   -> push => top = 0

             (   -> push => top = 1

            (   -> push => top = 2

            )  -> pop  =>  top = 1

           )  -> pop =>   top = 0

      While loop ends, and balanced is printed, but exp is unbalanced.                            

16. Consider the usual algorithm for determining whether a sequence of parentheses is balanced. What is the maximum number of parentheses that will appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()(())(()))?
1. 1
2. 2
3. 3
4. 4
5. 5 or more

Ans.  :  c, Max number of parentheses at a time will not be more than 3.

17. Suppose we have an array implementation of the stack, with ten items in the stack stored at data[0] through data[9]. The CAPACITY is 42. Where does the push member function place the new entry in the array?
1. data[0]
2. data[1]
3. data[9]
4. data[10]

Ans. : d, the next data is stored in data[10]

18. Consider the implementation of the stack using a partially-filled array. What goes wrong if we try to store the top of the stack at location [0] and the bottom of the stack at the last used position of the array?
1. Both peek and pop would require linear time.
2. Both push and pop would require linear time.
3. The stack could not be used to check balanced parentheses.
4. The stack could not be used to evaluate postfix expressions.

Ans. : b, because both push and pop will be required to be done on the top of the stack.

19. In the linked list implementation of the stack , where does the push member function place the new entry on the linked list?
1. At the head
2. At the tail
3. After all other entries those are greater than the new entry.
4. After all other entries those are smaller than the new entry.

Ans. a, The head acts as the top.

20. In the array version of the stack (with a fixed-sized array), which operations require linear time for their worst-case behavior?
1. is_empty
2. peek
3. pop
4. push

Ans. : c, Pop uses linear time.

21. In the linked-list version of the stack class, which operations require linear time for their worst-case behavior?
1. is_empty
2. peek
3. pop
4. push

Ans. : c, Pop would require linear time.

22. What is the value of the postfix expression 6 3 2 4 + - *:
1. Something between -15 and -100
2. Something between -5 and -15
3. Something between 5 and -5
4. Something between 5 and 15

Ans. : a, ans works out to be -18 and the infix expr. being 6*(3-(2+4))

23. 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. What is the maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?
1. 1
2. 2
3. 3
4. 4
5. 5

Ans . c, works out to be 3 at the max.

24.  The operation on stack that increments the top is called

1. Overflow
2. Push
3. Pop
4. Underflow

Ans)B

25.  The situation of deleting an element from a stack which doesn’t have elements is called

1. Overflow
2. Push
3. Pop
4. Underflow

Ans)D

26.   The time complexity of adding an element to a stack of n elements is?

1. O(1)
2. O(n)
3. O(n*n)
4. None

Ans)A

27.  The time complexity of deleting an element from a stack of n elements is?

1. O(n+1)
2. O(n)
3. O(1)
4. None

Ans)C

28.  A stack is said to be Full when it is _________

1. Unsorted
2. Underflow
3. Over flow
4. Sorted

Ans)C

29.  B(i) represents the bottom of I the stack and T(i) represents the
top of I the stack. When a Stack I will becomes full?

1. B(i)=T(i)
2. B(i+1) = T(i)+1
3. B(i-1)  = T(i+1)
4. B(i-1)  = T(i-1)

Ans)B

30.   what type of storage is used to represent stacks and queues

1. Random
2. Sequential
3. Dynamic
4. Logical

Ans : b , page 186 Tenenbaum 2^nd edition(2002)

31. Drawbacks of sequential storage in stacks

a. Fixed amount of storage remains allocated to the stack

b.No more than fixed amount of storage can be allocated to the stack

c. Both a) and b)

d.      None

            Ans : c, page 187 Tenenbaum 2^nd edition(2002)

32.  what is the infix expression of the given prefix expression  : +A*BC

1. A*B+C
2. A+B*C
3. (A+B)*C
4. A*(B+C)

Ans : b, Page no 242.Tenenbaum 1994 edition

33. what is the infix expression of the given prefix expression  : *+ABC
1. A*B+C
2. A+B*C
3. (A+B)*C
4. A*(B+C)

Ans : c, Page no 242.Tenenbaum 1994 edition

34. what is the infix expression of the given prefix expression  :

            +A*-BC$D*EF

1. ((A+B-C)*D)$(E*F)
2. A+B-C*D$E*F
3. A+(B-C)*D$(E*F)
4. ((A+B)-C*D)$E*F

Ans : c, Page no 242.Tenenbaum 1994 edition

35. what is the infix expression of the given prefix expression  :

            $+A*BC*+ABC

1. (A*B+C)$(A+B)*C
2. (A+B*C)$((A+B)*C)
3. A+(B*C)$A+(B*C)
4. (A+B)*C$A+(B*C)

Ans : b, Page no 242.Tenenbaum 1994 edition

36. what is the postfix expression of the given prefix expression  : +A*BC
1. ABC*+
2. AB+C*
3. AB*C+
4. ABC+*

Ans : a, Page no 242.Tenenbaum 1994 edition

37. what is the postfix expression of the given prefix expression  : *+ABC
1. ABC*+
2. AB+C*
3. AB*C+
4. ABC+*

Ans : b, Page no 242.Tenenbaum 1994 edition

38. what is the postfix expression of the given prefix expression  :

            +A*-BC$D*EF

1. ABCDEF-*$*+
2. ABC-DE*F$*+
3. AB-CDEF$**+
4. ABC-DEF*$*+

Ans : d, Page no 242.Tenenbaum 1994 edition

39. what is the postfix expression of the given prefix expression  :

            $+A*BC*+ABC

1. ABCABC*++*$
2. ABC+*AB+C*$
3. ABC*+AB+C*$
4. AB+C*AB+C*$

Ans : c, Page no 242.Tenenbaum 1994 edition

40. what is the infix expression of the given postfix expression  : ABC*+
1. A*B+C
2. A+B*C
3. (A+B)*C
4. A*(B+C)

Ans : b, Page no 242.Tenenbaum 1994 edition

41. what is the infix expression of the given Postfix expression  : AB+C*
1. A*B+C
2. A+B*C
3. (A+B)*C
4. A*(B+C)

Ans : c, Page no 242.Tenenbaum 1994 edition

42. what is the infix expression of the given Postfix expression  :

          ABC-DEF*$*+

1. ((A+B-C)*D)$(E*F)
2. A+B-C*D$E*F
3. A+(B-C)*D$(E*F)
4. ((A+B)-C*D)$E*F

Ans : c, Page no 242.Tenenbaum 1994 edition

43. what is the infix expression of the given Postfix expression  :

            ABC*+AB+C*$

1. (A*B+C)$(A+B)*C
2. (A+B*C)$((A+B)*C)
3. A+(B*C)$A+(B*C)
4. (A+B)*C$A+(B*C)

Ans : b, Page no 242.Tenenbaum 1994 edition

44. what is the postfix expression of the given Infix expression  : A+B*C
1. ABC*+
2. AB+C*
3. AB*C+
4. ABC+*

Ans : a, Page no 242.Tenenbaum 1994 edition

45. what is the postfix expression of the given Infix expression  : (A+B)*C
1. ABC*+
2. AB+C*
3. AB*C+
4. ABC+*

Ans : b, Page no 242.Tenenbaum 1994 edition

46. what is the postfix expression of the given Infix expression  :

            A+(B-C)*D$(E*F)

1. ABCDEF-*$*+
2. ABC-DE*F$*+
3. AB-CDEF$**+
4. ABC-DEF*$*+

Ans : d, Page no 242.Tenenbaum 1994 edition

47. what is the postfix expression of the given Infix expression  :

            (A+B*C)$((A+B)*C)

1. ABCABC*++*$
2. ABC+*AB+C*$
3. ABC*+AB+C*$
4. AB+C*AB+C*$

Ans : c, Page no 242.Tenenbaum 1994 edition

48. what is the Prefix expression of the given postfix expression  : ABC*+
1. +A*BC
2. +AB*C
3. +*ABC
4. *+ABC

Ans : a, Page no 242.Tenenbaum 1994 edition

49. what is the Prefix expression of the given Postfix expression  : AB+C*
1. +A*BC
2. +AB*C
3. +*ABC
4. *+ABC

Ans : d, Page no 242.Tenenbaum 1994 edition

50. what is the Prefix expression of the given Postfix expression  :

            ABC-DEF*$*+

1. +*-$*ABCDEF
2. A+*-BCD$*EF
3. +A*-BC$D*EF
4. +*-ABC$*DEF

Ans : c, Page no 242.Tenenbaum 1994 edition

51. what is the Prefix expression of the given Postfix expression  :

            ABC*+AB+C*$

1. $+**+ABCABC
2. $+A*BC*+ABC
3. $+*ABC*+ABC
4. +*ABC$*+ABC

Ans : b, Page no 242.Tenenbaum 1994 edition

52. what is the Prefix expression of the given Infix expression  : A+B*C
1. +AB*C
2. +*ABC
3. *+ABC
4. +A*BC

Ans : d, Page no 242.Tenenbaum 1994 edition

53. what is the Prefix expression of the given Infix expression  : (A+B)*C
1. *+ABC
2. +A*BC
3. +AB*C
4. +*ABC

Ans : a, Page no 242.Tenenbaum 1994 edition

54. what is the Prefix expression of the given Infix expression  :

            A+(B-C)*D$(E*F)

1. +*-$*ABCDEF
2. A+*-BCD$*EF
3. +*-ABC$*DEF
4. +A*-BC$D*EF

Ans : d, Page no 242.Tenenbaum 1994 edition

55. what is the Prefix expression of the given Infix expression  :

            (A+B*C)$((A+B)*C)

1. $+**+ABCABC
2. $+*ABC*+ABC
3. $+A*BC*+ABC
4. +*ABC$*+ABC

Ans : c, Page no 242.Tenenbaum 1994 edition

56) Consider the following statements.

(i) A stack is a list with the restriction that items are inserted or removed/deleted only at one position, namely the end of the list.

(ii) The general model is that one where there is some element that is at the top of the stack, and it is the only element that is visible.

(iii) A pop or top on an empty stack is generally considered an error in the stack ADT.

(iv) The fundamental operations on stacks are push and pop, where push is relevant to the removal of the most recently inserted element and pop is equivalent to an insertion.

(v) A stack is a list; insertion and deletion can be performed from both ends.

Which of the above statements is/are valid for stacks?

1. (i), & (ii) only

2. (i), (ii) & (iv) only

3. (i), (ii), (iii) & (iv) only

4. (i), (ii) & (iii) only

5. (i), (ii) & (v) only

Ans)   D

57)  Consider the following algorithm.

(i) Make an empty stack.

(ii) Read characters until end of the file.

(iii) If the character is an opening symbol, push it into the stack.

(iv)If it is a closing symbol, then if the stack is empty, report an error.

(v)Otherwise, pop the stack. If the symbol popped is not the corresponding opening symbol, then, report an error.

(vi)At end of the file, if the stack is not empty, report an error.

Identify, what the above algorithm intends to do.

1. Evaluating a mathematical expression

2. Check for balancing of parentheses, brackets and braces and ignore any other character that appears

3. Eliminating un-matched parentheses, brackets and braces and ignoring any other character that appears

4. Checking compiler errors

5. Determination of syntax errors

Ans) B

58)The following shows a series of stack operations.

1. Push(5)
2. Push(8)
3. Isempty( )
4. Pop( )
5. Push(3)
6. Pop( )
7. Pop( )
8. Pop( )
9. Isfull( )
10. Push(3)

If the above series of operations is performed, what would be the set returned values?

1. {false, 8, 3, 5, error, false, 3}

2. {5, 8, false, 8, 3, 5, error, false, 3}

3. {false, 8, 3, 5, error, false}

4. {false, 8,3, 5, false}

5. {false, 8, 3, 5, error, true}

Ans) C

59) Consider the following operations and their definitions.

(i) Clear( ) :– Clear the stack.

(ii) Is_Empty( ) :– Remove all items from the stack.

(iii) Insert( x) :- Insert element x in to any location of the stack.

(iv) Delete(p) :- Delete the element from the position p.

(v) Top( ) :- Return and remove the topmost element from the stack.

Which of the above operations is/are valid in stacks according to the basic definitions?

1. (i), (ii) and (v) only

2. (i)and (v) only

3. (i)only

4. (i)and (ii) only

5. (i), (ii), (iii), (iv) and (v)

Ans) C

60)  Consider the following infix expression.

((A+B)*C-(D-E))^(F+G)

Note: ^ denotes the power.

Equivalent postfix and prefix expressions are respectively

1. AB+C*DE--FG+^, ^-*ABC-DE+FG

2. AB+C*DE-FG+^, ^-*+ABC-DE+FG

3. AB+C*DE--FG+^, ^-*+ABC-DE+FG

4. AB+C*DE-FG+^, ^-*+ACB-DE+FG

5. AB+C*DE--FG+^, ^-*+CBA-DE+FG

Ans) C