Thirty questions in GATE format covering all phases (15 one-mark, 15 two-mark; 45 marks). Set a 90-minute timer, work on paper, and enter your answers in the boxes. For MSQ tick all correct options; for NAT enter a number. Then press Submit answers: the page scores you with GATE negative marking, shows topic-wise accuracy, lists the questions you got wrong and the lessons to re-read. The full key is at the very end of these notes.
Conventions: log = log₂; arrays 0-based except heaps (1-based); ascending sorts; comparisons count key comparisons; adjacency lists in alphabetical or numerical order.
⏱️
30 questions · 45 marks · 90 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.
Q1MCQ1 markLinked lists
A singly linked list keeps only a head pointer. Which operation costs Θ(n)?
- (A) Insert at the front
- (B) Read the first element
- (C) Insert at the end
- (D) Delete the first node
Q2NAT1 markTree height
Minimum possible height of a binary tree with 100 nodes (height of a single node = 0)?
Your answer:
Q3MCQ1 markAsymptotics
Which statement is FALSE?
- (A) n log n = o(n²)
- (B) 2ⁿ⁺¹ = O(2ⁿ)
- (C) log(n²) = Θ(log n)
- (D) 2²ⁿ = O(2ⁿ)
Q4NAT1 markHalving loop
for (i = 1024; i > 1; i = i / 2) count++; from count = 0. Final count?
Your answer:
Q5MCQ1 markMaster theorem
T(n) = 8T(n/2) + n² solves to:
- (A) Θ(n² log n)
- (B) Θ(n³)
- (C) Θ(n²)
- (D) Θ(n³ log n)
Q6NAT1 markBinary search
Maximum number of probes of binary search on a sorted array of 1000 elements?
Your answer:
Q7NAT1 markLoad factor
A chained hash table has 500 slots and stores 2000 keys. Load factor?
Your answer:
Q8MSQ1 markStability
Which of these, as usually implemented, are stable?
- (A) Heapsort
- (B) Insertion sort
- (C) Merge sort
- (D) Selection sort
Q9NAT1 markSecond largest
Minimum number of comparisons to find the second largest of 64 distinct numbers?
Your answer:
Q10MCQ1 markCounting sort
Counting sort on n integers in the range 0 … k runs in:
- (A) Θ(k log k)
- (B) Θ(n + k)
- (C) Θ(nk)
- (D) Θ(n log n)
Q11NAT1 markFast power
Multiplications used by repeated squaring for x⁶³ (squarings plus one per odd step)?
Your answer:
Q12MCQ1 markGreedy fails
For which problem is the greedy rule "highest value per unit weight first" NOT always optimal?
- (A) Fractional knapsack
- (B) 0/1 knapsack
- (C) Neither
- (D) Both
Q13NAT1 markRecursive calls
Naive recursive fib(7) (base cases fib(0), fib(1)) makes how many calls, including the first?
Your answer:
Q14MSQ1 markBFS
Which are true of BFS from a source s?
- (A) On a connected graph its tree has V − 1 edges.
- (B) It runs in Θ(V + E) with adjacency lists.
- (C) It uses a stack.
- (D) It finds the fewest-edge path from s to every reachable vertex.
Q15MCQ1 markNegative edges
A directed graph has some negative edge weights but no negative cycle. Which single-source algorithm is guaranteed correct on it?
- (A) Dijkstra's algorithm
- (B) Bellman–Ford
- (C) BFS
- (D) Prim's algorithm
Q16NAT2 marksRecurrence value
T(1) = 1, T(n) = 2T(n/2) + n. T(16)?
Your answer:
Q17NAT2 marksRoot recurrence
T(2) = 1, T(n) = T(√n) + 1. T(65536)?
Your answer:
Q18NAT2 marksLinear probing
Table of size 10, h(k) = k mod 10, linear probing. Insert 23, 43, 13, 27, 37. Total number of probes (home slot counts as one probe)?
Your answer:
Q19NAT2 marksEmpty slots
10 keys are hashed uniformly and independently into 10 slots (chaining). Expected number of empty slots (2 decimals)?
Your answer:
Q20NAT2 marksMerge sort
Top-down merge sort on [5, 2, 9, 1, 7, 3, 8, 4]. Total number of key comparisons?
Your answer:
Q21NAT2 marksQuicksort
Quicksort with Lomuto partition (pivot = last) on [4, 1, 3, 9, 7]. Total key comparisons?
Your answer:
Q22NAT2 marksBuild-heap
Bottom-up build-max-heap on [10, 20, 15, 30, 40] (1-based). Number of swaps?
Your answer:
Q23NAT2 marksFractional knapsack
Capacity 15. Items (value, weight): (40, 4), (30, 6), (50, 10), (45, 9). Maximum value with fractions allowed?
Your answer:
Q24NAT2 marksHuffman
Frequencies A 30, B 10, C 7, D 25, E 28 (out of 100). Average Huffman code length (2 decimals)?
Your answer:
Q25NAT2 marks0/1 knapsack
Items (weight, value): (3, 25), (2, 20), (1, 15), (4, 40), (5, 50); capacity 6. Maximum value?
Your answer:
Q26NAT2 marksCoin change
Number of ways to make 20 with coins {1, 5, 10} (order ignored)?
Your answer:
Q27NAT2 marksMatrix chain
Dimensions p = (4, 10, 3, 12, 20, 7). Minimum scalar multiplications?
Your answer:
Q28MSQ2 marksDFS edges
Directed graph 1→2, 1→3, 2→4, 3→2, 3→4, 4→1; DFS from 1 with numerical neighbour order. Which are true?
- (A) 4 → 1 is a back edge.
- (B) 3 → 2 is a cross edge.
- (C) 1 → 3 is a forward edge.
- (D) The graph contains a cycle.
Q29NAT2 marksPrim
Undirected graph: A–B 7, A–D 5, B–C 8, B–D 9, B–E 7, C–E 5, D–E 15, D–F 6, E–F 8, E–G 9, F–G 11. Weight of the MST found by Prim from A?
Your answer:
Q30NAT2 marksDijkstra
Undirected graph on 1–6: 1–2 7, 1–3 9, 1–6 14, 2–3 10, 2–4 15, 3–4 11, 3–6 2, 4–5 6, 5–6 9. Dijkstra from 1: distance to 5?
Your answer:
Show the key