What does ‘stack overflow' refer to?

removing items from an empty stack

accessing item from an undefined stack

removing items from an empty stack

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 ‘

The entries are stored in a linked list

There is a Sequential entry that is one by one

What are the disadvantages of arrays?

We must know before hand how many elements will be there in the array

There are chances of wastage of memory space if elements inserted in an array are lesser than than the allocated size

Insertion and deletion becomes tedious

You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?

Add a new element at the end of the list

Insert a new element as a first element

Delete the last element of the list

Add a new element at the end of the list

What kind of linked list is best to answer question like “What is the item at position n?”

Array implementation of linked list

Which of these is an application of linked lists?

For separate chaining in hash-tables

Queues serve major role in

Simulation of arbitrary linked list

Simulation of limited resource allocation

Which of the following is true about linked list implementation of queue?

In push operation, if new nodes are inserted at the beginning, then in pop operation, nodes must be removed from the beginning

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 beginning, then in pop operation, nodes must be removed from the beginning

In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from end

Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?

Possible if size of linked list is even

Possible if size of linked list is odd

Possible if X is not first node

What is a memory efficient double linked list?

The list has breakpoints for faster traversal

Each node has only one pointer to traverse the list back and forth

The list has breakpoints for faster traversal

An auxiliary singly linked list acts as a helper list to traverse through the doubly linked list

Consider you have a stack whose elements in it are as follows.5 4 3 2

Push(pop()), push(6), push(pop())

Push(pop()), push(pop()), push(6)

How do you calculate the pointer difference in a memory efficient double linked list?

pointer to previous node – pointer to next node

pointer to previous node xor pointer to next node

pointer to previous node – pointer to next node

pointer to next node – pointer to previous node

Consider a small circular linked list. How to detect the presence of cycles in this list effectively?

Cannot determine, you have to pre-define if the list contains cycles

Keep one node as head and traverse another temp node till the end to check if its ‘next points to head

Have fast and slow pointers with the fast pointer advancing two nodes at a time and slow pointer advancing by one node at a time

Cannot determine, you have to pre-define if the list contains cycles

What does ‘stack underflow' refer to?

accessing item from an undefined stack

removing items from an empty stack

What are the advantages of priority queues?

Processes with different priority can be efficiently handled

Applications with differing requirements

66 + Mcqs in Abstract Data Types in Data Structures and Algorithms Page 1 McqOptions

1.	What does ‘stack overflow' refer to?
A.	accessing item from an undefined stack
B.	adding items to a full stack
C.	removing items from an empty stack
D.	index out of bounds exception
Answer» C. removing items from an empty stack

Discussion

2.	What happens when you pop from an empty stack while implementing using the Stack ADT in Java?
A.	Undefined error
B.	Compiler displays a warning
C.	EmptyStackException is thrown
D.	NoStackException is thrown
Answer» D. NoStackException is thrown

Discussion

3.	Entries in a stack are “ordered”. What is the meaning of this statement?
A.	A collection of stacks is sortable
B.	Stack entries may be compared with the ‘<‘ operation
C.	The entries are stored in a linked list
D.	There is a Sequential entry that is one by one
Answer» E.

Discussion

4.	What is the space complexity of a linear queue having n elements?
A.	O(n)
B.	O(nlogn)
C.	O(logn)
D.	O(1)
Answer» B. O(nlogn)

Discussion

5.	A double-ended queue supports operations like adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What's the time complexity of performing addFront and addRear? (Assume ‘m' to be the size of the stack and ‘n' to be the number of elements)
A.	O(m) and O(n)
B.	O(1) and O(n)
C.	O(n) and O(1)
D.	O(n) and O(m)
Answer» C. O(n) and O(1)

Discussion

6.	A linear collection of data elements where the linear node is given by means of pointer is called?
A.	Linked list
B.	Node list
C.	Primitive list
D.	None of the mentioned
Answer» B. Node list

Discussion

7.	What is the time complexity of deleting from the rear end of the dequeue implemented with a singly linked list?
A.	O(nlogn)
B.	O(logn)
C.	O(n)
D.	O(n2)
Answer» D. O(n2)

Discussion

8.	In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
A.	log2 n
B.	n⁄2
C.	log2 n – 1
D.	n
Answer» E.

Discussion

