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?
Q. Which of the following is true about the linked list implementation of stack?
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)
{
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;
}
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)
{
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";
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 *
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 ?
Q. To evaluate an expression without any embedded function calls:
Q. The result of evaluating the postfix expression 10 5 + 60 6 / * 8 - will be?
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)?
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?
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 |
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:
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)?
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
}
}
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:
