Question

Multiple choice data structures questions about stacks.

1. Here 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?
   • A. ((())
   • B. ())(()
   • C. (()()))
   • D. (()))()
2. 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: (()(())(()))?
   • A. 1
   • B. 2
   • C. 3
   • D. 4
   • E. 5 or more
3. Consider the usual algorithm for determining whether a sequence of parentheses is balanced. Suppose that you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order). What is the maximum number of parentheses that will ever appear on the stack AT ONE TIME during the computation?A. 1 B. 2 C. 3 D. 4 E. 5 or more

Answer 1

Ans 1: Option A.  ((())

Ans 2: Option C. 3

Ans 3: Option B. 2