DataStructures Quiz-1

Following is C like pseudo code of a function that takes a number as an argument, and uses a stack S to do processing.

void fun(int n)

{

    Stack S;  // Say it creates an empty stack S

    while (n > 0)

    {

      // This line pushes the value of n%2 to stack S

      push(&S, n%2);

 

      n = n/2;

    }

 

    // Run while Stack S is not empty

    while (!isEmpty(&S))

      printf("%d ", pop(&S)); // pop an element from S and print it

}

• Prints binary representation of n in reverse order

• Prints binary representation of n

• Prints the value of Logn

• Prints the value of Logn in reverse order

Which one of the following is an application of Stack Data Structure?

• Managing function calls

• The stock span problem

• Arithmetic expression evaluation

• All of the above

Consider the following pseudocode that uses a stack 

• C

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 )

{

   pop a character off the stack

   write the character to the screen

}What is output for input "geeksquiz"?

• geeksquizgeeksquiz

• ziuqskeeg

• geeksquiz

• ziuqskeegziuqskeeg

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:

• 6, 1

• 5, 7

• 3, 2

• 1, 5

A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl< top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is (GATE CS 2004)

• (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)

• top1 + top2 = MAXSIZE

• (top1= MAXSIZE/2) or (top2 = MAXSIZE)

• top1= top2 -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

• 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

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

• 284

• 213

• 142

• 71

A priority queue Q is used to implement a stack S that stores characters. PUSH(C) is implemented as INSERT(Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in

• Non-increasing order

• Non-decreasing order

• strictly increasing order

• strictly decreasing order

Consider the following statements:

i. First-in-first out types of computations are efficiently supported by STACKS.

ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.

iii. Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.

iv. Last-in-first-out type of computations are efficiently supported by QUEUES.

Which of the following is correct?

• (ii) is true

• (i) and (ii) are true

• (iii) is true

• (ii) and (iv) are true