Topic in Data Structures & Algorithms
A data structure organises data in memory for efficient access and change, while an algorithm is a finite sequence of steps that solves a problem. Foundational MCQs check that you can separate an abstract data type from its implementation, tell primitive types from composite ones, and read asymptotic notation correctly: Big-O as an upper bound, Omega as a lower bound and Theta as a tight bound. Common tasks include simplifying expressions like 3n^2 + 5n + 7 to O(n^2), ranking growth rates such as O(2^n) against O(n^3), counting nested-loop iterations, and analysing recursion with tail calls, recursion trees and simple recurrences.
Below are 30 practice questions from a pool of 210 Foundations of DS & Algorithms MCQs, one of 12 topics in Data Structures & Algorithms. Each shows the correct answer with an explanation; when you are ready, take a timed quiz to test recall under exam conditions.
Each question below shows the correct answer with a full explanation. Use these to build conceptual understanding before attempting a timed quiz.
Q1. What is a data structure?
A data structure is a way to organize, manage, and store data so that it can be accessed and modified efficiently.
Q2. What does 'algorithm' mean?
An algorithm is a finite set of well-defined instructions or steps to solve a specific problem or perform a computation.
Q3. Which notation is used to describe the upper bound of an algorithm's time complexity?
Big-O notation describes the upper bound (worst case) of an algorithm's growth rate.
Q4. What is the time complexity of accessing an element in an array by index?
Array elements can be accessed directly using their index in constant time O(1).
Q5. Which of the following is a linear data structure?
An array is a linear data structure where elements are stored in contiguous memory locations.
Q6. What is the purpose of pseudocode?
Pseudocode is used to represent an algorithm in a structured, human-readable format without worrying about syntax of a specific language.
Q7. Which term refers to the amount of memory an algorithm uses?
Space complexity measures the total amount of memory space required by an algorithm as a function of input size.
Q8. What is O(1) complexity called?
O(1) is called constant time complexity because the execution time does not change with input size.
Q9. Which of the following is a non-linear data structure?
A tree is a non-linear data structure where elements are arranged in a hierarchical manner.
Q10. What is an Abstract Data Type (ADT)?
An ADT is a mathematical model that defines a data type by its behavior (operations) rather than its implementation.
Q11. What is the time complexity of the recurrence T(n) = 2T(n/2) + n?
By the Master Theorem (case 2), T(n) = 2T(n/2) + n gives O(n log n).
Q12. Which case of the Master Theorem applies when f(n) = Θ(n^(log_b(a)))?
Case 2 of the Master Theorem applies when f(n) = Θ(n^(log_b(a))), giving T(n) = Θ(n^(log_b(a)) * log n).
Q13. What does Omega (Ω) notation represent?
Omega notation provides an asymptotic lower bound on the growth rate of an algorithm.
Q14. If an algorithm has complexities O(n^2) in the worst case and Ω(n) in the best case, which is true?
The algorithm's performance ranges from the lower bound Ω(n) in the best case to the upper bound O(n^2) in the worst case.
Q15. What is amortized analysis?
Amortized analysis averages the time required to perform a sequence of operations, giving a tighter bound than worst-case per operation.
Q16. Which growth rate is faster: O(2^n) or O(n^3)?
Exponential growth O(2^n) grows much faster than polynomial growth O(n^3) for large n.
Q17. What is the time complexity of a nested loop where both loops run n times?
Two nested loops each running n times result in n × n = n^2 iterations, giving O(n^2).
Q18. In asymptotic analysis, which of these is the correct ordering from slowest to fastest growth?
The correct growth order is: O(1) < O(log n) < O(n) < O(n^2).
Q19. What is the recurrence relation for binary search?
Binary search divides the problem in half each time and does constant work, giving T(n) = T(n/2) + 1.
Q20. What does Theta (Θ) notation represent?
Theta notation provides a tight bound, meaning the function grows at the same rate asymptotically (both upper and lower bounds match).
Q21. What is the time complexity of the recurrence T(n) = 3T(n/4) + n log n?
Using Master Theorem case 3: log_4(3) ≈ 0.79 < 1, and f(n) = n log n = Ω(n^(0.79+ε)), so T(n) = Θ(n log n).
Q22. Which of the following recurrences cannot be solved by the Master Theorem?
T(n) = T(n-1) + n is not in the form T(n) = aT(n/b) + f(n) required by the Master Theorem, as it subtracts rather than divides.
Q23. What is the amortized cost of insertion in a dynamic array that doubles its size when full?
Although occasional resizing costs O(n), the amortized cost over n insertions is O(1) per insertion using aggregate analysis.
Q24. Using the substitution method, what is the solution to T(n) = T(n-1) + n with T(1) = 1?
Expanding: T(n) = n + (n-1) + ... + 1 = n(n+1)/2 = O(n^2).
Q25. What is the lower bound for any comparison-based sorting algorithm?
Any comparison-based sorting algorithm requires at least Ω(n log n) comparisons in the worst case, proven via decision tree analysis.
Q26. In the potential method of amortized analysis, the amortized cost is defined as:
In the potential method, amortized cost = actual cost + (Φ(after) - Φ(before)), where Φ is the potential function.
Q27. What complexity class does the problem of finding the median of an unsorted array belong to?
The median can be found in O(n) worst-case time using the median-of-medians deterministic selection algorithm.
Q28. What is the space complexity of a recursive algorithm with depth d and O(1) space per call?
Each recursive call adds a frame to the call stack. With depth d and O(1) per frame, total space is O(d).
Q29. Which of the following is true about the relationship between time and space complexity?
An algorithm cannot use more space than time, because writing to each memory cell takes at least one time step. So space ≤ time.
Q30. What is the time complexity of T(n) = 2T(n/2) + n/log n?
This recurrence falls in a gap of the Master Theorem. Using the Akra-Bazzi method or recursion tree, T(n) = O(n log log n).
Take a timed quiz drawn from 210+ questions on this topic. No signup required — your progress saves in your browser.
Start Foundations of DS & Algorithms Quiz