Font size
WorksheetsQueue & Stack Data Structures
Total questions: 80
Worksheet time: 45mins
If the insertion and deletion happens from both the ends then the queue is called a______Queue
a) Deque
b) Header
c) Queue
d) Circular Queue
Process of inserting an element in stack is called ____________
Create
Push
Evaluation
Pop
Entries in a stack are “ordered”. What is the meaning of this statement?
A collection of stacks is sortable
Stack entries may be compared with the ‘<‘ operation
The entries are stored in a linked list
There is a Sequential entry that is one by one
Which of the following applications may use a stack?
a) A parentheses balancing program
b) Tracking of local variables at run time
c) Compiler Syntax Analyzer
d) Data Transfer between two asynchronous process
What is the value of the postfix expression 6 3 2 4 + – *:
1
14
74
-18
The data structure required to check whether an expression contains balanced parenthesis is?
a) Stack
b) Queue
c) Array
d) Tree
Circular Queue is also known as ________
a) Ring Buffer
b) Square Buffer
c) Rectangle Buffer
d) Curve Buffer
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?
a) ABCD
b) DCBA
c) DCAB
d) ABDC
What does the following function do for a given Linked List with first node as head?
void fun1(struct node* head)
{
if(head == NULL)
return;
fun1(head->next);
printf("%d ", head->data);
}
a) Prints all nodes of linked lists
b) Prints all nodes of linked list in reverse order
c) Prints alternate nodes of Linked List
d) Prints alternate nodes in reverse order
Linked list data structure offers considerable saving in _____________
a) Computational Time
b) Space Utilization
c) Space Utilization and Computational Time
d) Speed Utilization
Which of the following is/are the levels of implementation of data structure
Abstract level
Application level
Implementation level
All of the above
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, 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
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 a circular queue, how do you increment the rear end of the queue?
rear++
(rear+1) % Number of Item
(rear % Number of Item)+1
rear–
What is the term for inserting into a full queue known as?
overflow
underflow
null pointer exception
all of the mentioned
Let the following circular queue can accommodate maximum six elements with the following data
front = 2 rear = 4
queue = _______; L, M, N, ___, ___
What will happen after ADD O operation takes place?
front = 2 rear = 5
queue = ______; L, M, N, O, ___
front = 3 rear = 5
queue = L, M, N, O, ___
front = 3 rear = 4
queue = ______; L, M, N, O, ___
front = 2 rear = 4
queue = L, M, N, O, ___
What is the reason for using a "circular queue" instead of a regular one?
running time of enqueue() is improved
reuse empty spaces
you can traverse all the elements more efficiently
none of the above
In Queue Insertion & Deletion take place at ________________.
same end
first end
different end
last end
One difference between a queue and a stack is:
Queues require dynamic memory, but stacks do not
Stacks require dynamic memory, but queues do not.
Queues use two ends of the structure; stacks use only one.
Stacks use two ends of the structure, queues use only one.
If the numbers 5, 10, 3, 42 are enqueued onto a queue in that order, what does dequeue return?
5
10
3
42
Queue can be implemented using a list?
True
False
What is the term for inserting into a full queue known as?
underflow
overflow
front
rear
The essential condition which is checked before insertion in a linked queue is?
Underflow
Overflow
Front value
Rear value
A queue of characters currently contained a,b,c,d. What would be the contents of queue after the following operationDELETE, ADD W, ADD X, DELETE, ADD Y.
A,B,C,W,Y
A,B,C,D,W
C,D,W,X,Y
W,Y,X,C,D
If front=rear ,then the queue is?
full
undeflow
overflow
empty
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
A Queue can only store 6 data items. The Queue is sent 4 data items: Bert, Cynthia, Cedric and Albert. Where does the "Rear" index pointer point?
0
1
2
3
A Queue can only store 6 data items. The Queue is sent 4 data items: Bert, Cynthia, Cedric and Albert. Where does the "Front" pointer point?
Bert
Cynthia
Cedric
Albert
If the character 'V', 'I', 'V', 'A' are placed in queue (in order), and being removed one at a time, choose the order for the character after that
AVIV
VIVA
VAVI
IVAV
In a stack, if a user tries to remove an element from empty stack it is called _________
Underflow
Empty collection
Overflow
Garbage Collection
Process of inserting an element in stack is called ____________
Create
Push
Evaluation
Pop
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
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
In a Queue Data Structure...
New elements may only be added to the end of the queue
Elements may only be retrieved from the front of the queue.
Elements may only be retrieved from the end of the queue.
New elements may only be added to the front of the queue
Select ALL the situations that a Queue data structure would be used?
Printer in a room full of computers
Characters typed on a keyboard
Back Button
Undo Button
Which is the correct operation for:
"Remove the front item from the queue and return it"
dQueue()
de.Queue(Item)
deQueue()
item.remove()
Cant be performed on a Queue Data Structure.
Which is the correct operation for:
"Remove the rear item from the queue and return it"
dQueue()
de.Queue(Item)
deQueue()
item.remove()
Cant be performed on a Queue Data Structure.
Which is the correct operation for:
"Add a item to the front of the queue."
enQueue(item)
Append.Queue(item)
enQueue()
AddItem(EnQueue())
Cant be performed on a Queue.
Select operations that can be performed on a Queue Data Structure...
isEmpty()
pop()
push()
isFull()
Append(Item)
Where would pointers be pointing if...
- Eli leaves the Queue
- Adam joins the Queue
front = 0 rear = 3
front = 1 rear = 4
front = 2 rear = 3
front = 0 rear = 4
front = 0 rear = 4
Where would pointers be pointing if...
- Eli leaves the Queue.
- Hanna joins the Queue.
- Adam joins the Queue.
- Jason leaves the Queue.
front = 0 rear = 5
front = 1 rear = 4
front = 2 rear = 4
front = 0 rear = 4
front = 2 rear = 5
What would happen if...
deQueue()
enQueue(Hanna)
enQueue(Steve)
enQueue(Jack)
front = 1 rear = 0
*and Steve would be unable to be added to position 0.
front = 1 rear = 5
*and Jack would be unable to be added to position 0
front = 0 rear = 5
front = 0 rear = 4
front = 1 rear = 4
Stacks follows____________ order
FIFO (First In First Out )
LIFO (Last In First Out)
Random
FILO(First In Last Out)
The examples of Linear Data Structures are
Stacks,Queues,Linked list
int,float,complex
Operators,tokens,punctuators
Tree, graph
Main Operations in Stacks are Called
Insertion and deletion
Push and Pop
append and insertion
append and pop
Insertion in Queue is done at_____ end , and deletion is at _______ end
start, last
front, rear
rear, front
begin, stop
Main Operations in Queue are Called
Enqueue and Dequeue
Append and Insertion
Push and Pop
append and traverse
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
While converting infix to postfix expression, what would be pushed into the stack?
only operators
opening symbol '('
operators and opening symbol
operands
operators and operands
While evaluating the postfix expression, what would be pushed into the stack?
operands
operators
operators and opening symbols
operators and operands
stack is not used for this evaluation
In a stack, if a user tries to remove an element from an empty stack it is called
Underflow
Empty Collection
Overflow
Garbage Collection
Pushing an element into a stack already having six elements and the size is six, then the stack has
Overflow
Crash
Underflow
User flow
A stack is a data structure in which elements
can be added to any position and removed only from the top
can be only added to the top and removed from any position
can be added and removed from the top only
can be added and removed from any position
The data structure required to check whether an expression contains balanced parenthesis is?
a) Stack
b) Queue
c) Array
d) Tree
Suppose you have the following series of queue operations.
q = Queue();
q.enqueue('hello');
q.enqueue('dog');
q.enqueue(3);
q.dequeue();
What items are left on the queue?
'hello', 'dog'
'dog', 3
'hello', 3
'hello', 'dog', 3
Suppose you have the following series of queue operations.
q = Queue();
q.enqueue(1);
q.enqueue(10);
q.enqueue(100);
q.dequeue();
q.dequeue();
What items are the output?
10010
101
110
10010