9.	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 of the mentioned
Answer» D. None of the mentioned

Discussion

10.	What is the time complexity to insert a node based on position in a priority queue?
A.	O(nlogn)
B.	O(logn)
C.	O(n)
D.	O(n2)
Answer» D. O(n2)

Discussion

11.	What are the disadvantages of arrays?
A.	We must know before hand how many elements will be there in the array
B.	There are chances of wastage of memory space if elements inserted in an array are lesser than than the allocated size
C.	Insertion and deletion becomes tedious
D.	All of the mentioned
Answer» E.

Discussion

12.	Given an array of size n, let's assume an element is ‘touched' if and only if some operation is performed on it(for example, for performing a pop operation the top element is ‘touched'). Now you need to perform Dequeue operation. Each element in the array is touched atleast?
A.	Once
B.	Twice
C.	Thrice
D.	Four times
Answer» E.

Discussion

13.	The postfix form of the expression (A+ B)(CD- E)*F / G is?
A.	AB+ CDE – FG /*
B.	AB + CD* E – F **G /
C.	AB + CD* E – F G /
D.	AB + CDE * – * F *G /
Answer» B. AB + CD* E – F **G /

Discussion

14.	Minimum number of queues to implement stack is ___________
A.	3
B.	4
C.	1
D.	2
Answer» D. 2

Discussion

15.	Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?
A.	Insertion Sort
B.	Quick Sort
C.	Heap Sort
D.	Merge Sort
Answer» E.

Discussion

16.	Convert the following infix expressions into its equivalent postfix expressions(A + B ⋀D)/(E – F)+G
A.	(A B D ⋀ + E F – / G +)
B.	(A B D +⋀ E F – / G +)
C.	(A B D ⋀ + E F/- G +)
D.	None of the mentioned
Answer» B. (A B D +⋀ E F – / G +)

Discussion

17.	You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?
A.	Delete the first element
B.	Insert a new element as a first element
C.	Delete the last element of the list
D.	Add a new element at the end of the list
Answer» D. Add a new element at the end of the list

Discussion

18.	The result of evaluating the postfix expression 5, 4, 6, +, , 4, 9, 3, /, +, is?
A.	600
B.	350
C.	650
D.	588
Answer» C. 650

Discussion

19.	The data structure required to check whether an expression contains balanced parenthesis is?
A.	Stack
B.	Queue
C.	Array
D.	Tree
Answer» B. Queue

Discussion

20.	Here is an infix expression: 4 + 3(63-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?
A.	1
B.	2
C.	3
D.	4
Answer» E.

Discussion

21.	What kind of linked list is best to answer question like “What is the item at position n?”
A.	Singly linked list
B.	Doubly linked list
C.	Circular linked list
D.	Array implementation of linked list
Answer» E.

Discussion

22.	The essential condition which is checked before deletion in a linked queue is?
A.	Underflow
B.	Overflow
C.	Front value
D.	Rear value
Answer» B. Overflow

Discussion

23.	What would be the asymptotic time complexity to find an element in the linked list?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	None of the mentioned
Answer» C. O(n2)

Discussion

24.	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 number of elements present in stack are
A.	1
B.	2
C.	3
D.	4
Answer» B. 2

Discussion

25.	Assume that the operators +,-, X are left associative and ^ is right associative.The order of precedence (from highest to lowest) is ^, X, +, -. The postfix expression for the infix expression a + b X c – d ^ e ^ f is
A.	abc X+ def ^^ –
B.	abc X+ de^f^ –
C.	ab+c Xd – e ^f^
D.	-+aXbc^ ^def
Answer» B. abc X+ de^f^ –

Discussion

26.	The prefix form of an infix expression p + q – r * t is?
A.	+ pq – *rt
B.	– +pqr * t
C.	– +pq * rt
D.	– + * pqrt
Answer» D. – + * pqrt

Discussion

27.	Which of these is an application of linked lists?
A.	To implement file systems
B.	For separate chaining in hash-tables
C.	To implement non-binary trees
D.	All of the mentioned
Answer» E.

Discussion

28.	Queues serve major role in
A.	Simulation of recursion
B.	Simulation of arbitrary linked list
C.	Simulation of limited resource allocation
D.	All of the mentioned
Answer» D. All of the mentioned

Discussion

29.	What is the value of the postfix expression 6 3 2 4 + – *:
A.	Something between -5 and -15
B.	Something between 5 and -5
C.	Something between 5 and 15
D.	Something between 15 and 100
Answer» E.

Discussion

30.	Which of the following is true about linked list implementation of queue?
A.	In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end
B.	In push operation, if new nodes are inserted at the beginning, then in pop operation, nodes must be removed from the beginning
C.	In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from end
D.	None of the mentioned
Answer» B. In push operation, if new nodes are inserted at the beginning, then in pop operation, nodes must be removed from the beginning

Discussion

31.	Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?
A.	Possible if X is not last node
B.	Possible if size of linked list is even
C.	Possible if size of linked list is odd
D.	Possible if X is not first node
Answer» B. Possible if size of linked list is even

Discussion

32.	What is a memory efficient double linked list?
A.	Each node has only one pointer to traverse the list back and forth
B.	The list has breakpoints for faster traversal
C.	An auxiliary singly linked list acts as a helper list to traverse through the doubly linked list
D.	None of the mentioned
Answer» B. The list has breakpoints for faster traversal

Discussion

33.	Consider you have a stack whose elements in it are as follows.5 4 3 2 << topWhere the top element is 2.You need to get the following stack6 5 4 3 2 << topThe operations that needed to be performed are (You can perform only push and pop):
A.	Push(pop()), push(6), push(pop())
B.	Push(pop()), push(6)
C.	Push(pop()), push(pop()), push(6)
D.	Push(6)
Answer» B. Push(pop()), push(6)

Discussion

34.	How do you calculate the pointer difference in a memory efficient double linked list?
A.	head xor tail
B.	pointer to previous node xor pointer to next node
C.	pointer to previous node – pointer to next node
D.	pointer to next node – pointer to previous node
Answer» C. pointer to previous node – pointer to next node

Discussion

35.	Which data structure is used for implementing recursion?
A.	Queue
B.	Stack
C.	Array
D.	List
Answer» C. Array

Discussion

36.	Which data structure is needed to convert infix notation to postfix notation?
A.	Branch
B.	Tree
C.	Queue
D.	Stack
Answer» E.

Discussion

37.	Consider a small circular linked list. How to detect the presence of cycles in this list effectively?
A.	Keep one node as head and traverse another temp node till the end to check if its ‘next points to head
B.	Have fast and slow pointers with the fast pointer advancing two nodes at a time and slow pointer advancing by one node at a time
C.	Cannot determine, you have to pre-define if the list contains cycles
D.	None of the mentioned
Answer» C. Cannot determine, you have to pre-define if the list contains cycles

Discussion

38.	Which of the following array position will be occupied by a new element being pushed for a stack of size N elements(capacity of stack > N).
A.	S[N-1].
B.	S[N].
C.	S[1].
D.	S[0].
Answer» C. S[1].

Discussion

39.	The postfix form of A*B+C/D is?
A.	*AB/CD+
B.	AB*CD/+
C.	A*BC+/D
D.	ABCD+/*
Answer» C. A*BC+/D

Discussion

40.	Which of the following data structures can be used for parentheses matching?
A.	n-ary tree
B.	queue
C.	priority queue
D.	stack
Answer» E.

Discussion

41.	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?
A.	1
B.	2
C.	3
D.	4 or more
Answer» C. 3

Discussion

42.	What does ‘stack underflow' refer to?
A.	accessing item from an undefined stack
B.	adding items to a full stack
C.	removing items from an empty stack
D.	index out of bounds exception
Answer» D. index out of bounds exception

Discussion

43.	Convert the following Infix expression to Postfix form using a stackx + y * z + (p * q + r) * s, Follow usual precedence rule and assume that the expression is legal.
A.	xyz+pqr+s*+
B.	xyz+pqr+s+*
C.	xyz+pqr+s*+
D.	None of the mentioned
Answer» B. xyz+pqr+s+*

Discussion

44.	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
Answer» B. DCBA

Discussion

45.	What is the space complexity for deleting a linked list?
A.	O(1)
B.	O(n)
C.	Either O(1) or O(n)
D.	O(logn)
Answer» B. O(n)

Discussion

46.	What are the advantages of priority queues?
A.	Easy to implement
B.	Processes with different priority can be efficiently handled
C.	Applications with differing requirements
D.	All of the mentioned
Answer» E.

Discussion

47.	Which of the following concepts make extensive use of arrays?
A.	Binary trees
B.	Scheduling of processes
C.	Caching
D.	Spatial locality
Answer» E.

Discussion

48.	If the elements “A”, “B”, “C” and “D” are placed in a stack and are deleted one at a time, what is the order of removal?
A.	ABCD
B.	DCBA
C.	DCAB
D.	ABDC
Answer» C. DCAB

Discussion

49.	Which of the following array element will return the top-of-the-stack-element for a stack of size N elements(capacity of stack > N).
A.	S[N-1].
B.	S[N].
C.	S[N-2].
D.	S[N+1].
Answer» B. S[N].

Discussion

50.	Given only a single array of size 10 and no other memory is available. Which of the following operation is not feasible to implement (Given only push and pop operation)?
A.	Push
B.	Pop
C.	Enqueue
D.	Returntop
Answer» D. Returntop

Discussion

Explore topic-wise MCQs in Data Structures and Algorithms.

What does ‘stack overflow' refer to?

What happens when you pop from an empty stack while implementing using the Stack ADT in Java?

Entries in a stack are “ordered”. What is the meaning of this statement?

What is the space complexity of a linear queue having n elements?

A linear collection of data elements where the linear node is given by means of pointer is called?

What is the time complexity of deleting from the rear end of the dequeue implemented with a singly linked list?

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

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?

What is the time complexity to insert a node based on position in a priority queue?

What are the disadvantages of arrays?

Given an array of size n, let's assume an element is ‘touched' if and only if some operation is performed on it(for example, for performing a pop operation the top element is ‘touched'). Now you need to perform Dequeue operation. Each element in the array is touched atleast?

The postfix form of the expression (A+ B)*(C*D- E)*F / G is?

Minimum number of queues to implement stack is ___________

Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

Convert the following infix expressions into its equivalent postfix expressions(A + B ⋀D)/(E – F)+G

You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?

The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is?

The data structure required to check whether an expression contains balanced parenthesis is?

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?

What kind of linked list is best to answer question like “What is the item at position n?”

The essential condition which is checked before deletion in a linked queue is?

What would be the asymptotic time complexity to find an element in the linked list?

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 number of elements present in stack are

Assume that the operators +,-, X are left associative and ^ is right associative.The order of precedence (from highest to lowest) is ^, X, +, -. The postfix expression for the infix expression a + b X c – d ^ e ^ f is

The prefix form of an infix expression p + q – r * t is?

Which of these is an application of linked lists?

Queues serve major role in

What is the value of the postfix expression 6 3 2 4 + – *:

Which of the following is true about linked list implementation of queue?

Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?

What is a memory efficient double linked list?

Consider you have a stack whose elements in it are as follows.5 4 3 2 << topWhere the top element is 2.You need to get the following stack6 5 4 3 2 << topThe operations that needed to be performed are (You can perform only push and pop):

How do you calculate the pointer difference in a memory efficient double linked list?

Which data structure is used for implementing recursion?

Which data structure is needed to convert infix notation to postfix notation?

Consider a small circular linked list. How to detect the presence of cycles in this list effectively?

Which of the following array position will be occupied by a new element being pushed for a stack of size N elements(capacity of stack > N).

The postfix form of A*B+C/D is?

Which of the following data structures can be used for parentheses matching?

What does ‘stack underflow' refer to?

Convert the following Infix expression to Postfix form using a stackx + y * z + (p * q + r) * s, Follow usual precedence rule and assume that the expression is legal.

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?

What is the space complexity for deleting a linked list?

What are the advantages of priority queues?

Which of the following concepts make extensive use of arrays?

If the elements “A”, “B”, “C” and “D” are placed in a stack and are deleted one at a time, what is the order of removal?

Which of the following array element will return the top-of-the-stack-element for a stack of size N elements(capacity of stack > N).

Given only a single array of size 10 and no other memory is available. Which of the following operation is not feasible to implement (Given only push and pop operation)?

The postfix form of the expression (A+ B)(CD- E)*F / G is?

The result of evaluating the postfix expression 5, 4, 6, +, , 4, 9, 3, /, +, is?

Here is an infix expression: 4 + 3(63-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?