Data Structures and Algorithms carries some of the most predictable marks in GATE CSE. This GATE-style practice set focuses on what the exam repeatedly tests: solving recurrences, properties of trees and heaps, sorting behaviour, hashing and graph algorithms. The explanations show the working, so use them to check your method, not just the answer.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 15 questions.
Topics covered in this set
- Recurrences and the master theorem
- Binary trees, complete trees and BSTs
- Heaps and build-heap complexity
- Sorting: stability and worst cases
- Hashing and load factor
- BFS, Dijkstra, Bellman-Ford, Kruskal and topological sort
GATE CSE Algorithms MCQs with answers and explanations
Q1. What is the solution of T(n) = 2T(n/2) + n?
a) Θ(n log n)
b) Θ(n²)
c) Θ(n)
d) Θ(log n)
Q2. What is the solution of T(n) = T(n − 1) + n with T(1) = 1?
a) Θ(n²)
b) Θ(2ⁿ)
c) Θ(n)
d) Θ(n log n)
Q3. What is the solution of T(n) = 4T(n/2) + n²?
a) Θ(n³)
b) Θ(n log n)
c) Θ(n²)
d) Θ(n² log n)
Q4. What is the maximum number of nodes in a binary tree of height h, where a tree with only a root has height 0?
a) 2^h
b) 2^(h+1) − 1
c) h²
d) 2^h − 1
Q5. How many leaf nodes does a complete binary tree with 100 nodes have?
a) 64
b) 51
c) 49
d) 50
Q6. What is the time complexity of building a binary max-heap from n unsorted elements using the bottom-up heapify method?
a) O(log n)
b) O(n log n)
c) O(n)
d) O(n²)
Q7. Which traversal of a binary search tree produces the keys in sorted (ascending) order?
a) Inorder
b) Level order
c) Postorder
d) Preorder
Q8. Quick sort that always picks the first element as the pivot is given an already sorted array of n elements. What is its running time?
a) O(n²)
b) O(n)
c) O(log n)
d) O(n log n)
Q9. Which of these sorting algorithms is stable in its standard implementation?
a) Heap sort
b) Selection sort
c) Quick sort
d) Merge sort
Q10. Why can Dijkstra's algorithm give wrong answers on a graph with negative edge weights?
a) It runs out of memory
b) It only works on trees
c) It finalises a vertex's distance when it is extracted, assuming no later path can be shorter, which negative edges can violate
d) It cannot handle undirected graphs
Q11. In hashing with separate chaining and load factor α = n/m, what is the expected time for an unsuccessful search under simple uniform hashing?
a) Θ(log n)
b) Θ(n)
c) Θ(1)
d) Θ(1 + α)
Q12. What is the minimum number of comparisons needed in the worst case to find both the minimum and the maximum of 100 elements?
a) 198
b) 150
c) 148
d) 99
Q13. What is the value of the postfix expression 2 3 4 * + 5 -?
a) 25
b) -1
c) 9
d) 15
Q14. What is the time complexity of BFS on a graph with V vertices and E edges stored as adjacency lists?
a) O(E log V)
b) O(V + E)
c) O(VE)
d) O(V²)
Q15. A directed graph has a topological ordering if and only if:
a) Every vertex has in-degree at least 1
b) It has an even number of edges
c) It is strongly connected
d) It has no directed cycle (it is a DAG)
Quick revision notes
- Master theorem: compare f(n) with n^(log_b a); equal order gives an extra log n factor.
- Complete binary tree with n nodes has ceil(n/2) leaves.
- Build-heap is O(n); heap sort is O(n log n).
- Merge sort is stable; quick sort worst case is O(n²).
- Dijkstra needs non-negative weights; Bellman-Ford is O(VE); BFS is O(V + E).
Frequently asked questions
Are these actual GATE previous year questions?
No. They are original GATE-style questions written to match the syllabus and difficulty. Use them alongside official GATE papers.
How much of GATE CSE is algorithms and data structures?
Together they usually account for a significant share of marks each year, and they also support questions in other subjects, so they are worth mastering early.
Should I memorise the master theorem?
Yes, along with how to unroll recurrences that do not fit it, such as T(n) = T(n − 1) + n.
Comments
Post a Comment