Arrays, stacks and queues
What is the time complexity of accessing an array element by index? (a) O(1) (b) O(log n) (c) O(n) (d) O(n log n)
(a) O(1). An array is a contiguous block, so the address of element i is computed arithmetically from the base address. Searching an unsorted array is still O(n) - constant access and constant search are different claims.
Which data structure follows LIFO order? (a) Queue (b) Stack (c) Linked list (d) Heap
(b) Stack - last in, first out, with push and pop at the same end. A queue is FIFO, adding at the rear and removing from the front.
Which data structure is used to evaluate a postfix expression? (a) Queue (b) Stack (c) Tree (d) Graph
(b) Stack. Push operands; on an operator, pop the required operands, apply it, and push the result. The same structure converts infix to postfix and checks balanced parentheses.
What problem does a circular queue solve compared with a linear array queue?
It reuses the space freed at the front. In a linear array queue, repeated enqueue and dequeue push the rear index to the end and the queue reports itself full while slots at the front sit empty. Wrapping the indices with modulo arithmetic fixes that.
Which data structure does the runtime use to manage function calls and recursion? (a) Queue (b) Heap (c) Stack (d) Tree
(c) Stack - the call stack, which holds a frame per active call with its local variables and return address. Recursion without a reachable base case exhausts it, producing a stack overflow.
Practice this now
Linked lists
What is the time complexity of deleting the last node of a singly linked list with n nodes, given only the head? (a) O(1) (b) O(log n) (c) O(n) (d) O(n²)
(c) O(n). You must walk to the second-last node to update its next pointer, since a singly linked list has no backward links. A doubly linked list with a tail pointer does it in O(1).
What is the main advantage of a linked list over an array?
Insertion and deletion at a known position take O(1) pointer updates with no shifting, and the structure grows without reallocation. The costs are losing O(1) random access and paying memory overhead per node for the pointers.
Which technique detects a cycle in a linked list in O(1) extra space? (a) Hashing visited nodes (b) Floyd's slow and fast pointers (c) Reversing the list (d) Sorting the nodes
(b) Floyd's cycle-detection algorithm - one pointer moves one step and another two; if they ever meet, a cycle exists. Hashing also works but uses O(n) extra space.
Practice this now
Trees and heaps
Which traversal of a binary search tree produces elements in ascending order? (a) Pre-order (b) In-order (c) Post-order (d) Level-order
(b) In-order (left, root, right). It is the standard way to test whether a tree is a valid BST - the in-order output must be strictly increasing.
What is the worst-case time complexity of searching in a binary search tree? (a) O(1) (b) O(log n) (c) O(n) (d) O(n log n)
(c) O(n). O(log n) holds only when the tree is balanced; inserting already-sorted data degenerates the BST into a linked list. Self-balancing trees like AVL and red-black guarantee O(log n) in the worst case, which is precisely why they exist.
What is the maximum number of nodes in a binary tree of height h, counting the root as height 0?
2^(h+1) − 1. Each level i holds at most 2^i nodes, and the geometric sum gives the total. Check the convention in the question - some texts count the root as height 1, which shifts the formula.
In a min-heap, what are the complexities of finding and extracting the minimum? (a) O(1) and O(1) (b) O(1) and O(log n) (c) O(log n) and O(log n) (d) O(n) and O(log n)
(b) O(1) to find, O(log n) to extract. The minimum is always at the root, but removing it requires moving the last element up and sifting it down through the tree's height. Insertion is likewise O(log n).
Which data structure best implements a priority queue? (a) Sorted array (b) Unsorted array (c) Binary heap (d) Hash table
(c) Binary heap - O(log n) insert and O(log n) extract-min, with O(1) peek. A sorted array gives O(1) peek but O(n) insert; a hash table has no ordering at all.
Which traversal would you use to produce a prefix expression, and which to safely delete a tree?
Pre-order (root, left, right) produces prefix notation and is used to copy a tree. Post-order (left, right, root) is used to delete, because children must be freed before their parent.
Practice this now
Hashing
What are the average and worst case complexities of a hash table lookup? (a) O(1) and O(1) (b) O(1) and O(n) (c) O(log n) and O(n) (d) O(n) and O(n)
(b) O(1) average, O(n) worst case. If every key hashes to the same bucket, lookup degenerates into a linear scan of that chain. A good hash function and a sensible load factor are what keep the average case true.
Which of these is a collision resolution technique? (a) Chaining (b) Open addressing (c) Double hashing (d) All of these
(d) All of these. Chaining stores colliding entries in a list at the bucket; open addressing probes for another slot (linear or quadratic probing); double hashing uses a second hash function to compute the probe step.
What is the load factor of a hash table?
The ratio of stored entries to buckets. As it rises, collisions rise and performance drifts away from O(1), so implementations resize and rehash once the load factor crosses a threshold - 0.75 in Java's HashMap by default.
Practice this now
Related reading
Sorting and searching
This is the densest MCQ area in the subject. The table is worth memorising outright, since a large share of questions are direct lookups from it.
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
What is the worst-case complexity of quicksort, and when does it occur?
O(n²), when the pivot is consistently the smallest or largest element - classically on already-sorted input with a first-element or last-element pivot. Randomised or median-of-three pivot selection makes this case vanishingly unlikely.
Which sorting algorithm is stable? (a) Quick sort (b) Heap sort (c) Merge sort (d) Selection sort
(c) Merge sort. Stability means equal elements keep their original relative order, which matters when sorting by a second key. Insertion and bubble sort are also stable; quick, heap and selection sort are not.
What is the prerequisite for binary search, and what is its complexity?
The array must be sorted, and the complexity is O(log n) because each comparison halves the search space. Applying binary search to unsorted data is the classic wrong answer in this family.
Which sorting algorithm performs best on data that is already nearly sorted? (a) Quick sort (b) Insertion sort (c) Selection sort (d) Heap sort
(b) Insertion sort, which approaches O(n) on nearly-sorted input because each element needs almost no shifting. Selection sort is O(n²) regardless of input, and naive quicksort actually degrades on sorted data.
Practice this now
Graphs
How many edges does a complete undirected graph with n vertices have? (a) n (b) n − 1 (c) n(n−1)/2 (d) n²
(c) n(n−1)/2. Every pair of distinct vertices is joined once. A complete directed graph has n(n−1) edges, since each pair contributes two arcs.
Which data structures underlie BFS and DFS respectively? (a) Stack and queue (b) Queue and stack (c) Both queues (d) Both stacks
(b) BFS uses a queue to explore level by level; DFS uses a stack, either explicitly or via recursion on the call stack. This single fact answers a surprising number of graph MCQs.
What is the space complexity of an adjacency matrix versus an adjacency list? (a) O(V) and O(V²) (b) O(V²) and O(V + E) (c) O(E) and O(V) (d) Both O(V²)
(b) O(V²) for the matrix and O(V + E) for the list. Use a matrix for dense graphs and O(1) edge lookups; use a list for sparse graphs, which is most real-world data.
Why does Dijkstra's algorithm fail with negative edge weights?
Because it finalises a vertex's distance the moment it is dequeued, assuming no later path can improve it - an assumption a negative edge breaks. Use the Bellman-Ford algorithm, which is O(VE) but tolerates negative weights and detects negative cycles.
Which traversal detects whether a directed graph has a cycle, and what does topological sort require?
DFS with a recursion-stack marker detects a back edge and hence a cycle. Topological sorting requires a directed acyclic graph - if a cycle exists, no valid ordering can be produced.
Practice this now
How to revise complexities so they stick
- ✓Build the sorting table from a blank page, not by re-reading it. Columns: best, average, worst, space, stable.
- ✓For every structure, learn the operation that is unexpectedly expensive - array insertion in the middle, linked-list random access, hash-table worst case, unbalanced BST search.
- ✓Learn worst cases together with the condition that triggers them. 'Quicksort is O(n²)' is half an answer; 'on sorted input with a poor pivot' is the whole one.
- ✓Ask 'which access pattern?' rather than 'which structure?'. Random access by index means array; last-in-first-out means stack; ordered iteration means tree; fast key lookup means hash table.
- ✓Then drill under time. Complexity recall must be instant, because written tests give roughly a minute per question.
Practice this now