NEW
Font size
WorksheetsStack and Queue
Total questions: 30
Worksheet time: 3600secs
Choose correct output for the following sequence of operations
push(5)
push(8)
pop
push(2)
push(5)
pop
pop
pop
push(1)
pop
8 5 2 5 1
8 5 5 2 1
8 2 5 5 1
8 1 2 5 5
Only top element can be accessed in stack
TRUE
FALSE
Consider the following operation performed on a stack of size 5.
Push(1);
Pop();
Push(2);
Push(3);
Pop();
Push(4);
Pop();
Pop();
Push(5);
After the completion of all operation, the no of element present on stack are
1
2
3
4
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
If the elements “A”, “B”, “D” and “C” are placed in a stack and are deleted one at a time, in what order will they be removed?
ABCD
ABDC
CDBA
DCAB
In linked list implementation of a queue, the important condition for a queue to be empty is?
FRONT is null
REAR is null
LINK is empty
None of the mentioned
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
How many queues are needed to implement a stack. 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 true about linked list implementation of queue?
In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.
In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.
Both of the above
None of the above
Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are
Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT
Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR
Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT
Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.
What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue?
O(n)
O(n+k)
O(nk)
O(n^2)
Suppose 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?
A queue cannot be implemented using this stack.
A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.
A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.
A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.
Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below.
The maximum possible number of iterations of the while loop in the algorithm is
16
32
64
256
Following is C like pseudo code of a function that takes a number as an argument, and uses a stack S to do processing.
What does the above function do in general?
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
The following postfix expression with single digit operands is evaluated using a stack:
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
If the sequence of operations - push (1), push (2), pop, push (1), push (2), pop, pop, pop, push (2), pop are performed on a stack, the sequence of popped out values
2,2,1,1,2
2,2,1,2,2
2,1,2,2,1
2,1,2,2,2
The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is
A
B
C
D
E
Consider the following operations performed on a stack of size 5 : Push (a); Pop() ; Push(b); Push(c); Pop(); Push(d); Pop();Pop(); Push (e) Which of the following statements is correct?
Underflow occurs
Stack operations are performed smoothly
Overflow occurs
None of the above
Which of the following is not an inherent application of stack?
Implementation of recursion
Evaluation of a postfix expression
Job scheduling
Reverse a string
Which of them is an abstract data structure (ADT)?
A) Stacks
B) Queues
Both A and C
C) Functions
Consider the usual algorithm for determining whether a sequence of parentheses is balanced.
Suppose that you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order).
The maximum number of parentheses that appear on the stack AT ANY ONE TIME during the computation?
1
2
3
4 or more
User perform following operations on stack of size 5 then -
push(1);
pop();
push(2);
push(3);
pop();
push(2);
pop();
pop();
push(4);
pop();
pop();
push(5);
Overflow Occurs
Stack Operations will be performed Smoothly
Underflow Occurs
None of these
What is the value of the postfix expression 6 3 2 4 + – *
1
40
74
-18
The following postfix expression with single digit operands is evaluated using a stack:
8 2 3 ^ / 2 3 * + 5 1 * -
6,1
5,7
3,2
1,5
To evaluate an expression without any embedded function calls:
One stack is enough
Two stacks are needed
As many stacks as the height of the expression tree are needed
A Turing machine is needed in the general case
What will be the postfix form of the above expression -
(A+B)∗(C∗D-E)∗F/G
None of these
A B + C D ∗ E − F G ∗ / ∗
A B + C D E ∗ − F G / ∗ ∗
A B + C D ∗ E − F G / ∗ ∗
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
List of data in which element can be inserted and removed at the same end is called as __________.
array
stack
linked list
queue
Convert the infix exression
(A + B) * (C + D)
to Postfix.
A B C * + D +
A B + C D + *
A B * C D * +
A B + C + D +
