Data Structure and Algorithms (DSA) MCQs (Multiple-Choice Questions)

1. What is the worst-case time complexity?

1. Minimum time required for program execution
2. Average time required for program execution
3. Maximum time required for program execution
4. None of the above

Answer: C) Maximum time required for program execution

Explanation:

Time complexity of a program represents the time required for a program to run to completion. Worst case time complexity is the maximum time required for program execution.

Discuss this question

2. What is the best-case time complexity?

1. Minimum time required for program execution
2. Average time required for program execution
3. Maximum time required for program execution
4. None of the above

Answer: A) Minimum time required for program execution

Explanation:

Time complexity of a program represents the time required for a program to run to completion. Best case time complexity is the minimum time required for program execution.

Discuss this question

3. Which of the following correctly defines the worst-case time complexity of Linear Search Algorithm?

1. O(n)
2. O(1)
3. O(nlogn)
4. O(n2)

Answer: A) O(n)

Explanation:

Linear Search, searches an element sequentially in a list. In the worst case, where an element is not present, the linear search algorithm has to scan all elements leading to O(n).

Discuss this question

4. Which of the following data structures is used for breadth first traversal of a graph?

1. Stack
2. Graph
3. Queue
4. Tree

Answer: C) Queue

Explanation:

For breadth first traversal of a graph, queue is used whereas for depth first traversal of a graph, stack is used.

Discuss this question

5. Which of the following data structures is used for depth first traversal of a graph?

1. Stack
2. Graph
3. Queue
4. Tree

Answer: A) Stack

Explanation:

For breadth first traversal of a graph, queue is used whereas for depth first traversal of a graph, stack is used.

Discuss this question

6. The below formula is used by which tree?

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

1. Red Black Tree
2. AVL Tree
3. Binary Search Tree
4. B+ Tree

Answer: A) Red Black Tree

Explanation:

In Binary Search tree, nodes exhibit the following properties:

• Value of left tree node is less than the root node
• Value of root tree node is greater or more than the root node

Discuss this question

7. What is the minimum number of spanning tree(s) in a connected graph?

1. 1
2. n
3. nxn
4. 0

Answer: A) 1

Explanation:

Every connected graph must have at least one spanning tree.

Discuss this question

8. How to find if two vertices A and B of a graph have a path in between them?

1. Using Breadth First Search, BFS
2. Using Depth First Search, DFS
3. Both of the above
4. None of the above

Answer: C) Both of the above

Explanation:

Both BFS and DFS, we can find if two vertices A and B have a path in between them.

Discuss this question

9. What is the time required to merge two sorted lists of size m and n respectively?

1. O(m)
2. O(n)
3. O(m + n)
4. None of the above

Answer: C) O(m + n)

Explanation:

Time required to merge two sorted lists of size m and n is O(m+n).

Discuss this question

10. Queue can be used for?

1. Parsing expression
2. Recursion
3. Resource Allocation
4. None of the above

Answer: C) Resource Allocation

Explanation:

Queue is generally used for limited resources allocation. Stack is used for other operations.

Discuss this question

11. Stack can be used for?

1. Parsing expression
2. Recursion
3. Function Calls Implementation
4. All of the above

Answer: D) All of the above

Explanation:

Stack is an important data structure in computer science and it is used in multiple areas including

• Parsing regular expressions
• Memory management
• Recursive function calls
• Function calls management
• String reversal
• And many more

Discuss this question

12. Which of the following sorting algorithms is using pivot to partition unsorted lists?

1. Insertion Sort
2. Quick Sort
3. Merge Sort
4. Bubble Sort

Answer: B) Quick Sort

Explanation:

Quick Sort algorithm uses a pivot element to partition an array and then call itself recursively twice to sort the resultant sub-arrays.

Discuss this question

13. Which of the following conditions is required to be met for interpolation search to work?

1. Collection should be in sorted form and equally distributed
2. Collection should not be in sorted form but should be equally distributed
3. Collection should not be equally distributed but should be sorted form
4. None of the above

Answer: A) Collection should be in sorted form and equally distributed

Explanation:

Interpolation search is a variant of binary search. Data collection should be sorted and equally distributed for interpolation search to work correctly.

