1. The postfix form of the expression (A+ B)*(C*D- E)*F / G is?
a) AB+ CD*E - FG /**
b) AB + CD* E - F **G /
c) AB + CD* E - *F *G /
d) AB + CDE * - * F *G /
2. The data structure required to check whether an expression contains balanced
parenthesis is?
a) Stack
b) Queue
c) Array
d) Tree
3. What data structure would you mostly likely see in a non recursive implementation of a
recursive algorithm?
a) LinkList
b) Stack
c) Queue
d) Tree
4. The process of accessing data stored in a serial access memory is similar to
manipulating data on a ------?
a) Heap
b) Binary Tree
c) Array
d) Stack
5. The postfix form of A*B+C/D is?
a) *AB/CD+
b) AB*CD/+
c) A*BC+/D
d) ABCD+/*
6. Which data structure is needed to convert infix notation to postfix notation?
a) Branch
b) Tree
c) Queue
7. The prefix form of A-B/ (C * D ⋀ E) is?
d) Stack
a) -/*⋀ACBDE
b) -ABCD*⋀DE
c) -A/B*C⋀DE
d) -A/BC*⋀DE
8. What is the result of the following operation
Top (Push (S, X))
a) X
b) Null
c) S
d) None
9. The prefix form of an infix expression p + q - r * t is?
a) + pq - *rt
b) - +pqr * t
c) - +pq * rt
d) - + * pqrt
10. Which data structure is used for implementing recursion?
a) Queue
b) Stack
c) Array
d) List
11. The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is?
a) 600
b) 350
c) 650
d) 588
(A + B ⋀D)/(E - F)+G
12. Convert the following infix expressions into its equivalent postfix expressions
a) (A B D ⋀ + E F - / G +)
c) (A B D ⋀ + E F/- G +)
b) (A B D +⋀ E F - / G +)
d) None
13. Convert the following Infix expression to Postfix form using a stack
x + y * z + (p * q + r) * s, Follow usual precedence rule and assume that the expression is legal.
a) xyz*+pq*r+s*+
b) xyz*+pq*r+s+*
c) xyz+*pq*r+s*+
d) none
14. Which of the following statement(s) about stack data structure is/are NOT correct?
a) Stack data structure can be implemented using linked list
b) New node can only be added at the top of the stack
c) Stack is the FIFO data structure
d) The last node at the bottom of the stack has a NULL link
15. Consider the linked list implementation of a stack. Which of the following node is
considered as Top of the stack?
a) First node
b) Last node
c) Any node
d) Middle node
16. 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
a) 1
b) 2
c) 3
d) 4
17. Which of the following is not an inherent application of stack?
a) Reversing a string
b) Evaluation of postfix expression
c) Implementation of recursion
d) Job scheduling
18. Which of the following operation take worst case linear time in the array implementation
of stack?
a) Push
b) Pop
c) IsEmpty
d) None
19. The type of expression in which operator succeeds its operands is?
a) Infix Expression
b) pre fix Expression
c) postfix Expression
d) None
20. Which of the following application generally use a stack?
a) Parenthesis balancing program
b) Syntax analyzer in compiler
c) Keeping track of local variables at run time
d) All of the above
21. Consider the following array implementation of stack:
#define MAX 10
Struct STACK
{
Int arr [MAX];
Int top = -1;
}
If the array index starts with 0, the maximum value of top which does not cause stack overflow is?
a) 8
b) 9
c) 10
d) 11
22. What is the minimum number of stacks of size n required to implement a queue of size
n?
a) One
b) Two
c) Three
23. Assume that the operators +,-, X are left associative and ⋀ is right associative. The
d) Four
order of precedence (from highest to lowest) is ⋀, X, +, -. The postfix expression
corresponding to the infix expression a + b X c – d ⋀ e ⋀ f is
a) abc X+ def ⋀ ⋀ -
c) ab+c Xd – e ⋀f⋀
b) abc X+ de⋀f⋀ -
d) -+aXbc⋀ ⋀def
24. If the elements “A”, “B”, “C” and “D” are placed in a stack and are deleted one at a time,
in what order will they be removed?
a) ABCD
b) DCBA
c) DCAB
d) ABDC
25. 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 ( ( ) ( ( ) ) ( ( ) ) )?
a) 1
b) 2
c) 3
d) 4
MCQs on Queue
1. A linear list of elements in which deletion can be done from one end (front) and
insertion can take place only at the other end (rear) is known as a ?
a) Queue
b) Stack
c) Tree
d) Linked list
2. The data structure required for Breadth First Traversal on a graph is?
a) Stack
b) Array
c) Queue
d) Tree
3. A queue is a ?
a) FIFO (First In First Out) list
b) LIFO (Last In First Out) list.
c) Ordered array
d) Linear tree
5. In Breadth First Search of Graph, which of the following data structure is used?
a) Stack
b) Queue
c) Linked list
d) None
6. 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) ABCD
7. In linked list implementation of a queue, where does a new element be inserted?
a) At the head of link list
b) At the tail of the link list
c) At the centre position in the link list
d) None
8. In the array implementation of circular queue, which of the following operation
take worst case linear time?
a) Insertion
b) Deletion
c) To empty a queue
d) None
9. In linked list implementation of queue, if only front pointer is maintained, which of
the following operation take worst case linear time?
a) Insertion
b) Deletion
c) To empty a queue
d) Both a) and c)
10. If the MAX_SIZE is the size of the array used in the implementation of circular
queue. How is rear manipulated while inserting an element in the queue?
a) rear=(rear%1)+MAX_SIZE
b) rear=rear%(MAX_SIZE+1)
c) rear=(rear+1)%MAX_SIZE
d) rear=rear+(1%MAX_SIZE)
11. 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?
a) Front=rear= -1
b) Front=(rear+1)%MAX_SIZE
c) Rear=front+1
d) Rear=(front+1)%MAX_SIZE
12. 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.
a) 0
b) 7
c) 9
d) 10
13. 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 EMPTY?
a) Front=rear=0
b) Front= rear=-1
c) Front=rear+1
d) Front=(rear+1)%MAX_SIZE
14. A data structure in which elements can be inserted or deleted at/from both the
ends but not in the middle is?
a) Queue
b) Circular queue
c) Dequeue
d) Priority queue
15. In linked list implementation of a queue, front and rear pointers are tracked.
Which of these pointers will change during an insertion into a NONEMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) None of the front and rear pointer
16. A normal queue, if implemented using an array of size MAX_SIZE, gets full when
a) Rear=MAX_SIZE-1
b) Front=(rear+1)mod MAX_SIZE
c) Front=rear+1
d) Rear=front
17. In linked list implementation of a queue, front and rear pointers are tracked.
Which of these pointers will change during an insertion into EMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) None
18. An array of size MAX_SIZE is used to implement a circular queue. Front, Rear,
and count are tracked. Suppose front is 0 and rear is MAX_SIZE -1. How many
elements are present in the queue?
a) Zero
b) One
c) MAX_SIZE-1
d) MAX_SIZE
19. Suppose a circular queue of capacity (n-1) elements is implemented with an
array of n elements. Assume that the insertion and deletion operations are carried
out using REAR and FRONT as array index variables, respectively. Initially
REAR=FRONT=0. The conditions to detect queue full and queue is empty are?
a) Full: (REAR+1)mod n == FRONT
Empty: REAR==FRONT
b) Full: (REAR+1)mod n == FRONT
Empty: (FRONT+1) mod n == REAR
c) Full: REAR==FRONT
Empty: (REAR+1) mod n==FRONT
d) Full: (FRONT+1)mod n==REAR
Empty: REAR==FRONT
