Programming and data structure miscellaneous

Programming and data structure miscellaneous

Easy Questions

Programming & Data Structure

Programming and data structure miscellaneous
  1. An implementation of a queue Q, using two stacks S1 and S2 is given below
        void insert (Q, x) {
        push (S1, x);
        }
        void delete (Q) {
    if (stack-empty (S2)) then
        if (stack-empty (S1)) then {
          print (“Q is empty”);
          return;
        }
        else while (! (stack-empty (S1))) {
        x = pop (S1);
        push (S2, x);
        }
    x = pop (S2);
    }
    Let n insert and m(≤ n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?








  1. View Hint View Answer Discuss in Forum

    The order in which insert and delete operations are performed matters here.
    The best case : Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push operations are performed. So, total m+ n push (n push for insert() and m push for delete()) operations and 2m pop operations are performed.
    The worst case : First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations and n push operation are performed. Other than first, in all delete operations, 1 pop operation is performed. So, total m + n pop operations and 2n push operations are performed (n push for insert() and m push for delete())

    Correct Option: A

    The order in which insert and delete operations are performed matters here.
    The best case : Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push operations are performed. So, total m+ n push (n push for insert() and m push for delete()) operations and 2m pop operations are performed.
    The worst case : First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations and n push operation are performed. Other than first, in all delete operations, 1 pop operation is performed. So, total m + n pop operations and 2n push operations are performed (n push for insert() and m push for delete())

  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








  1. View Hint View Answer Discuss in Forum

    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

    Correct Option: A

    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

  1. Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?








  1. View Hint View Answer Discuss in Forum

    The queue can be implemated where ENQUEUE takes a sequence of three instructions (reverse, push, reverse) and DEQUEUE takes a single instruction (pop).

    Correct Option: C

    The queue can be implemated where ENQUEUE takes a sequence of three instructions (reverse, push, reverse) and DEQUEUE takes a single instruction (pop).

  1. Which one of the following is TRUE at any valid state in shift – reduce parsing?








  1. View Hint View Answer Discuss in Forum

    Viable prefixes appear only at the top of the stack and not inside is valid in shift reduce parsing, because we will write the shift reduce parsing program for every variable such that if any variable contain more than one possibility, it will choose the correct production.

    Correct Option: B

    Viable prefixes appear only at the top of the stack and not inside is valid in shift reduce parsing, because we will write the shift reduce parsing program for every variable such that if any variable contain more than one possibility, it will choose the correct production.

  1. An array contains four occurrences of 0, five occurrences of 1, and three occurrences of 2 in any order. The array is to be sorted using swap operations (elements that are swapped need to be adjacent).
    (a) What is the minimum number of swaps needed to sort such an array in the worst case?
    (b) Give an ordering of elements in the above array so that the minimum number of swaps needed to sort the array is maximum.








  1. View Hint View Answer Discuss in Forum

    (a) 47
    (b) 22210000 1111 Arrangements that satisfy one of the following two constraints are also correct.
    (i) 1’s in the first 4 positions and no 2 in the last 3 positions
    or

    (ii) 1’s in the last 3 positions and no zero in the first 4 positions
    or

    Correct Option: C

    (a) 47
    (b) 22210000 1111 Arrangements that satisfy one of the following two constraints are also correct.
    (i) 1’s in the first 4 positions and no 2 in the last 3 positions
    or

    (ii) 1’s in the last 3 positions and no zero in the first 4 positions
    or