NEW
Font size
WorksheetsData Structures Training Quiz2
Total questions: 15
Worksheet time: 8mins
In a stack, if a user tries to remove an element from an empty stack it is called _________
Underflow
Empty Collection
Overflow
Garbage Collecction
What is the value of the postfix expression 6 3 2 4 + – *?
1
40
74
-18
Here is an infix expression: 4 + 3*(6*3-12). Suppose that we are using the usual stack algorithm to convert the expression from infix to postfix notation. The maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?
1
2
3
4
The following postfix expression with single digit operands is evaluated using a stack:
8 2 3 ^ / 2 3 + 5 1 -
Note: Note that ^ is the exponentiation operator. The top two elements of the stack after the
first * is evaluated are:
3,2
1,5
6,1
5,7
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 general case
The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is
284
213
142
71
A function f defined on stacks 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)?
6
4
3
2
Suppose a stack is to be implemented with 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)?
O(1) for insertion and O(n) for deletion
O(1) for insertion and O(1) for deletion
O(n) for insertion and O(1) for deletion
O(n) for insertion and O(n) for deletion
Consider n elements that are equally distributed in k stacks. In each stack, elements of it are arranged in ascending order (min 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 n elements in increasing order. What will be the time complexity of the best known algorithm?
O(n log k)
O(nk)
O(n2)
O(k2)
If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, in what order will they be removed?
ABCD
DCBA
DCAB
ABDC
A normal queue, if implemented using an array of size MAX_SIZE, gets full when?
Rear = MAX_SIZE – 1
Front = (rear + 1)mod MAX_SIZE
Front = rear + 1
Rear = front
Which one of the following is an application of Queue Data Structure?
When a resource is shared among multiple consumers.
When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes
Load Balancing
All of the above
How many stacks are needed to implement a queue. Consider the situation where no other data structure like arrays, linked list is available to you
1
2
3
4
Which of the following is NOT a common operation in a queue data structure?
Enqueue
Dequeue
Peek
Shuffle
