Data Structures
Introduction
Explore ways to organise and retrieve information efficiently, and analyse the time and space required by algorithms.
Topic-Wise Overview
Foundations
Abstract data types, complexity analysis, Big O and recursion
Linear Structures
Stacks, queues, deques, priority queues and linked lists
Searching and Sorting
Linear and binary search; comparison and non-comparison sorting algorithms
Hashing and Trees
Hash tables, binary search trees, heaps and balanced trees
Graphs and Memory
Graph representations, traversals, shortest paths and memory management
Question Bank Navigation
Use the links below to jump directly to each practice set. The questions remain numbered in order, and each MCQ includes an expandable answer.
- Practice MCQs — Foundations
- Additional Topic-Wise MCQs — Questions 26–51
- Applied and Advanced MCQs — Questions 52–77
- Further Applied MCQs — Questions 78–97
- Additional Topic Questions 98–109
- Short Questions with Answers
- Solved Programming Exercises — Python
Study tip: Begin with the foundational questions, then move to applied questions and programming exercises. Labels indicate practice groupings, not formal exam difficulty ratings.
Study Guidance
Start with the core definitions, follow practical examples and check your understanding with independent exercises. Practice the questions and worked examples below; further topic-wise material will be added progressively.
Practice MCQs — Foundations
25 questions covering complexity, stacks, queues, lists, searching, sorting, hashing, trees and graphs. Expand an answer to see its explanation.
Complexity
Q1. Which notation describes an asymptotic upper bound?
- A. An exact runtime in seconds
- B. Memory address
- C. Big O
- D. Big Omega only
Show correct answer and explanation
Correct answer: C. Big O
Big O provides an upper bound on asymptotic growth.
Q2. What is the worst-case time of linear search in an array of n elements?
- A. O(n)
- B. O(n²)
- C. O(1)
- D. O(log n)
Show correct answer and explanation
Correct answer: A. O(n)
If the target is last or absent, all n elements are checked.
Stacks
Q3. What order does a stack follow?
- A. Ascending key
- B. Random
- C. FIFO
- D. LIFO
Show correct answer and explanation
Correct answer: D. LIFO
The most recently pushed item is the first popped.
Q4. Push 4, push 7, then pop. Which value is returned?
- A. 4
- B. 7
- C. 11
- D. No value
Show correct answer and explanation
Correct answer: B. 7
7 is at the top of the stack.
Q5. Which structure naturally holds active recursive function calls?
- A. File index
- B. Stack
- C. Binary search tree
- D. Graph adjacency list
Show correct answer and explanation
Correct answer: B. Stack
Call frames are managed as a stack in common runtime implementations.
Queues
Q6. What order does a conventional queue follow?
- A. Descending numeric
- B. LIFO
- C. Priority sorted
- D. FIFO
Show correct answer and explanation
Correct answer: D. FIFO
The first item added is the first removed.
Q7. Enqueue A, B and C; dequeue twice. Which item remains at the front?
- A. C
- B. None
- C. A
- D. B
Show correct answer and explanation
Correct answer: A. C
A and B leave in order, so C is next.
Q8. What determines removal order in a priority queue?
- A. Only string length
- B. Fixed index 0
- C. Item priority
- D. Only insertion time
Show correct answer and explanation
Correct answer: C. Item priority
A priority queue serves according to priority (with tie behaviour dependent on implementation).
Linked Lists
Q9. What does a singly linked list node typically contain?
- A. Only an array index
- B. CPU instructions only
- C. Entire memory
- D. Value and reference to the next node
Show correct answer and explanation
Correct answer: D. Value and reference to the next node
A node stores an item and a link to the next node.
Q10. Given a head pointer, what is the cost of inserting at the front of a singly linked list?
- A. O(log n)
- B. O(1)
- C. O(n²)
- D. O(n)
Show correct answer and explanation
Correct answer: B. O(1)
Only a constant number of pointer updates is required.
Q11. Which linked-list property generally differs from a contiguous array?
- A. Lists cannot be traversed
- B. Lists always permit O(1) random indexed access
- C. Nodes need not be stored adjacently
- D. Only arrays store values
Show correct answer and explanation
Correct answer: C. Nodes need not be stored adjacently
Links connect nodes that may occupy separate memory locations.
Sorting
Q12. What is the worst-case time of insertion sort on n elements?
- A. O(n²)
- B. O(1)
- C. O(log n)
- D. O(n)
Show correct answer and explanation
Correct answer: A. O(n²)
A reverse-ordered input can require a quadratic number of shifts/comparisons.
Q13. What is typical worst-case time for merge sort?
- A. O(n log n)
- B. O(n²)
- C. O(1)
- D. O(2ⁿ)
Show correct answer and explanation
Correct answer: A. O(n log n)
Divide-and-conquer merging gives O(n log n) time.
Q14. Which simple sorting algorithm repeatedly selects the smallest remaining value?
- A. Counting sort
- B. Merge sort
- C. Selection sort
- D. Quick sort
Show correct answer and explanation
Correct answer: C. Selection sort
Selection sort selects the minimum from the unsorted portion each pass.
Searching
Q15. When can ordinary binary search be applied correctly?
- A. On an arbitrary unsorted array
- B. On sorted, indexable data
- C. Only on graphs
- D. Only on strings of length one
Show correct answer and explanation
Correct answer: B. On sorted, indexable data
Binary search depends on sorted order to eliminate half the candidates.
Q16. Binary search on 16 sorted elements needs at most how many comparisons for a successful or unsuccessful search under a standard midpoint algorithm?
- A. 16
- B. 2
- C. 4
- D. 5
Show correct answer and explanation
Correct answer: D. 5
An unsuccessful search can examine up to five midpoints as an interval of length 16 shrinks to zero.
Hashing
Q17. A hash-table collision occurs when what happens?
- A. A tree has one child
- B. Two arrays differ in length
- C. Two keys map to the same bucket or slot
- D. A value is negative
Show correct answer and explanation
Correct answer: C. Two keys map to the same bucket or slot
Collisions arise from distinct keys sharing a computed location.
Q18. Which collision-resolution method stores multiple items in buckets using a list or similar collection?
- A. Binary search
- B. Merge sort
- C. Depth-first search
- D. Separate chaining
Show correct answer and explanation
Correct answer: D. Separate chaining
Chaining stores colliding entries in a bucket-associated structure.
Trees
Q19. In a binary tree, how many children can a node have at most?
- A. 1
- B. 2
- C. 3
- D. Unlimited
Show correct answer and explanation
Correct answer: B. 2
Each binary-tree node has at most a left child and a right child.
Q20. For a binary search tree with distinct keys, which traversal outputs keys in increasing order?
- A. Inorder
- B. Preorder
- C. Postorder
- D. Level order
Show correct answer and explanation
Correct answer: A. Inorder
Visiting left subtree, root and right subtree yields ascending keys.
Q21. What is the height of a single-node tree when height is measured in edges?
- A. Undefined
- B. 0
- C. 1
- D. 2
Show correct answer and explanation
Correct answer: B. 0
There are no edges along the longest root-to-leaf path.
Graphs
Q22. Which graph search normally uses a queue to discover vertices by increasing distance in an unweighted graph?
- A. BFS
- B. Quick sort
- C. Heap sort
- D. DFS
Show correct answer and explanation
Correct answer: A. BFS
Breadth-first search explores neighbours layer by layer using a queue.
Q23. Which search is naturally implemented using a stack or recursion?
- A. Breadth-first search only
- B. Binary search
- C. Selection sort
- D. Depth-first search
Show correct answer and explanation
Correct answer: D. Depth-first search
DFS follows a branch deeply and backtracks, often through recursion or an explicit stack.
Q24. What does an adjacency matrix entry at (i,j) usually record for a simple unweighted graph?
- A. The sorting order
- B. The processor speed
- C. Whether an edge connects vertices i and j
- D. The graph diameter automatically
Show correct answer and explanation
Correct answer: C. Whether an edge connects vertices i and j
The matrix stores edge incidence, usually 1 for an edge and 0 otherwise.
Q25. In a connected, unweighted graph, what does BFS find from a given source?
- A. Always the minimum spanning tree
- B. The maximum weighted path
- C. All Hamiltonian cycles
- D. A path with the fewest edges to each reachable vertex
Show correct answer and explanation
Correct answer: D. A path with the fewest edges to each reachable vertex
BFS distances count edges and are shortest in unweighted graphs.
Short Questions with Answers
1. Explain stack and queue with an example.
Stack: last-in, first-out; after pushing 2 and 5, pop returns 5. Queue: first-in, first-out; after enqueuing 2 and 5, dequeue returns 2.
2. Differentiate linear search and binary search.
Linear search scans sequentially, needs no sorting and takes O(n) worst case. Binary search needs ordered data with efficient middle access and uses O(log n) comparisons.
3. Explain a hash collision.
If two keys hash to the same location, a collision occurs. Separate chaining puts collided items in a bucket-associated collection; open addressing probes alternative slots.
4. How does inorder traversal work?
For each binary-tree node, first traverse the left subtree, then visit the node, then traverse the right subtree. A binary search tree with distinct keys produces ascending keys.
5. Explain BFS in an unweighted graph.
Place the source in a queue and mark it visited. Repeatedly remove a vertex and enqueue each unvisited neighbour. Newly discovered vertices have distance one more than the current vertex.
Solved Programming Exercises — Python
Exercise 1: Stack Operations in Python
Problem: Push three values and pop the most recently pushed.
values = []
values.append(3)
values.append(8)
values.append(5)
print(values.pop())
print(values)Expected output: 5 [3, 8]
Explanation: The last appended value is popped first; this implements LIFO.
Exercise 2: Binary Search in Python
Problem: Find the index of 14 in a sorted array.
values = [2, 5, 8, 11, 14, 19]
target = 14
left, right = 0, len(values) - 1
position = -1
while left <= right:
mid = (left + right) // 2
if values[mid] == target:
position = mid
break
elif values[mid] < target:
left = mid + 1
else:
right = mid - 1
print(position)Expected output: 4
Explanation: The search halves the candidate interval and finds 14 at zero-based index 4.
Exercise 3: Breadth-First Traversal in Python
Problem: Traverse a small graph from A in BFS order.
from collections import deque
adj = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
queue = deque(['A'])
seen = {'A'}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in adj[node]:
if neighbour not in seen:
seen.add(neighbour)
queue.append(neighbour)
print(order)Expected output: [‘A’, ‘B’, ‘C’, ‘D’]
Explanation: The queue visits A first, followed by its neighbours B and C, then D.
Additional Topic-Wise MCQs — Questions 26–51
New conceptual, application and code-behaviour questions with expandable answers and explanations.
Asymptotic Analysis
Q26. A loop increments i by 1 from 0 to n−1; what is its iteration count?
- A. log n
- B. n²
- C. n
- D. n/2
Show correct answer and explanation
Correct answer: C. n
The loop executes once for each of n indices.
Q27. Starting with i = 1, a loop doubles i while i < n, with n ≥ 2. How does its iteration count grow?
- A. O(log n)
- B. O(2ⁿ)
- C. O(n²)
- D. O(n)
Show correct answer and explanation
Correct answer: A. O(log n)
The number of iterations is the smallest k with 2^k ≥ n, namely ⌈log₂ n⌉, and therefore is Θ(log n).
Q28. What is the auxiliary space of an iterative in-place selection sort?
- A. O(n²)
- B. O(1)
- C. O(log n)
- D. O(n)
Show correct answer and explanation
Correct answer: B. O(1)
Only a constant number of temporary variables is needed.
Stacks and Queues
Q29. A stack receives push(2), push(3), pop(), push(4). What does pop() return next?
- A. 4
- B. Nothing
- C. 2
- D. 3
Show correct answer and explanation
Correct answer: A. 4
After removing 3, 4 becomes the new top.
Q30. A circular queue with fixed capacity is useful primarily for what?
- A. Sorting arbitrary keys
- B. Traversing trees only
- C. Compressing images
- D. Reusing freed array slots efficiently
Show correct answer and explanation
Correct answer: D. Reusing freed array slots efficiently
Circular indexing allows wraparound and reuse of available storage.
Q31. Which structure is commonly used to evaluate postfix expressions?
- A. Binary tree only
- B. Hash table
- C. Stack
- D. Priority queue only
Show correct answer and explanation
Correct answer: C. Stack
Operands are pushed and operators consume the top stack values.
Q32. What is a deque?
- A. A search tree
- B. A double-ended queue
- C. A directed acyclic graph
- D. A fixed-size heap only
Show correct answer and explanation
Correct answer: B. A double-ended queue
A deque supports insertion and removal at both ends.
Linked Lists
Q33. For a singly linked list without a tail pointer, how long can appending take?
- A. O(1) always
- B. O(log n)
- C. O(n)
- D. O(n²)
Show correct answer and explanation
Correct answer: C. O(n)
Without a tail pointer, reaching the last node requires traversal.
Q34. Which pointer update inserts node N immediately after P in a singly linked list?
- A. N.next=P.next; P.next=N
- B. P=N.next; N=P.next
- C. P.next=null always
- D. N.next=N
Show correct answer and explanation
Correct answer: A. N.next=P.next; P.next=N
Preserve the old successor before linking P to N.
Q35. What extra reference does a doubly linked list node commonly have?
- A. Root of a heap
- B. Binary search pivot
- C. Array capacity
- D. Previous node
Show correct answer and explanation
Correct answer: D. Previous node
Doubly linked nodes usually store both next and previous references.
Sorting
Q36. Which algorithm is stable in its standard merge-based implementation?
- A. In-place quicksort in general
- B. Merge sort
- C. Selection sort by arbitrary swapping
- D. Heap sort
Show correct answer and explanation
Correct answer: B. Merge sort
A conventional merge implementation preserves the order of equal keys.
Q37. For a reverse-sorted list, how many comparisons does basic selection sort perform asymptotically?
- A. O(n)
- B. O(n²)
- C. O(1)
- D. O(log n)
Show correct answer and explanation
Correct answer: B. O(n²)
Basic selection sort scans the unsorted suffix regardless of initial order.
Q38. Why can quicksort reach O(n²) time?
- A. Using recursion at all
- B. Stable equal keys
- C. Choosing the middle index
- D. Highly unbalanced partitions
Show correct answer and explanation
Correct answer: D. Highly unbalanced partitions
A sequence of near-empty partitions yields a quadratic sum of work.
Q39. Which sorting method is non-comparison-based for bounded integer keys?
- A. Counting sort
- B. Insertion sort
- C. Merge sort
- D. Heap sort
Show correct answer and explanation
Correct answer: A. Counting sort
Counting sort uses key frequencies rather than pairwise ordering comparisons.
Hash Tables
Q40. What is a load factor for a typical chained hash table?
- A. Number of comparisons in merge sort
- B. Size of the largest key
- C. Number of entries divided by number of buckets
- D. Height of its root
Show correct answer and explanation
Correct answer: C. Number of entries divided by number of buckets
Load factor α = n/m measures average entries per bucket.
Q41. In linear probing, where is the next collision candidate usually sought?
- A. A linked list at the same bucket
- B. A binary tree root
- C. A sorted array
- D. A nearby slot in a fixed probe sequence
Show correct answer and explanation
Correct answer: D. A nearby slot in a fixed probe sequence
Open addressing examines alternate slots according to a probe sequence.
Trees
Q42. What are the nodes with no children called?
- A. Parents
- B. Leaves
- C. Ancestors
- D. Roots only
Show correct answer and explanation
Correct answer: B. Leaves
A leaf has no child nodes.
Q43. In a complete binary tree, where is the last level filled?
- A. In arbitrary order
- B. With exactly one node
- C. From left to right
- D. From right to left
Show correct answer and explanation
Correct answer: C. From left to right
All levels except possibly the last are full; the last is filled left to right.
Q44. Which heap property defines a min-heap?
- A. Every parent key is ≤ its children
- B. Every left child is smaller than every right child
- C. All nodes are equal
- D. The tree is a search tree
Show correct answer and explanation
Correct answer: A. Every parent key is ≤ its children
A min-heap keeps each parent no greater than its children.
Q45. What is the worst-case height of an unbalanced BST with n nodes?
- A. O(n)
- B. O(n²)
- C. O(1)
- D. O(log n) always
Show correct answer and explanation
Correct answer: A. O(n)
Sorted insertions can create a chain of n nodes.
Graphs
Q46. For an undirected graph with 5 vertices and 4 edges, what is the sum of all vertex degrees?
- A. 4
- B. 5
- C. 8
- D. 20
Show correct answer and explanation
Correct answer: C. 8
The handshaking lemma gives total degree 2m = 8.
Q47. What is a topological ordering defined for?
- A. Only complete graphs
- B. Directed acyclic graphs
- C. Every undirected cycle
- D. Any weighted graph
Show correct answer and explanation
Correct answer: B. Directed acyclic graphs
A DAG admits a vertex ordering respecting every directed edge.
Q48. Which representation uses O(V²) space for V vertices?
- A. Adjacency list in all cases
- B. Edge list in all cases
- C. Queue
- D. Adjacency matrix
Show correct answer and explanation
Correct answer: D. Adjacency matrix
A V×V adjacency matrix has V² entries.
Q49. For unweighted shortest paths from a source, which algorithm is appropriate?
- A. Selection sort
- B. Binary search
- C. Breadth-first search
- D. Depth-first search always
Show correct answer and explanation
Correct answer: C. Breadth-first search
BFS visits vertices by increasing distance in edge count.
Q50. Dijkstra’s algorithm requires what edge-weight condition for its standard correctness guarantee?
- A. Exactly one edge
- B. All weights negative
- C. No cycles of any kind
- D. Nonnegative edge weights
Show correct answer and explanation
Correct answer: D. Nonnegative edge weights
The standard algorithm assumes all edge weights are nonnegative.
Q51. Which traversal follows a path deeply before backtracking?
- A. Insertion sort
- B. DFS
- C. BFS
- D. Heapification
Show correct answer and explanation
Correct answer: B. DFS
Depth-first search explores descendants before returning to alternatives.
Applied and Advanced MCQs — Questions 52–77
Additional application, code-tracing and concept questions. C++ conventions apply to OOP questions; standard algorithm/data-structure models apply to Data Structures.
Complexity and Recursion
Q52. For T(n)=2T(n/2)+n with T(1)=Θ(1), what is T(n) for powers of 2?
- A. Θ(n log n)
- B. Θ(n²)
- C. Θ(n)
- D. Θ(log n)
Show correct answer and explanation
Correct answer: A. Θ(n log n)
The merge-sort recurrence has log n levels, each with Θ(n) work.
Q53. For T(n)=T(n−1)+1, T(1)=1, what is asymptotic growth?
- A. Θ(log n)
- B. Θ(n)
- C. Θ(n²)
- D. Θ(1)
Show correct answer and explanation
Correct answer: B. Θ(n)
The recurrence adds one unit for each decrease from n to 1.
Q54. A recursive function calls itself once with n−1 until n=0. What is maximum call-stack depth?
- A. Θ(n)
- B. Θ(n²)
- C. Θ(1)
- D. Θ(log n)
Show correct answer and explanation
Correct answer: A. Θ(n)
There are n+1 active levels before the base case.
Q55. Starting at i = 1, a loop doubles i while i < n for integer n ≥ 2 and performs constant work each time. What is its runtime?
- A. Θ(n²)
- B. Θ(2ⁿ)
- C. Θ(n)
- D. Θ(log n)
Show correct answer and explanation
Correct answer: D. Θ(log n)
The loop makes ⌈log₂ n⌉ iterations, each doing constant work, so the runtime is Θ(log n).
Stacks and Queues
Q56. Evaluate the postfix expression 5 2 + 3 *.
- A. 10
- B. 11
- C. 21
- D. 30
Show correct answer and explanation
Correct answer: C. 21
First 5+2=7; then 7×3=21.
Q57. Which structure is best suited to managing undo operations when only the latest change is undone?
- A. Priority queue
- B. Hash set
- C. Binary heap
- D. Stack
Show correct answer and explanation
Correct answer: D. Stack
The latest action is reversed first, a last-in-first-out pattern.
Q58. A queue initially contains [A,B,C] front to back. After dequeue and enqueue D, what is the order?
- A. [C,D,B]
- B. [D,B,C]
- C. [B,C,D]
- D. [A,C,D]
Show correct answer and explanation
Correct answer: C. [B,C,D]
Dequeue removes A; enqueue adds D at the back.
Q59. If a queue is implemented by a circular array, what does wrapping mean?
- A. After last array index, the next index is zero
- B. The queue becomes sorted
- C. Every enqueue copies all elements
- D. The first slot is never reused
Show correct answer and explanation
Correct answer: A. After last array index, the next index is zero
Circular indexing uses the array modulo its capacity.
Linked Lists
Q60. With only a head pointer, deleting the first node of a nonempty singly linked list takes what time?
- A. O(n²)
- B. O(1)
- C. O(log n)
- D. O(n)
Show correct answer and explanation
Correct answer: B. O(1)
The head can be advanced to its successor in constant time.
Q61. Which condition identifies the final node in a conventional null-terminated singly linked list?
- A. Its next reference is null
- B. Its value is zero
- C. It has two children
- D. Its array index equals n
Show correct answer and explanation
Correct answer: A. Its next reference is null
The last node has no successor link.
Searching and Sorting
Q62. What is the worst-case comparison count for linear search on a list of 8 items?
- A. 3
- B. 4
- C. 7
- D. 8
Show correct answer and explanation
Correct answer: D. 8
The searched-for item may be last or absent, requiring eight comparisons.
Q63. How many comparisons does selection sort make on 5 elements using the standard minimum-selection procedure?
- A. 4
- B. 5
- C. 10
- D. 20
Show correct answer and explanation
Correct answer: C. 10
The passes compare 4+3+2+1=10 pairs regardless of original order.
Q64. Which common sorting algorithm is stable when implemented by merging equal keys from the left half first?
- A. Selection sort with arbitrary swaps
- B. Merge sort
- C. Heap sort
- D. Typical in-place quicksort
Show correct answer and explanation
Correct answer: B. Merge sort
Keeping left-half equal keys first preserves their original relative order.
Q65. Which data are needed for an ordinary binary search on an array?
- A. Only distinct values
- B. Only powers of two
- C. Sorted values
- D. Only positive numbers
Show correct answer and explanation
Correct answer: C. Sorted values
Binary search requires ordering; duplicate values are permitted.
Hashing
Q66. In separate chaining, what does a hash table typically store at each bucket?
- A. A collection of colliding entries
- B. A binary search pivot only
- C. A graph root
- D. A running total of keys
Show correct answer and explanation
Correct answer: A. A collection of colliding entries
Each bucket can hold multiple items whose keys map there.
Q67. If a table has 12 entries across 8 buckets, what is its load factor?
- A. 4
- B. 20
- C. 0.67
- D. 1.5
Show correct answer and explanation
Correct answer: D. 1.5
Load factor is n/m = 12/8 = 1.5 for separate chaining.
Q68. What happens when open-addressing insertion probes a slot already occupied by another key?
- A. It switches into a binary tree
- B. It follows the probing sequence to another slot
- C. It always overwrites the key
- D. It must terminate the program
Show correct answer and explanation
Correct answer: B. It follows the probing sequence to another slot
Open addressing resolves collisions by examining alternate locations.
Trees and Heaps
Q69. A tree has one root and exactly three edges along its longest root-to-leaf path. What is its height in edges?
- A. 2
- B. 3
- C. 4
- D. 8
Show correct answer and explanation
Correct answer: B. 3
Height counts edges on the longest downward path, giving 3.
Q70. In a min-heap, which position contains a minimum element?
- A. The last leaf
- B. Always the right child
- C. An arbitrary internal node
- D. The root
Show correct answer and explanation
Correct answer: D. The root
Each parent has a key no greater than its children, so the root is minimal.
Q71. What is the worst-case complexity of searching for a key in a skewed, unbalanced BST with n nodes?
- A. O(n)
- B. O(n log n)
- C. O(1)
- D. O(log n)
Show correct answer and explanation
Correct answer: A. O(n)
A skewed BST can form a chain with n nodes.
Q72. What order does postorder traversal use for a binary tree?
- A. Root-left-right
- B. Left-root-right
- C. Left-right-root
- D. Right-root-left
Show correct answer and explanation
Correct answer: C. Left-right-root
Postorder processes left subtree, then right subtree, then root.
Graphs
Q73. In an undirected simple graph with 6 vertices each of degree 2, how many edges are there?
- A. 8
- B. 12
- C. 4
- D. 6
Show correct answer and explanation
Correct answer: D. 6
The sum of degrees is 12; dividing by two gives six edges.
Q74. For a directed graph with a cycle, what is true about a topological ordering of all its vertices?
- A. It always exists
- B. It cannot exist
- C. It must start at the cycle
- D. It always uses BFS
Show correct answer and explanation
Correct answer: B. It cannot exist
A topological ordering exists exactly for directed acyclic graphs.
Q75. Which shortest-path method works for unweighted graphs using a queue?
- A. Selection sort
- B. Binary search
- C. BFS
- D. DFS for all cases
Show correct answer and explanation
Correct answer: C. BFS
BFS discovers vertices at increasing edge-distance.
Q76. For a dense graph with V vertices, which representation directly tests whether edge (u,v) exists in O(1) time?
- A. Adjacency matrix
- B. Unsorted edge list
- C. Singly linked list of all vertices
- D. Only a queue
Show correct answer and explanation
Correct answer: A. Adjacency matrix
A matrix entry indexed by u and v provides constant-time lookup.
Q77. What is the sum of outdegrees in any finite directed graph?
- A. Number of edges
- B. Twice number of edges
- C. Number of vertices squared
- D. Always zero
Show correct answer and explanation
Correct answer: A. Number of edges
Each directed edge contributes one to its source’s outdegree.
Further Applied MCQs — Questions 78–97
Advanced conceptual, code-based and application questions with explanations. C++ conventions are used in OOP questions; standard data-structure assumptions are used elsewhere.
Algorithm Reasoning
Q78. How many comparisons are needed to find the maximum of n≥1 elements by linear scanning?
- A. n²
- B. log₂n
- C. n−1
- D. n
Show correct answer and explanation
Correct answer: C. n−1
After choosing the first item, compare the remaining n−1 items.
Q79. Which recurrence represents binary search with constant work per step?
- A. T(n)=T(n−1)+n
- B. T(n)=T(n/2)+O(1)
- C. T(n)=2T(n/2)+n
- D. T(n)=nT(n−1)
Show correct answer and explanation
Correct answer: B. T(n)=T(n/2)+O(1)
Each step narrows the search to approximately half the elements.
Q80. Two sequential loops each visit n elements and do constant work. What is their combined runtime?
- A. Θ(log n)
- B. Θ(2ⁿ)
- C. Θ(n²)
- D. Θ(n)
Show correct answer and explanation
Correct answer: D. Θ(n)
Their running times add to n+n=2n, which is Θ(n).
Q81. A binary-search procedure on a sorted array starts left=0, right=7. What initial midpoint does (left+right)//2 give?
- A. 7
- B. 8
- C. 3
- D. 4
Show correct answer and explanation
Correct answer: C. 3
Integer division of 7 by 2 yields index 3.
Stacks and Queues
Q82. Starting with an empty stack, push 1, push 2, pop, push 5. What is at the top?
- A. Empty
- B. 1
- C. 2
- D. 5
Show correct answer and explanation
Correct answer: D. 5
After removing 2, pushing 5 makes it the top element.
Q83. What structure is used by BFS to process discovered vertices in arrival order?
- A. Heap sort
- B. Queue
- C. Stack only
- D. Binary search tree
Show correct answer and explanation
Correct answer: B. Queue
A FIFO queue processes vertices layer by layer.
Q84. What is a standard use of a stack in parsing?
- A. Matching nested parentheses
- B. Choosing shortest weighted paths
- C. Sorting using a hash function
- D. Storing every graph edge
Show correct answer and explanation
Correct answer: A. Matching nested parentheses
Opening delimiters are pushed and checked against closing delimiters.
Linked Lists
Q85. In a nonempty singly linked list with a head pointer, removing the head is what time complexity?
- A. O(log n)
- B. O(1)
- C. O(n²)
- D. O(n)
Show correct answer and explanation
Correct answer: B. O(1)
Update the head to the successor in constant time.
Q86. What extra pointer is typically stored by doubly linked nodes?
- A. Previous pointer
- B. Heap pointer
- C. Hash seed
- D. Root pointer
Show correct answer and explanation
Correct answer: A. Previous pointer
Nodes reference both next and previous neighbours.
Sorting
Q87. After applying one standard left-to-right pass of bubble sort to [5, 2, 4, 1], what is the array?
- A. [1, 2, 4, 5]
- B. [2, 4, 1, 5]
- C. [5, 4, 2, 1]
- D. [2, 5, 1, 4]
Show correct answer and explanation
Correct answer: B. [2, 4, 1, 5]
Compare adjacent pairs and swap if out of order: [2,5,4,1], then [2,4,5,1], then [2,4,1,5]. The largest element reaches the final position.
Q88. Which algorithm has Θ(n log n) worst-case time under a standard merge sort implementation?
- A. Bubble sort
- B. Insertion sort
- C. Merge sort
- D. Selection sort
Show correct answer and explanation
Correct answer: C. Merge sort
Merge sort recursively divides and merges, producing n log n work.
Q89. What input commonly triggers Θ(n²) work for standard insertion sort?
- A. All values equal with strict comparison
- B. A single element
- C. Already ascending
- D. Reverse sorted
Show correct answer and explanation
Correct answer: D. Reverse sorted
Each new element must shift past nearly all previously seen values.
Hash Tables
Q90. A chained hash table has 18 keys and 12 buckets. What is its load factor?
- A. 30
- B. 0.67
- C. 1.5
- D. 6
Show correct answer and explanation
Correct answer: C. 1.5
Load factor is keys divided by buckets: 18/12=1.5.
Q91. What is a collision in hashing?
- A. Two distinct keys map to the same bucket
- B. A key has length zero
- C. A tree has one child
- D. Two values are sorted
Show correct answer and explanation
Correct answer: A. Two distinct keys map to the same bucket
A hash function can map different keys to one bucket.
Trees
Q92. In a BST with distinct integer keys, what order does inorder traversal produce?
- A. Descending
- B. Increasing
- C. Insertion order
- D. Unspecified random
Show correct answer and explanation
Correct answer: B. Increasing
The left-root-right traversal follows the BST key ordering.
Q93. For a min-heap, where is one smallest key always located?
- A. Root
- B. Rightmost leaf
- C. Any internal node
- D. Last array cell
Show correct answer and explanation
Correct answer: A. Root
The heap-order property places a minimum at the root.
Graphs
Q94. An undirected graph has 7 edges. What is the sum of its vertex degrees?
- A. 21
- B. 49
- C. 7
- D. 14
Show correct answer and explanation
Correct answer: D. 14
Each edge contributes two to the sum of degrees.
Q95. Which algorithmic technique underlies topological sorting using indegree counts?
- A. Backtracking over all permutations
- B. Dijkstra relaxation
- C. Kahn’s algorithm
- D. Binary search
Show correct answer and explanation
Correct answer: C. Kahn’s algorithm
Kahn’s algorithm repeatedly selects vertices with indegree zero, removes their outgoing edges, and produces a topological order when the graph is acyclic.
Q96. Which algorithm gives shortest paths by number of edges in an unweighted graph?
- A. DFS always
- B. BFS
- C. Selection sort
- D. Linear search
Show correct answer and explanation
Correct answer: B. BFS
Breadth-first search explores vertices by distance layers.
Q97. In a dense graph with V vertices, what space does a conventional adjacency matrix use?
- A. O(V)
- B. O(E) only
- C. O(V²)
- D. O(log V)
Show correct answer and explanation
Correct answer: C. O(V²)
Its V by V entries require quadratic storage.
Quality Review — New Topic Questions 98–109
Additional questions selected to strengthen underrepresented topics, with answer explanations.
Sorting Variants
Q98. Which algorithm processes keys digit by digit, commonly relying on stable passes?
- A. Radix sort
- B. Selection sort
- C. BFS
- D. Binary search
Show correct answer and explanation
Correct answer: A. Radix sort
Radix sort sorts keys by individual digits or positions.
Q99. What is a practical limitation of counting sort?
- A. It must compare every pair of keys
- B. It cannot handle repeated keys
- C. It must use recursion
- D. A very large key range may use excessive memory
Show correct answer and explanation
Correct answer: D. A very large key range may use excessive memory
Counting sort uses an array sized to the key range.
Q100. What does stable sorting preserve?
- A. Array capacity
- B. Relative order of records having equal keys
- C. The original order of all records
- D. Always the smallest element’s position
Show correct answer and explanation
Correct answer: B. Relative order of records having equal keys
Equal-key elements keep their original relative ordering.
Graph Algorithms
Q101. Which algorithm computes shortest paths from a source in graphs with nonnegative edge weights?
- A. Topological sort alone
- B. Dijkstra’s algorithm
- C. Prim’s algorithm
- D. DFS alone
Show correct answer and explanation
Correct answer: B. Dijkstra’s algorithm
Dijkstra’s greedy relaxation is correct for nonnegative weights.
Q102. A directed acyclic graph has edges A→C and B→C. Which sequence is a valid topological order?
- A. C, A, B
- B. A, C, B
- C. B, C, A
- D. B, A, C
Show correct answer and explanation
Correct answer: D. B, A, C
Both A and B must occur before C. The order B, A, C respects both directed edges.
Q103. Which common graph representation is typically more memory-efficient for sparse graphs?
- A. Adjacency lists
- B. Dense adjacency matrices
- C. A V×V matrix with 1s
- D. A full pairwise distance matrix
Show correct answer and explanation
Correct answer: A. Adjacency lists
Adjacency lists store vertices and actual edges, taking O(V+E) space.
Q104. What does a topological sorting algorithm do when it detects a directed cycle?
- A. Delete every edge automatically
- B. Convert the graph into an undirected one
- C. Report that a full topological ordering is impossible
- D. Output any permutation as valid
Show correct answer and explanation
Correct answer: C. Report that a full topological ordering is impossible
Every directed cycle creates contradictory precedence requirements.
Balanced Trees
Q105. Which balancing scheme uses red and black node colours to constrain BST height?
- A. Unbalanced BST
- B. Trie with no ordering
- C. Binary heap
- D. Red-black trees
Show correct answer and explanation
Correct answer: D. Red-black trees
Red-black invariants keep the height logarithmic.
Q106. What is the worst-case search complexity of an AVL tree with n nodes?
- A. O(n)
- B. O(log n)
- C. O(1)
- D. O(n²)
Show correct answer and explanation
Correct answer: B. O(log n)
Height-balancing maintains logarithmic tree height.
Memory and Structures
Q107. What is the main purpose of garbage collection?
- A. Find shortest paths
- B. Encrypt stack frames
- C. Reclaim memory that is no longer reachable or needed
- D. Sort keys into ascending order
Show correct answer and explanation
Correct answer: C. Reclaim memory that is no longer reachable or needed
Garbage collectors reclaim unused managed allocations according to their reachability/liveness model.
Q108. What is a trie particularly suited for?
- A. Prefix-based string lookup
- B. General integer multiplication
- C. Matrix inversion only
- D. Heap extraction
Show correct answer and explanation
Correct answer: A. Prefix-based string lookup
Trie edges commonly encode successive symbols of keys, supporting prefix queries.
Q109. Why do cache-friendly contiguous arrays often outperform linked lists in sequential scans?
- A. Spatial locality reduces memory-access overhead
- B. Arrays always require fewer comparisons
- C. Lists cannot contain integers
- D. Arrays have no bounds
Show correct answer and explanation
Correct answer: A. Spatial locality reduces memory-access overhead
Nearby array elements tend to benefit from cache locality.
Additional Data Structures MCQs — Questions 110–150
Q110. What property makes an array suitable for constant-time indexed access?
- A. Each element has a next pointer
- B. It is always sorted
- C. Every element is a tree node
- D. Contiguous storage with direct address calculation
Show correct answer and explanation
Correct answer: D. Contiguous storage with direct address calculation
Array indexing computes an element address from its index under the standard array model.
Q111. When is a dynamic array likely to reallocate its storage?
- A. When an insertion exceeds current capacity
- B. Every time an element is read
- C. Only when all elements are equal
- D. Whenever binary search is used
Show correct answer and explanation
Correct answer: A. When an insertion exceeds current capacity
Growing past capacity may require allocating a larger contiguous block.
Q112. What is amortized analysis used to describe?
- A. The number of graph vertices only
- B. Average cost per operation over a sequence of operations
- C. Only worst-case input size
- D. Memory addresses of stack frames
Show correct answer and explanation
Correct answer: B. Average cost per operation over a sequence of operations
Amortized bounds spread occasional costly steps across many operations.
Q113. What is a circular linked list?
- A. An always sorted array
- B. A graph without vertices
- C. A linked list whose final node links back into the list
- D. A list with no links
Show correct answer and explanation
Correct answer: C. A linked list whose final node links back into the list
In a circular list the final link returns to a node, commonly the head.
Q114. Why can linked lists be less cache-friendly than arrays?
- A. They always have fewer nodes
- B. They cannot store values
- C. They require a sorted key
- D. Successive nodes may be scattered in memory
Show correct answer and explanation
Correct answer: D. Successive nodes may be scattered in memory
Noncontiguous nodes often cause poorer spatial locality.
Q115. What is stack underflow?
- A. Attempting to remove an item from an empty stack
- B. Adding an item to a nonfull stack
- C. A successful search
- D. An extra hash collision
Show correct answer and explanation
Correct answer: A. Attempting to remove an item from an empty stack
A pop on an empty stack cannot return a valid stored item.
Q116. What is queue overflow in a bounded queue?
- A. A successful enqueue
- B. Attempting to insert when the queue is full
- C. Removing the last available item
- D. Moving the front pointer
Show correct answer and explanation
Correct answer: B. Attempting to insert when the queue is full
A capacity-limited queue needs to handle an enqueue with no free slot.
Q117. What does a queue’s front operation usually do?
- A. Remove every element
- B. Reverse all entries
- C. Inspect the next item without removing it
- D. Sort the entire queue
Show correct answer and explanation
Correct answer: C. Inspect the next item without removing it
Front or peek returns the item scheduled to leave next.
Q118. Which data structure is naturally used by an event scheduler based on event times?
- A. Unordered stack
- B. Unsorted singly linked list only
- C. Fixed integer variable
- D. Priority queue
Show correct answer and explanation
Correct answer: D. Priority queue
A priority queue efficiently selects the event with the earliest scheduled time.
Q119. What is the primary requirement of a balanced binary search tree?
- A. Its height remains controlled relative to the number of nodes
- B. Every node has exactly two children
- C. All keys are equal
- D. It contains no references
Show correct answer and explanation
Correct answer: A. Its height remains controlled relative to the number of nodes
Balancing avoids the linear-height degeneration of ordinary BSTs.
Q120. What does an AVL rotation maintain?
- A. The tree is converted to a hash table
- B. Binary search ordering while restoring height balance
- C. All key values become equal
- D. Every node becomes a root
Show correct answer and explanation
Correct answer: B. Binary search ordering while restoring height balance
AVL rotations locally restructure links without changing sorted key order.
Q121. What is a graph’s adjacency list?
- A. Only the vertex degrees
- B. A sorted array of weights only
- C. For each vertex, a collection of its neighbors
- D. A matrix of every possible path
Show correct answer and explanation
Correct answer: C. For each vertex, a collection of its neighbors
Adjacency lists store edges by listing neighbors at each vertex.
Q122. What is a connected component of an undirected graph?
- A. One directed edge only
- B. A graph’s maximum weight
- C. A sorting pass
- D. A maximal set of mutually reachable vertices
Show correct answer and explanation
Correct answer: D. A maximal set of mutually reachable vertices
Every pair of vertices within a connected component is joined by a path.
Q123. How can DFS be used to detect a cycle in an undirected graph?
- A. Find an edge to a visited vertex other than the current parent
- B. Check only the number of vertices
- C. Require every degree to be one
- D. Always return true for trees
Show correct answer and explanation
Correct answer: A. Find an edge to a visited vertex other than the current parent
During undirected DFS, such a non-parent visited neighbor indicates a cycle.
Q124. What is a spanning tree of a connected undirected graph?
- A. A shortest path only
- B. A connected acyclic subgraph containing all vertices
- C. The set of all edges
- D. A graph containing only one vertex
Show correct answer and explanation
Correct answer: B. A connected acyclic subgraph containing all vertices
A spanning tree connects every vertex using exactly V−1 edges.
Q125. Which classical algorithm constructs a minimum spanning tree using edge weights in increasing order?
- A. Insertion sort alone
- B. Fibonacci recursion
- C. Kruskal’s algorithm
- D. Binary search
Show correct answer and explanation
Correct answer: C. Kruskal’s algorithm
Kruskal processes candidate edges by weight while avoiding cycles.
Q126. Which data structure is commonly used by Kruskal’s algorithm to track components?
- A. A postfix stack only
- B. A hash string only
- C. An array of source filenames
- D. Disjoint-set union
Show correct answer and explanation
Correct answer: D. Disjoint-set union
Union-find efficiently determines whether two endpoints are already connected.
Q127. What is path compression in a disjoint-set forest?
- A. Making nodes point closer to the representative during find
- B. Deleting every root
- C. Sorting values in every component
- D. Reversing all graph edges
Show correct answer and explanation
Correct answer: A. Making nodes point closer to the representative during find
Path compression flattens parent links and improves future find operations.
Q128. Why is a min-heap often used with Dijkstra’s algorithm?
- A. To convert edges into a tree before search
- B. To extract a vertex with the smallest tentative distance
- C. To detect all negative cycles automatically
- D. To guarantee all weights are integers
Show correct answer and explanation
Correct answer: B. To extract a vertex with the smallest tentative distance
A priority queue supports efficient selection of the smallest tentative distance.
Q129. Which graph algorithm can handle negative edge weights and detect reachable negative cycles?
- A. Standard Dijkstra without modification
- B. Selection sort
- C. Bellman-Ford
- D. Ordinary BFS
Show correct answer and explanation
Correct answer: C. Bellman-Ford
Bellman-Ford relaxes edges repeatedly and checks for reachable negative cycles.
Q130. When can a shortest path be undefined due to negative weights?
- A. When the graph has more than ten vertices
- B. Whenever there is a queue
- C. When every edge weight is positive
- D. When a reachable negative cycle can lead to the destination
Show correct answer and explanation
Correct answer: D. When a reachable negative cycle can lead to the destination
Repeated traversal of a relevant negative cycle can reduce path cost without bound.
Q131. What is a hash function used for in a hash table?
- A. Map keys to hash values or bucket locations
- B. Guarantee unique output for every key
- C. Balance a binary tree
- D. Find shortest graph paths
Show correct answer and explanation
Correct answer: A. Map keys to hash values or bucket locations
A hash function determines where to seek a key, with collisions handled separately.
Q132. Why does a high load factor often slow a chained hash table?
- A. Every value is deleted
- B. More entries tend to occupy each bucket
- C. All keys become invalid
- D. The number of buckets doubles automatically
Show correct answer and explanation
Correct answer: B. More entries tend to occupy each bucket
Longer chains can increase expected search work.
Q133. What does rehashing usually involve?
- A. Deleting all stored values
- B. Sorting every key lexicographically
- C. Reassigning entries into a new bucket arrangement
- D. Converting every entry to a tree node
Show correct answer and explanation
Correct answer: C. Reassigning entries into a new bucket arrangement
After changing capacity or hashing parameters, keys are redistributed into buckets.
Q134. What is the worst-case time of a hash-table lookup without favorable distribution assumptions?
- A. Always O(1)
- B. Always O(log log n)
- C. O(2^n) exactly
- D. O(n)
Show correct answer and explanation
Correct answer: D. O(n)
Pathological collisions can force examination of many entries.
Q135. Which sorting algorithm repeatedly swaps adjacent out-of-order items?
- A. Bubble sort
- B. Merge sort
- C. Counting sort
- D. Radix sort
Show correct answer and explanation
Correct answer: A. Bubble sort
Bubble sort scans neighboring pairs and swaps them when needed.
Q136. Which sorting algorithm partitions data around a pivot?
- A. Selection sort
- B. Quicksort
- C. Insertion sort
- D. Counting sort
Show correct answer and explanation
Correct answer: B. Quicksort
Quicksort recursively orders elements relative to a pivot.
Q137. Why is stable sorting useful for records with multiple keys?
- A. It always runs in O(n)
- B. It cannot reorder any element
- C. It preserves earlier ordering among equal keys
- D. It guarantees the smallest memory use
Show correct answer and explanation
Correct answer: C. It preserves earlier ordering among equal keys
Stability enables sorting by secondary and then primary keys.
Q138. What does breadth-first traversal of a rooted tree visit first?
- A. Only leaves
- B. The rightmost path exclusively
- C. Nodes by key size in every tree
- D. Nodes at smaller depths
Show correct answer and explanation
Correct answer: D. Nodes at smaller depths
BFS visits the root and then successive depth levels.
Q139. Which tree traversal visits the root before either subtree?
- A. Preorder
- B. Inorder
- C. Postorder
- D. Reverse inorder only
Show correct answer and explanation
Correct answer: A. Preorder
Preorder processes root, then left and right subtrees.
Q140. What is a binary tree’s height in edges?
- A. The sum of node keys
- B. The maximum number of edges on a root-to-leaf path
- C. The number of leaves
- D. The root’s degree only
Show correct answer and explanation
Correct answer: B. The maximum number of edges on a root-to-leaf path
Height measures the longest downward path from the root.
Q141. What is the maximum number of nodes at level d in a binary tree if the root is level 0?
- A. 2d+1
- B. d²
- C. 2^d
- D. d+1
Show correct answer and explanation
Correct answer: C. 2^d
Each binary level can double the number of nodes, giving at most 2^d.
Q142. How many edges does a tree with 12 vertices contain?
- A. 12
- B. 13
- C. 24
- D. 11
Show correct answer and explanation
Correct answer: D. 11
Every finite tree with V vertices has V−1 edges.
Q143. What is a trie node commonly associated with?
- A. A prefix of stored keys
- B. A weighted graph’s diameter
- C. Only a heap maximum
- D. A sorting pivot
Show correct answer and explanation
Correct answer: A. A prefix of stored keys
Paths from the root encode successive symbols and their prefixes.
Q144. What is a suffix of a string?
- A. The length of an array
- B. A contiguous portion ending at the string’s last character
- C. Any unordered subset of characters
- D. A prefix only
Show correct answer and explanation
Correct answer: B. A contiguous portion ending at the string’s last character
A suffix begins at some position and continues to the end of the string.
Q145. Which abstract data type supports insert, delete and find-min operations?
- A. Fixed Boolean
- B. Recursion stack only
- C. Min-priority queue
- D. Read-only array
Show correct answer and explanation
Correct answer: C. Min-priority queue
A min-priority queue maintains items to retrieve and remove the minimum.
Q146. How many vertex-degree units does an undirected edge contribute overall?
- A. 1
- B. 0
- C. 4
- D. 2
Show correct answer and explanation
Correct answer: D. 2
Each undirected edge contributes one to each endpoint degree, counting loops twice.
Q147. Which condition is necessary for an undirected graph to have an Euler circuit?
- A. Every vertex with a nonzero degree lies in one component and every vertex has even degree
- B. Exactly three vertices have odd degree
- C. Every edge has a unique weight
- D. It has no cycle
Show correct answer and explanation
Correct answer: A. Every vertex with a nonzero degree lies in one component and every vertex has even degree
A connected edge-containing component with all even degrees admits an Euler circuit.
Q148. What is the time complexity of BFS using adjacency lists for a graph with V vertices and E edges?
- A. O(2^V)
- B. O(V+E)
- C. O(V²E)
- D. O(1)
Show correct answer and explanation
Correct answer: B. O(V+E)
BFS processes vertices and scans their adjacency lists, totaling O(V+E).
Q149. Why are dynamic programming tables useful?
- A. They eliminate all space use
- B. They guarantee constant-time algorithms
- C. They store solutions of subproblems to avoid repeated computation
- D. They require every problem to be a graph
Show correct answer and explanation
Correct answer: C. They store solutions of subproblems to avoid repeated computation
Memoization or tabulation reuses results of overlapping subproblems.
Q150. What is memoization?
- A. Deleting cached values immediately
- B. Sorting a graph’s adjacency matrix
- C. Repeatedly computing the same result without storage
- D. Caching results of previously solved subproblems
Show correct answer and explanation
Correct answer: D. Caching results of previously solved subproblems
Memoization trades storage for avoiding redundant computation.
Interactive MCQ Practice
Practise one MCQ at a time. Reveal the correct answer and explanation before proceeding to the next question.
Start Data Structures — One Question at a Time