Discuss this question

14. Which of the following algorithmic approaches focuses on achieving a localized optimum solution?

1. Divide and Conquer Approach
2. Greedy Approach
3. Dynamic Approach
4. All of the above

Answer: B) Greedy Approach

Explanation:

Greedy approach focus is to achieve a local optimum solution.

Discuss this question

15. Quick Sort is based on?

1. Divide and Conquer Approach
2. Greedy Approach
3. Improved Binary Search
4. None of the above

Answer: A) Divide and Conquer Approach

Explanation:

Binary Search algorithm uses divide and conquer approach. It divides the collection using a pivot and then sorts the two sub collections recursively.

Discuss this question

16. Tree traversal is generally easier than graph traversal, because?

1. Tree have roots
2. Trees are connected
3. Graphs may have loops
4. None of the above

Answer: A) Tree have roots

Explanation:

Tree traversal is easier as they have roots and don't have loops.

Discuss this question

17. Which of the following asymptotic notations is the worst among all?

1. O(n)
2. O(1)
3. O(n^3)
4. O(2n)

Answer: C) O(n^3)

Explanation:

• O(n³) being cubic is the worst one.  
• O(n) is dependent on n.
• O(1) is constant.
• O(2n) is dependent on n but O(n) is better.

Discuss this question

18. Which of the following asymptotic notations is the best among all?

1. O(n)
2. O(1)
3. O(n^3)
4. O(2n)

Answer: B) O(1)

Explanation:

• O(n³) being cubic is the worst one.  
• O(n) is dependent on n.
• O(1) is constant and is the best one.
• O(2n) is dependent on n but O(n) is better.

Discuss this question

19. Which of the following replaces the root in deletion operation of max heap?

1. Next value of left subtree
2. Next value of right subtree
3. Any random value of tree
4. Last element of last level

Answer: D) Last element of last level

Explanation:

Root level is always replaced by the last element of the last level regardless of max heap or min heap deletion operation.

Discuss this question

20. Which of the following replaces the root in deletion operation of min heap?

1. Next value of left subtree
2. Next value of right subtree
3. Any random value of tree
4. Last element of last level

Answer: D) Last element of last level

Explanation:

Root level is always replaced by the last element of the last level regardless of max heap or min heap deletion operation.

Discuss this question

21. Which of the following data structures can be used to check if an expression has matching parenthesis or not?

1. Tree
2. Queue
3. Stack
4. Linkedlist

Answer: C) Stack

Explanation:

Stack. As stack is using the LIFO (Last In First Out) approach, it is best suited to find matching parenthesis.

Discuss this question

22. How many edges are required to make a cyclic graph of n vertices?

1. n-1
2. 2n
3. n
4. n+1

Answer: C) n

Explanation:

To create a cycle graph, edges must be more or the same as the number of vertices.

Discuss this question

23. Which of the following exhibits the search efficiency of O(1)?

1. Stack
2. Queue
3. Hashtable
4. Heap

Answer: C) Hashtable

Explanation:

Hashtable has the capability of O(1) time complexity.

Discuss this question

24. How many moves are required as minimum to solve the Tower of Hanoi problem?

1. n
2. 2n
3. 2n-1
4. 2^n-1

Answer: D) 2^n-1

Explanation:

Considering n as the number of disks, 2ⁿ-1 are the minimum number of moves required to solve the Tower of Hanoi problem. For example, in the case of 3 disks, minimum 2³-1 = 7 moves are required to solve the Tower of Hanoi problem.

Discuss this question

25. Which of the following correctly defines the Tower of Hanoi problem?

1. Divide and Conquer
2. Recursive
3. Both of the above
4. None of the above

Answer: C) Both of the above

Explanation:

Recursive approach solution of Tower of Hanoi uses divide and Conquer.

Discuss this question

26. Which of the following search algorithms does not require collection to be sorted first?

1. Linear Search
2. Interpolation Search
3. Binary Search
4. None of the above

Answer: A) Linear Search

Explanation:

Interpolation and Binary Search both require data to be sorted first. Linear search can work with unsorted data.

Discuss this question