Data Structure MCQ (Multiple Choice Questions)
1. Which data structure follows the Last-In-First-Out (LIFO) principle?
a) Queue
b) Stack
c) Linked List
d) Tree
Explanation: A stack follows the Last-In-First-Out (LIFO) principle, where the most recently added element is the first one to be removed, similar to a stack of plates.
2. In a queue, elements are added at the rear and removed from the front. This follows which principle?
a) LIFO
b) FIFO
c) Random Access
d) Priority Based
Explanation: Queues use the First-In-First-Out (FIFO) principle, ensuring the earliest added element is processed first, like people waiting in line.
3. What is the time complexity for accessing an element in an array by index?
a) O(n)
b) O(1)
c) O(log n)
d) O(n²)
Explanation: Arrays allow constant time O(1) access because elements are stored in contiguous memory locations, and the address can be calculated directly using the index.
4. Which data structure is best suited for implementing recursion?
a) Queue
b) Stack
c) Array
d) Graph
Explanation: Recursion relies on the call stack — a stack data structure — that manages function calls, parameters, and return addresses.
5. In a singly linked list, what does the ‘next’ pointer of the last node point to?
a) The first node
b) Itself
c) NULL
d) A random node
Explanation: The last node in a singly linked list has its ‘next’ pointer set to NULL to indicate the end of the list.
6. What is the primary advantage of a doubly linked list over a singly linked list?
a) Faster insertion at the beginning
b) Less memory usage
c) Traversal in both directions
d) Easier to implement
Explanation: Doubly linked lists maintain pointers to both the next and previous nodes, enabling efficient bidirectional traversal.
7. Which operation is used to remove an element from the top of a stack?
a) Push
b) Pop
c) Enqueue
d) Dequeue
Explanation: Pop removes and returns the element at the top of the stack while maintaining the LIFO order.
8. In a binary tree, what is the maximum number of children a node can have?
a) 1
b) 2
c) 3
d) Unlimited
Explanation: A binary tree is defined such that each node has at most two children (left and right).
9. What data structure is typically used to implement a priority queue?
a) Stack
b) Linked List
c) Heap
d) Array
Explanation: Binary heaps (min-heap or max-heap) provide efficient O(log n) insert and extract-min/max operations, making them ideal for priority queues.
10. In hashing, what is the term for when two keys map to the same index?
a) Overflow
b) Collision
c) Chaining
d) Probing
Explanation: Collision occurs when two or more distinct keys hash to the same array index in a hash table.
11. What is the time complexity of inserting an element at the end of a dynamic array when it is full?
a) O(1)
b) O(n)
c) O(log n)
d) O(1) amortized
Explanation: When the array is full, it must be resized (usually doubled) and all elements copied, which takes O(n) time in the worst case (though amortized complexity is O(1)).
12. In a circular queue, how is the rear pointer updated after enqueue?
a) Rear = Rear – 1
b) Rear = (Rear + 1) % Size
c) Rear = Front + 1
d) Rear = Size – 1
Explanation: The modulo operation allows the rear pointer to wrap around to the beginning when it reaches the end, implementing circular behavior.
13. Which traversal of a binary tree requires a stack for iterative implementation?
a) Inorder
b) Preorder
c) Postorder
d) All of the above
Explanation: All three depth-first traversals (inorder, preorder, postorder) can be implemented iteratively using an explicit stack to simulate the recursive call stack.
14. What is the minimum number of queues needed to implement a stack?
a) 1
b) 2
c) 3
d) 4
Explanation: Two queues can simulate stack behavior: one holds elements, the other is used temporarily to reverse order during push/pop operations.
15. In a graph, if there is a path from every vertex to every other vertex, it is called?
a) Directed
b) Undirected
c) Connected
d) Weighted
Explanation: A connected graph ensures there is at least one path between every pair of vertices.
16. What is the space complexity of an adjacency list for a graph with V vertices and E edges?
a) O(V)
b) O(E)
c) O(V + E)
d) O (V²)
Explanation: Adjacency lists store each vertex and a list of its adjacent vertices, requiring space proportional to vertices plus edges.
17. Which sorting algorithm is stable and has O(n log n) average time complexity?
a) Quick Sort
b) Heap Sort
c) Merge Sort
d) Bubble Sort
Explanation: Merge Sort is stable (preserves relative order of equal elements) and guarantees O(n log n) time in all cases.
18. In a binary search tree (BST), where are all elements in the left subtree?
a) Greater than root
b) Less than root
c) Equal to root
d) No restriction
Explanation: The BST property states that all nodes in the left subtree have values less than the root, and all in the right subtree have values greater.
19. What is the height of a balanced binary tree with n nodes?
a) O(n)
b) O(log n)
c) O(√n)
d) O(1)
Explanation: Balanced binary search trees (AVL, Red-Black) maintain height Θ(log n), ensuring efficient O(log n) operations.
20. Which data structure uses LIFO for undo operations in software?
a) Queue
b) Stack
c) Heap
d) Graph
Explanation: Undo functionality typically pushes previous states onto a stack and pops them when the user requests undo.
21. In open addressing hashing, what technique probes for the next slot linearly?
a) Chaining
b) Linear Probing
c) Quadratic Probing
d) Double Hashing
Explanation: Linear probing sequentially checks the next slot (index + 1, +2, etc.) until an empty slot is found.
22. What is the time complexity to find the minimum in a min-heap?
a) O(n)
b) O(log n)
c) O(1)
d) O(n log n)
Explanation: In a min-heap, the smallest element is always at the root, so it can be accessed in constant time.
23. In a deque, insertions and deletions can occur at?
a) One end only
b) Both ends
c) Middle
d) Random positions
Explanation: Deque (double-ended queue) supports efficient addition and removal from both the front and rear.
24. Which tree traversal outputs nodes in sorted order for a BST?
a) Preorder
b) Inorder
c) Postorder
d) Level order
Explanation: Inorder traversal of a BST visits nodes in ascending sorted order (left → root → right).
25. What is the worst-case time complexity for searching in a hash table?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Explanation: In the worst case (all keys hash to the same bucket), searching degenerates to a linear scan.
26. In an AVL tree, what is the balance factor?
a) Height of left – height of right
b) Height of left subtree – height of right subtree
c) Number of nodes in left – right
d) Depth of tree
Explanation: The balance factor is the difference in height between left and right subtrees and must be -1, 0, or 1 in an AVL tree.
27. Which graph traversal uses a queue?
a) DFS
b) BFS
c) Dijkstra
d) Prim
Explanation: Breadth-First Search (BFS) explores level by level and uses a queue to manage nodes at the current level.
28. What is the purpose of a sentinel node in linked lists?
a) To store data
b) To simplify boundary conditions
c) To point to NULL
d) To hold the tail
Explanation: Sentinel (dummy) nodes eliminate special cases for empty lists or operations at the head/tail.
29. In a complete binary tree, all levels are fully filled except possibly?
a) The root
b) The last level
c) The middle levels
d) No exceptions
Explanation: A complete binary tree fills all levels from left to right; only the last level may be partially filled.
30. Which operation rotates nodes in AVL trees to balance?
a) Insertion
b) Deletion
c) Rotation
d) Traversal
Explanation: Rotations (LL, RR, LR, RL) are performed to restore the AVL balance property after insertions or deletions.
31. What data structure represents a hierarchical relationship?
a) Array
b) Stack
c) Tree
d) Queue
Explanation: Trees naturally model hierarchical structures with parent-child relationships (e.g., file systems, organization charts).
32. In adjacency matrix for graphs, what does a 1 indicate?
a) No edge
b) Edge exists
c) Weight
d) Vertex count
Explanation: In an unweighted adjacency matrix, a value of 1 indicates the presence of an edge between two vertices.
33. Which is not a primitive data structure?
a) Integer
b) Float
c) Linked List
d) Char
Explanation: Primitive data types (int, float, char, etc.) are built-in; linked lists are composite/user-defined structures.
34. What is the time complexity of bubble sort in worst case?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(1)
Explanation: Bubble sort performs nested loops comparing and swapping adjacent elements, leading to quadratic time in the worst case.
35. In a max-heap, the parent is always?
a) Smaller than children
b) Greater than or equal to children
c) Equal to children
d) No relation
Explanation: The max-heap property ensures every parent node is greater than or equal to its children.
36. Which search requires a sorted array?
a) Linear
b) Binary
c) Hash
d) Interpolation
Explanation: Binary search relies on the sorted order to eliminate half the search space in each step.
37. What is a self-balancing binary search tree?
a) BST
b) Binary Tree
c) AVL Tree
d) Heap
Explanation: AVL trees automatically maintain balance (height difference ≤ 1) after insertions and deletions.
38. In a stack, underflow occurs when?
a) Pushing to full stack
b) Popping from empty stack
c) Overflow
d) Peeking
Explanation: Underflow is the error condition when attempting to remove an element from an already empty stack.
39. Which data structure is used for breadth-first traversal?
a) Stack
b) Queue
c) Heap
d) List
Explanation: BFS uses a queue to process nodes level by level (FIFO behavior matches level-order exploration).
40. What is the load factor in hashing?
a) Number of elements / size
b) Number of elements divided by table size
c) Collisions count
d) Probes
Explanation: Load factor = number of stored elements (n) / number of buckets (m); high load factor increases collisions.
41. In a red-black tree, what color is the root always?
a) Red
b) Black
c) Either
d) None
Explanation: The root node of a red-black tree is always black to help maintain the balancing properties.
42. Which algorithm finds shortest paths in weighted graphs?
a) BFS
b) DFS
c) Dijkstra
d) Kruskal
Explanation: Dijkstra’s algorithm finds the shortest paths from a single source in graphs with non-negative edge weights.
43. What is the time complexity to delete a node from a linked list?
a) O(1)
b) O(n)
c) O(log n)
d) O(n²)
Explanation: Deletion generally requires traversing the list to find the target node (or its predecessor), resulting in O(n) time.
44. In quicksort, what is the pivot?
a) First element
b) Last element
c) Element used for partitioning
d) Middle element
Explanation: The pivot is the element chosen to partition the array into two sub-arrays during quicksort.
45. Which is a non-linear data structure?
a) Array
b) Stack
c) Queue
d) Graph
Explanation: Graphs allow arbitrary connections between nodes (non-sequential), unlike linear structures (array, stack, queue).
46. What does DFS stand for in graph traversal?
a) Data First Search
b) Depth First Search
c) Breadth First Search
d) Direct First Search
Explanation: Depth-First Search explores as far as possible along each branch before backtracking.
47. In a trie, what is it used for?
a) Numbers
b) Strings
c) Graphs
d) Arrays
Explanation: A trie (prefix tree) is optimized for efficient storage and retrieval of strings (e.g., autocomplete, dictionaries).
48. What is the space complexity of a binary tree with n nodes?
a) O(1)
b) O(log n)
c) O(n)
d) O(n²)
Explanation: Each of the n nodes requires space for data and up to two child pointers, resulting in O(n) space.
49. Which operation is O(1) in a hash set?
a) Insertion in worst case
b) Average case lookup
c) Deletion in worst case
d) Resizing
Explanation: Hash sets (hash tables without values) provide average O(1) time for lookup, insertion, and deletion.
50. In a balanced BST, insertion time is?
a) O(n)
b) O(log n)
c) O(1)
d) O(n log n)
Explanation: Self-balancing BSTs (AVL, Red-Black) maintain logarithmic height, so insertion (and search/delete) takes O(log n) time.
