WorksheetsStack & Queue
Total questions: 70
Worksheet time: 47mins
What is a stack in data structure?
A stack is a data structure that allows random access to its elements.
A stack is a non-linear data structure.
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle.
A stack is a linear data structure that follows the First-In-First-Out (FIFO) principle.
What are the two main operations performed on a stack?
insert and remove
add and remove
enqueue and dequeue
push and pop
How is a stack implemented using an array in C?
Using a linked list instead of an array.
Using a queue instead of a stack.
Using a binary tree instead of an array.
Using a fixed-size array and a top variable to keep track of the top element.
What is the time complexity of push and pop operations in a stack implemented using an array?
O(log n)
O(n^2)
O(1)
O(n)
What is the time complexity of accessing the top element of a stack implemented using an array?
O(log n)
O(n)
O(1)
O(n^2)
What is a stack overflow?
A stack overflow is when a program's variables exceed their maximum size.
A stack overflow is when a program's call stack exceeds its maximum size.
A stack overflow is when a program encounters an infinite loop.
A stack overflow is when a program runs out of memory.
What is a stack underflow?
An item is popped from a full stack.
An item is popped from an empty stack.
An item is pushed onto an empty stack.
An item is pushed onto a full stack.
How is a stack implemented using a linked list in C?
By creating a linked list structure with a top pointer and using push and pop operations to add and remove elements from the top of the stack.
By creating a linked list structure with a tail pointer and using push and pop operations to add and remove elements from the tail of the stack.
By creating a linked list structure with a front pointer and using push and pop operations to add and remove elements from the front of the stack.
By creating a linked list structure with a bottom pointer and using enqueue and dequeue operations to add and remove elements from the bottom of the stack.
What is the time complexity of push and pop operations in a stack implemented using a linked list?
O(1)
O(log n)
O(n^2)
O(n)
What is the difference between a stack implemented using an array and a stack implemented using a linked list?
The array-based stack has a fixed maximum capacity, while the linked list-based stack can grow dynamically as needed.
The main difference is the way elements are stored and accessed: array-based stack uses a fixed-size contiguous block of memory, while linked list-based stack uses dynamically allocated nodes that are linked together.
The array-based stack allows for constant-time access to any element, while the linked list-based stack requires traversing the list to access an element.
The array-based stack is more memory efficient than the linked list-based stack due to its contiguous memory allocation.
In a stack, if a user tries to remove an element from an empty stack it is called _________
Underflow
Empty collection
Overflow
Garbage Collection
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 * - 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 the general case
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 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 logk)
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
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
Only top element can be accessed in stack
TRUE
FALSE
Stacks have LIFO ordering
TRUE
FALSE
The postfix form of the expression (A+ B)*(C*D- E)*F / G is?
AB + CDE * - * F *G /
AB+ CD*E - FG /**
AB + CD* E - F **G /
AB + CD* E - *F *G /
Which of them is an abstract data structure (ADT)?
Stacks
Functions
Queues
Both A and C
LIFO stands for
List of Outputs
Last in First Out
First in Last Out
None of them
Act of adding values into a stack is called
Popping
Polling
Pushing
None
The postfix form of A*B+C/D is?
*AB/CD+
AB*CD/+
A*BC+/D
ABCD+/*
Convert the following Infix expression to Postfix form using a stack
x + y * z + (p * q + r) * s
xyz*+pq*r+s*+
xyz*+pq*r+s+*
xyz+*pq*r+s*+
none
Which of the following statement(s) about stack data structure is/are NOT correct?
Stack data structure can be implemented using linked list
New node can only be added at the top of the stack
Stack is the FIFO data structure
The last node at the bottom of the stack has a NULL link
Which of the following application generally use a stack?
Parenthesis balancing program
Syntax analyzer in compiler
Keeping track of local variables at run time
All of the above
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
In linked list implementation of a queue, where does a new element be inserted?
At the head of link list
At the centre position in the link list
At the tail of the link list
None of the mentioned
In linked list implementation of a queue, from where is the item deleted?
At the head of link list
At the centre position in the link list
At the tail of the link list
None of the mentioned
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
What is the term for inserting into a full queue known as?
overflow
underflow
null pointer exception
all of the mentioned
a QUEUE in a computer acts just like people queuing for a bus - the first person in queue is going to be the first to get on the bus.
True
False
A Queue uses a front and rear pointer?
True
False
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
Stack can be implemented using _________ and ________ ?
Array and Binary Tree
Linked List and Graph
Array and Linked List
Queue and Linked List
When the function calls another function then the details of the previous function are stored in Stack?
Yes
No
Consider an empty stack of an integers. Let the numbers 4,5,6,7,8 to be pushed on to this stack only in the order they appeared from left to right. Let P indicates PUSH and Q indicates POP operation. What sequence of operations should be performed on stack in order to get the output as 548.
PPPXPPXX
PPXPPPXX
PPXXPPPX
PXXPPXPX
What is the postfix expression for the corresponding infix expression?
a+b*c+(d*e)
abc*+de*+
abc+*de*+
a+bc*de+*
abc*+(de)*+
What is the postfix expression for the infix expression?
a-b-c
abc--
ab – c –
– -abc
-ab-c
Which of the following statement is incorrect with respect to infix to postfix conversion algorithm?
operand is always placed in the output
operator is placed in the stack when the stack operator has lower precedence
parenthesis are included in the output
higher and equal priority operators follow the same condition
What is the corresponding postfix expression for the given infix expression?
a+(b*c(d/e^f)*g)*h)
ab*cdef/^*g-h+
abcdef^/*g*h*+
abcd*^ed/g*-h*+
abc*de^fg/*-*h+
What is the correct postfix expression for the following expression?
a+b*(c^d-e)^(f+g*h)-i
abc^de-fg+*^*+i-
abcde^-fg*+*^h*+i-
abcd^e-fgh*+^*+i-
ab^-dc*+ef^gh*+i-
In linked list implementation of a queue, where does a new element be inserted?
At the head of link list
At the tail of the link list
At the centre position in the link list
None
If the MAX_SIZE is the size of the array used in the implementation of circular queue, array index start with 0, front point to the first element in the queue, and rear point to the last element in the queue. Which of the following condition specify that circular queue is FULL?
Front=rear= -1
Front=(rear+1)%MAX_SIZE
Rear=front+1
Rear=(front+1)%MAX_SIZE
A circular queue is implemented using an array of size 10. The array index starts with 0, front is 6, and rear is 9. The insertion of next element takes place at the array index.
0
7
9
10
Which one of the following is not the application of the stack data structure
String reversal
Recursion
Backtracking
Asynchronous data transfer
What is the outcome of the prefix expression +, -, *, 3, 2, /, 8, 4, 1 ?
12
11
5
4
If the elements '1', '2', '3' and '4' are inserted in a queue, what would be order for the removal?
If the elements '1', '2', '3' and '4' are inserted in a stack, what would be order for the removal?
1234
4321
4321
1234
3241
4123
None
The time complexity of enqueue operation in Queue is __
O(1)
O(n)
O(logn)
O(nlogn)
Consider the following code.
int fun() {
if(isEmpty())
{
return -10;
}
else
{
int n;
n= q[front];
front++;
return n;
}
}
Which operation does the above code perform?
Enqueue
Dequeue
Return the front element
Both b and c
What would be the output after performing the following operations in a Deque?
Insertfront(10);
Insertfront(20);
Insertrear(30);
Insertrear(40);
Deletefront();
Insertfront(50);
Deleterear();
Display();
10, 20, 30
50, 10, 30
40, 20, 30
None of the above
Consider the implementation of the singly linked list having the head pointer only in the representation. Which of the following operations can be performed in O(1) time?
i) Deletion of the last node in the linked list
ii) Insertion at the front of the linked list
iii) Deletion of the first node in the linked list
iv) Insertion at the end of the linked list
ii
both ii and iii
both i and iv
both i and ii
Find the output of the following prefix expression.
*+2-2 1/-4 2+-5 3 1
2
12
10
4
If -*+abcd = 11, find a, b, c, d using evaluation of prefix algorithm.
a=2, b=3, c=5, d=4
a=1, b=2, c=5, d=4
a=5, b=4, c=7,d=5
a=1, b=2, c=3, d=4
n the given C snippet, find the statement number that has error.
//C code to push an element into a stack
1. void push( struct stack *s, int x)
2. {
3. if(s->top==MAX-1)
4. {
5. printf(“stack overflow”);
6. }
7. else
8. {
9. s->items[++s->top]=x;
10. s++;
11. }
12. }
1
9
10
11
The result of evaluating the postfix expression 5, 4, 6, +, , 4, 9, 3, /, +, is?
600
350
650
588
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
Consider the usual implementation of parentheses balancing program using stack. What is the maximum number of parentheses that will appear on stack at any instance of time during the analysis of ( ( ) ( ( ) ) ( ( ) ) )?
1
2
3
4
