Introduction
Data Structures and Algorithms (DSA) form the backbone of computer science. A data structure decides how information is organized in memory, while an algorithm defines the step-by-step method used to process it. Together they determine whether a program is fast or slow, scalable or fragile. Every major software system, from search engines and operating systems to banking applications and mobile apps, depends on well-chosen data structures and efficient algorithms.
For students in Pakistan, DSA is a high-weightage subject in PPSC, FPSC, NTS, and Lecturer Computer Science examinations, as well as university entry tests and postgraduate admissions. Technical interviews at software houses and multinational companies also rely heavily on DSA to test logical thinking and problem-solving ability.
This article presents 50 carefully selected, high-yield Data Structures and Algorithms MCQs with answers and clear explanations. The questions are divided into four sections: Linear Data Structures, Non-Linear Data Structures, Sorting, Searching and Algorithmic Techniques, and Algorithmic Complexity. This first part covers Questions 1 to 25. Read each explanation carefully, because understanding the concept matters more than memorizing the option.
Section 1: Linear Data Structures (Arrays, Linked Lists, Stacks, Queues)
Q1. Which data structure follows the LIFO (Last In, First Out) principle?
(A) Queue (B) Stack (C) Array (D) Linked List
Correct Answer: (B) Stack
Explanation: In a stack, insertion and deletion both take place at one end, called the top. The element pushed last is therefore the first one to be popped, which is the LIFO rule. Function call management and undo operations are common applications.
Q2. What is the time complexity of accessing an element in an array by its index?
(A) O(n) (B) O(log n) (C) O(1) (D) O(n log n)
Correct Answer: (C) O(1)
Explanation: Arrays store elements in contiguous memory locations, so the address of any element is computed directly from the base address and the index. This makes random access a constant-time operation regardless of array size.
Q3. Which of the following is NOT a linear data structure?
(A) Array (B) Linked List (C) Queue (D) Binary Tree
Correct Answer: (D) Binary Tree
Explanation: In linear data structures, elements are arranged sequentially, with each element having at most one predecessor and one successor. A binary tree is hierarchical, since a node can have two children, so it is classified as a non-linear data structure.
Q4. What is the time complexity of inserting a new node at the beginning of a singly linked list (when the head pointer is available)?
(A) O(1) (B) O(n) (C) O(log n) (D) O(n²)
Correct Answer: (A) O(1)
Explanation: To insert at the beginning, we create a new node, point its next pointer to the current head, and update the head to the new node. No traversal is needed, so the operation takes constant time.
Q5. Which operation is used to add an element to a stack?
(A) Enqueue (B) Insert (C) Push (D) Append
Correct Answer: (C) Push
Explanation: Push places a new element on the top of the stack, while pop removes the top element. Enqueue is the corresponding insertion operation for a queue, not for a stack.
Q6. A queue works on which principle?
(A) LIFO (B) FIFO (C) LILO with priority (D) Random access
Correct Answer: (B) FIFO
Explanation: A queue inserts elements at the rear and removes them from the front, so the element that arrived first is served first. This is the First In, First Out principle, similar to a line of people at a ticket counter.
Q7. What is the result of evaluating the postfix expression 5 3 + 2 *?
(A) 13 (B) 15 (C) 10 (D) 16
Correct Answer: (D) 16
Explanation: Scanning left to right with a stack, 5 and 3 are pushed, then + pops both and pushes 8. Next, 2 is pushed and * multiplies 8 by 2, giving 16. The equivalent infix expression is (5 + 3) * 2.
Q8. Which data structure is typically used to convert an infix expression to postfix?
(A) Stack (B) Queue (C) Binary Tree (D) Hash Table
Correct Answer: (A) Stack
Explanation: The standard conversion algorithm uses a stack to temporarily hold operators and parentheses so that operator precedence and associativity are respected. Operands go directly to the output, while operators are popped according to their precedence.
Q9. What is the main advantage of a circular queue over a simple (linear) queue?
(A) It is faster for searching (B) It uses less memory per element (C) It reuses empty space freed by dequeued elements (D) It allows insertion at both ends
Correct Answer: (C) It reuses empty space freed by dequeued elements
Explanation: In a simple array-based queue, space at the front stays unused after elements are removed, even when the rear reaches the end. A circular queue wraps the rear back to the beginning, so the unused slots are reused and memory is utilized efficiently.
Q10. What is the main advantage of a linked list over an array?
(A) Faster random access (B) Dynamic size and efficient insertion/deletion (C) Less memory usage per element (D) Better cache performance
Correct Answer: (B) Dynamic size and efficient insertion/deletion
Explanation: A linked list grows and shrinks at run time, and inserting or deleting a node only requires changing pointers, without shifting elements. Arrays offer faster random access and better cache locality, but they have a fixed size and costly shifting.
Q11. What is the postfix form of the infix expression A + B * C?
(A) ABC*+ (B) AB+C* (C) ABC+* (D) +A*BC
Correct Answer: (A) ABC*+
Explanation: Multiplication has higher precedence than addition, so B * C is converted first to BC*. Then A is combined with that result using +, giving ABC*+. Option (B) would represent (A + B) * C.
Q12. A stack overflow condition occurs when:
(A) A pop operation is applied to an empty stack (B) The stack contains only one element (C) The top pointer is at the middle position (D) A push operation is applied to a full stack
Correct Answer: (D) A push operation is applied to a full stack
Explanation: Overflow means there is no space left to insert a new element. Trying to pop from an empty stack is called underflow, which is the opposite condition. In recursion, overflow often happens when the call depth becomes too large.
Q13. Which data structure is used to implement Breadth-First Search (BFS) of a graph?
(A) Stack (B) Binary Heap (C) Queue (D) Hash Table
Correct Answer: (C) Queue
Explanation: BFS explores all neighbours of a vertex before moving to the next level. A queue’s FIFO order ensures vertices are processed in the order they are discovered, which gives level-by-level traversal.
Q14. Each node of a doubly linked list contains:
(A) Data and one pointer to the next node (B) Data, a pointer to the previous node, and a pointer to the next node (C) Only two data fields (D) Data and a pointer to the head node
Correct Answer: (B) Data, a pointer to the previous node, and a pointer to the next node
Explanation: The extra previous pointer allows traversal in both directions and makes deletion of a given node easier. The trade-off is additional memory for the second pointer in every node.
Q15. A Deque (double-ended queue) allows:
(A) Insertion and deletion at both the front and the rear (B) Insertion only at the front (C) Deletion only at the rear (D) Insertion in the middle only
Correct Answer: (A) Insertion and deletion at both the front and the rear
Explanation: A deque generalizes both stack and queue, because elements can be added or removed from either end. Depending on how it is used, it can behave as a stack, a queue, or a sliding-window structure.
Section 2: Non-Linear Data Structures (Trees, Binary Search Trees, Graphs, Heaps)
Q16. In a binary tree, what is the maximum number of nodes at level l (taking the root at level 0)?
(A) 2l (B) 2^l (C) l² (D) 2l − 1
Correct Answer: (B) 2^l
Explanation: Each node can have at most two children, so the number of possible nodes doubles at every level. Level 0 has 1 node, level 1 has 2, level 2 has 4, and so on, giving 2^l nodes at level l.
Q17. What does the inorder traversal of a Binary Search Tree (BST) produce?
(A) Elements in descending order (B) Elements in level order (C) Elements in ascending (sorted) order (D) Elements in random order
Correct Answer: (C) Elements in ascending (sorted) order
Explanation: In a BST, every key in the left subtree is smaller than the root and every key in the right subtree is larger. Inorder traversal visits Left, Root, Right, so the keys are visited from smallest to largest.
Q18. What is the maximum number of nodes in a binary tree of height h (taking the height of a single root node as 0)?
(A) 2^(h+1) − 1 (B) 2^h (C) 2^h − 1 (D) 2h + 1
Correct Answer: (A) 2^(h+1) − 1
Explanation: A tree is largest when every level is completely filled. Summing 1 + 2 + 4 + … + 2^h gives 2^(h+1) − 1. If height is counted in levels starting at 1, the same formula becomes 2^h − 1, so always check the convention used in the question.
Q19. Which of the following represents the preorder traversal sequence?
(A) Left, Root, Right (B) Left, Right, Root (C) Right, Root, Left (D) Root, Left, Right
Correct Answer: (D) Root, Left, Right
Explanation: Preorder visits the root first, then recursively traverses the left subtree, and finally the right subtree. Option (A) is inorder and option (B) is postorder. Preorder is useful for copying a tree or producing prefix expressions.
Q20. What is the worst-case time complexity of searching in a BST with n nodes?
(A) O(1) (B) O(log n) (C) O(n) (D) O(n log n)
Correct Answer: (C) O(n)
Explanation: If keys are inserted in sorted order, the BST degenerates into a skewed tree that looks like a linked list. Searching then requires visiting up to n nodes. A balanced BST such as an AVL tree guarantees O(log n).
Q21. In a Min-Heap, the root node contains:
(A) The largest element (B) The smallest element (C) The median element (D) Any random element
Correct Answer: (B) The smallest element
Explanation: A min-heap is a complete binary tree where every parent is less than or equal to its children. By this property, the smallest value always sits at the root. Min-heaps are widely used to implement priority queues and in Dijkstra’s algorithm.
Q22. What is the maximum number of edges in a simple undirected graph with n vertices (no self-loops or multiple edges)?
(A) n(n − 1)/2 (B) n² (C) n(n + 1)/2 (D) n − 1
Correct Answer: (A) n(n − 1)/2
Explanation: In a complete undirected graph, every vertex connects to all other n − 1 vertices. Since each edge is counted twice in this approach, we divide by 2, giving n(n − 1)/2 edges.
Q23. Which data structure is commonly used to implement Depth-First Search (DFS)?
(A) Queue (B) Priority Queue (C) Array of pointers (D) Stack
Correct Answer: (D) Stack
Explanation: DFS goes as deep as possible along a path before backtracking. A stack, either an explicit one or the system call stack used in recursion, naturally supports this last-in, first-out backtracking behaviour.
Q24. In a full binary tree where every node has either 0 or 2 children, if there are n internal nodes, how many leaf nodes are there?
(A) n (B) n − 1 (C) n + 1 (D) 2n
Correct Answer: (C) n + 1
Explanation: In a full binary tree, the number of leaves is always one more than the number of internal nodes. For example, a tree with 1 internal node (the root) has 2 leaves, and a tree with 3 internal nodes has 4 leaves.
Q25. In an AVL tree, the allowed values of the balance factor of any node are:
(A) 0, 1, 2 (B) −1, 0, 1 (C) −2, −1, 0 (D) Any integer
Correct Answer: (B) −1, 0, 1
Explanation: The balance factor is the height of the left subtree minus the height of the right subtree. An AVL tree keeps this difference within one for every node, using rotations after insertion or deletion, which guarantees O(log n) search, insert, and delete.
Data Structures and Algorithms MCQs (Part 2: Questions 26 to 50)
Section 3: Sorting, Searching & Algorithmic Techniques
Q26. What is the worst-case time complexity of Quick Sort?
(A) $O(n \log n)$
(B) $O(n^2)$
(C) $O(n)$
(D) $O(\log n)$
Correct Answer: (B) $O(n^2)$
Explanation: Quick Sort takes $O(n^2)$ time in the worst case when the chosen pivot is consistently the extreme element (e.g., already sorted array with poor pivot selection). On average, its time complexity is $O(n \log n)$.
Q27. Which sorting algorithm operates on the Divide and Conquer strategy and always guarantees $O(n \log n)$ worst-case time complexity?
(A) Bubble Sort
(B) Insertion Sort
(C) Merge Sort
(D) Selection Sort
Correct Answer: (C) Merge Sort
Explanation: Merge Sort recursively divides the array into two halves, sorts them, and merges them back. Its performance remains $O(n \log n)$ in best, average, and worst cases at the cost of $O(n)$ extra space.
Q28. What prerequisite must be met before applying Binary Search on an array?
(A) Array must be stored in a linked list
(B) Array elements must be sorted
(C) Array size must be a power of 2
(D) Array must not contain duplicate values
Correct Answer: (B) Array elements must be sorted
Explanation: Binary Search compares the target value to the middle element and eliminates half of the remaining elements in each step. This decision depends entirely on elements being in sorted order.
Q29. What is the time complexity of Binary Search on a sorted array of size $n$?
(A) $O(1)$
(B) $O(n)$
(C) $O(\log n)$
(D) $O(n \log n)$
Correct Answer: (C) $O(\log n)$
Explanation: Since the search space is halved at every comparison, the total number of operations required is logarithmic relative to the input size $n$.
Q30. Which sorting algorithm is stable and has a best-case time complexity of $O(n)$ when the array is already sorted?
(A) Selection Sort
(B) Quick Sort
(C) Heap Sort
(D) Insertion Sort
Correct Answer: (D) Insertion Sort
Explanation: Insertion Sort iterates through the list and places each item in its correct relative position. If the list is already sorted, it makes only $n – 1$ comparisons without shifting elements, giving an $O(n)$ best case.
Q31. Linear Search requires how many comparisons in the worst case for an array of $n$ elements?
(A) $1$
(B) $\log_2 n$
(C) $n$
(D) $n / 2$
Correct Answer: (C) $n$
Explanation: In Linear Search, if the target element is at the very end of the array or not present at all, every element must be checked once, resulting in $n$ comparisons or $O(n)$ time complexity.
Q32. Which technique stores the results of expensive function calls to reuse them when the same inputs occur again?
(A) Greedy Approach
(B) Backtracking
(C) Memoization (Dynamic Programming)
(D) Divide and Conquer
Correct Answer: (C) Memoization (Dynamic Programming)
Explanation: Memoization is a top-down dynamic programming technique where subproblem solutions are cached in a lookup table so they do not need to be recomputed.
Q33. What is the key characteristic of a Greedy Algorithm?
(A) It checks all possible solutions to find the global optimum
(B) It makes the locally optimal choice at each step hoping to find the global optimum
(C) It works backwards from the final goal
(D) It requires backtracking when a bad path is chosen
Correct Answer: (B) It makes the locally optimal choice at each step hoping to find the global optimum
Explanation: Greedy algorithms prioritize immediate benefits at each decision point without reconsidering previous steps or evaluating future consequences (e.g., Prim’s algorithm, Kruskal’s algorithm, Fractional Knapsack).
Q34. Which sorting algorithm repeatedly selects the minimum element from the unsorted sublist and moves it to the sorted sublist?
(A) Bubble Sort
(B) Selection Sort
(C) Merge Sort
(D) Quick Sort
Correct Answer: (B) Selection Sort
Explanation: Selection Sort maintains a sorted part and an unsorted part. In each pass, it finds the smallest element in the unsorted region and swaps it with the first unsorted element.
Q35. What is the spatial complexity (auxiliary space) required by Merge Sort?
(A) $O(1)$
(B) $O(\log n)$
(C) $O(n)$
(D) $O(n^2)$
Correct Answer: (C) $O(n)$
Explanation: Merge Sort requires an extra auxiliary array of size $n$ to temporary store and merge elements during the combine step.
Q36. Which algorithmic technique is used in solving the N-Queens problem and Sudoku?
(A) Dynamic Programming
(B) Greedy Algorithm
(C) Backtracking
(D) Branch and Bound
Correct Answer: (C) Backtracking
Explanation: Backtracking builds candidates for solutions incrementally and abandons (“backtracks”) a candidate as soon as it determines the candidate cannot lead to a valid full solution.
Q37. What is the average time complexity of searching for an element in a Hash Table?
(A) $O(1)$
(B) $O(\log n)$
(C) $O(n)$
(D) $O(n \log n)$
Correct Answer: (A) $O(1)$
Explanation: Hash tables compute the index directly using a hash function, allowing constant-time $O(1)$ average performance for lookups, insertions, and deletions.
Q38. What occurs when two different keys generate the same hash value in a hash table?
(A) Hash Overflow
(B) Hash Collision
(C) Hash Underflow
(D) Null Pointer Exception
Correct Answer: (B) Hash Collision
Explanation: A collision happens when a hash function maps two distinct keys to the exact same index. Techniques like Chaining (Open Hashing) and Open Addressing (Linear Probing) are used to handle collisions.
Q39. Which algorithm is used to find the Shortest Path from a single source node to all other nodes in a weighted graph with non-negative edge weights?
(A) Prim’s Algorithm
(B) Kruskal’s Algorithm
(C) Dijkstra’s Algorithm
(D) Floyd-Warshall Algorithm
Correct Answer: (C) Dijkstra’s Algorithm
Explanation: Dijkstra’s algorithm uses a greedy approach (often implemented with a Min-Heap) to calculate the shortest path tree from a starting vertex to all other vertices in a graph with non-negative edge weights.
Q40. Kruskal’s and Prim’s algorithms are used to find:
(A) Single-source shortest path
(B) All-pairs shortest path
(C) Minimum Spanning Tree (MST)
(D) Topological sort of a graph
Correct Answer: (C) Minimum Spanning Tree (MST)
Explanation: Both Prim’s and Kruskal’s algorithms find a Minimum Spanning Tree (MST) for a connected, edge-weighted undirected graph, connecting all vertices with the minimum total edge weight without creating cycles.
Section 4: Algorithmic Complexity (Big O Notation)
Q41. What does Big O notation describe in algorithm analysis?
(A) Exact execution time in seconds
(B) Best-case execution behavior
(C) Upper bound on time or space complexity (Worst-case behavior)
(D) Average memory consumption on a specific CPU
Correct Answer: (C) Upper bound on time or space complexity (Worst-case behavior)
Explanation: Big O notation represents asymptotic upper bounds, providing a theoretical ceiling on how time or space requirements grow as input size $n$ increases toward infinity.
Q42. Which of the following time complexities grows the FASTEAST as input size $n$ increases?
(A) $O(n \log n)$
(B) $O(n^2)$
(C) $O(2^n)$
(D) $O(n^3)$
Correct Answer: (C) $O(2^n)$
Explanation: Exponential growth $O(2^n)$ grows significantly faster than polynomial growth ($O(n^2)$, $O(n^3)$) or logarithmic growth ($O(n \log n)$), making algorithms with exponential time complexity impractical for large inputs.
Q43. Which asymptotic notation represents the tight bound (both lower and upper bound) of an algorithm?
(A) Big O ($\mathcal{O}$)
(B) Big Omega ($\Omega$)
(C) Big Theta ($\Theta$)
(D) Little o ($o$)
Correct Answer: (C) Big Theta ($\Theta$)
Explanation: Big Theta ($\Theta$) bounds a function from above and below within constant factors, defining the exact rate of growth or tight bound of an algorithm.
Q44. What is the time complexity of printing all pairs of elements from an array of size $n$ using nested loops?
(A) $O(n)$
(B) $O(n \log n)$
(C) $O(n^2)$
(D) $O(2^n)$
Correct Answer: (C) $O(n^2)$
Explanation: Two nested loops, each running from $0$ to $n-1$, execute the inner statement $n \times n = n^2$ times, leading to a quadratic time complexity of $O(n^2)$.
Q45. An algorithm that halves the input size in each step (like Binary Search) typically has a time complexity of:
(A) $O(1)$
(B) $O(\log n)$
(C) $O(n)$
(D) $O(n^2)$
Correct Answer: (B) $O(\log n)$
Explanation: Repeated division of problem size by a constant factor (e.g., dividing by 2) reduces the problem to base size in $\log_2 n$ steps, resulting in logarithmic time complexity.
Q46. What is the time complexity of calculating the Fibonacci number using simple recursive functions without memoization?
(A) $O(n)$
(B) $O(n^2)$
(C) $O(2^n)$
(D) $O(\log n)$
Correct Answer: (C) $O(2^n)$
Explanation: Naive recursive Fibonacci creates a binary call tree where each call spawns two more calls $F(n-1) + F(n-2)$, causing the number of operations to grow exponentially as $O(2^n)$.
Q47. If an algorithm takes constant time regardless of the size of the input, its time complexity is expressed as:
(A) $O(1)$
(B) $O(n)$
(C) $O(0)$
(D) $O(\log n)$
Correct Answer: (A) $O(1)$
Explanation: $O(1)$ or constant time complexity means the execution time remains fixed and independent of the input size $n$ (e.g., pushing to a stack, array index access).
Q48. Arranging the following growth rates from SMALLEST to LARGEST:
$$O(1), O(\log n), O(n), O(n \log n), O(n^2)$$
(A) $O(1) < O(n) < O(\log n) < O(n \log n) < O(n^2)$
(B) $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2)$
(C) $O(\log n) < O(1) < O(n) < O(n^2) < O(n \log n)$
(D) $O(1) < O(\log n) < O(n \log n) < O(n) < O(n^2)$
Correct Answer: (B) $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2)$
Explanation: Constant $O(1)$ is the slowest growing (best), followed by Logarithmic $O(\log n)$, Linear $O(n)$, Linearithmic $O(n \log n)$, and Quadratic $O(n^2)$.
Q49. Master Theorem is used to determine the time complexity of:
(A) Iterative algorithms
(B) Divide and conquer recurrences
(C) Greedy graph algorithms
(D) Sorting algorithms only
Correct Answer: (B) Divide and conquer recurrences
Explanation: Master Theorem provides a direct asymptotic formula for recurrence relations of the form $T(n) = aT(n/b) + f(n)$ commonly found in divide-and-conquer algorithms like Merge Sort and Binary Search.
Q50. What is the space complexity of an iterative function that computes the sum of $n$ elements in an array using a single accumulator variable?
(A) $O(n)$
(B) $O(1)$
(C) $O(\log n)$
(D) $O(n^2)$
Correct Answer: (B) $O(1)$
Explanation: The function only uses a fixed amount of extra memory (one loop variable and one sum variable) regardless of the size of the input array $n$, making the space complexity $O(1)$.
Related Subject-wise MCQs: