Dark Mode On/Off

# Stack Data Structure Questions

This Test will cover basic concepts of Stack data Structure and related algorithm.
Q. Which one of the following is an application of Stack Data Structure?
 A. Managing function calls B. The stock span problem C. Arithmetic expression evaluation D. All of the above
Q. Which of the following is true about the linked list implementation of stack?
 A. In `push` operation, if new nodes are inserted at the beginning of linked list, then in `pop` operation, nodes must be removed from end. B. In `push` operation, if new nodes are inserted at the end, then in `pop` operation, nodes must be removed from the beginning. C. Both of the above D. None of the above
Q. Given below is a pseudocode that uses a stack. What will be the output for input `Studytonight` for the given pseudocode:
``````
declare a stack of characters;

while (there are more characters in the word to read)
{
push the character on the stack;
}
while (the stack is not empty)
{
pop a character off the stack;
write the character to the screen;
}
```
```
 A. StudytonightStudytonight B. thginotydutS C. Studytonight D. thginotydutSthginotydutS

Q. Following is an incorrect pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced or not. Which of the unbalanced sequences does the below code think is balanced?
``````declare a character stack;

while (more input is available)
{
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";```
```
 A. `((())` B. `())(()` C. `(()()))` D. `(()))() `
Q. The postfix expression specified below, with single digit operands is evaluated using a stack. The top two elements of the stack after the first `*` is evaluated will be (Note that `^` is the exponentiation operator):
``8 2 3 ^ / 2 3 * + 5 1 * ``
 A. 6, 1 B. 5, 7 C. 3, 2 D. 1, 5
Q. Assume that the operators `+`, `-`, `*` are left associative and `^` is right associative. The order of precedence (from highest to lowest) is `^`, `*`, `+`, `-`. The postfix expression corresponding to the infix expression `a + b x c - d ^ e ^ f` will be ?
 A. `abcx+def^^-` B. `abcx+de^f^-` C. `ab+cxd-e^f^` D. `-+axbc^^def`
Q. To evaluate an expression without any embedded function calls:
 A. One stack is enough B. Two stacks are needed C. As many stacks as the height of the expression tree are needed D. A Turing machine is needed in the general case
Q. The result of evaluating the postfix expression `10 5 + 60 6 / * 8 -` will be?
 A. 284 B. 213 C. 142 D. 71

Q. Suppose a stack is to be implemented using 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
Q. Consider `n` elements that are equally distributed in `k` stacks. In each stack, elements are arranged in ascending order (minimum value 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 the `n` elements in increasing order. What will be the time complexity of the best known algorithm?
 A. O(nlogk) B. O(nk) C. O(n2) D. O(k2)
Q. Which of the following statements is true:
 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
 A. (ii) and (iii) are true B. (i) and (ii) are true C. (iii) and (iv) are true D. (ii) and (iv) are true
Q. 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 will be in:
 A. Non-increasing order B. Non-decreasing order C. strictly increasing order D. strictly decreasing order

Q. A function `f` defined on stack 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
Q. Following is C like pseudocode for a function that takes a number as an argument, and uses a stack `S` to do the processing. What will the below function do in general?
``````
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
}
}
```
```
 A. Prints binary representation of `n` in reverse order B. Prints binary representation of `n` C. Prints the value of `Log n` D. Prints the value of `Log n` in reverse order
Q. 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" will be:
 A. `(top1 = MAXSIZE/2)` and `(top2 = MAXSIZE/2+1)` B. `top1 + top2 = MAXSIZE` C. `(top1 = MAXSIZE/2)` or `(top2 = MAXSIZE)` D. `top1 = top2 -1`