GATE CS 2024 — PYQ-style Set 1

Practice sheet: all 25 questions

Prefer reading first? Every question from this practice set, with the answer and a worked explanation. (Solving them in the practice set above earns XP — up to ≈150.)

1. Q1. A binary tree has 63 nodes and every level is completely filled. What is its height? (The root is at height 0.)

   Show answer & explanation

   Answer: 5

   A perfect binary tree of height h has 2^(h+1) − 1 nodes; 2⁶ − 1 = 63 gives h = 5. The level-by-level counts 1, 2, 4, 8, 16, 32 sum to 63 — six levels, heights 0 through 5.

2. Q2. What is the worst-case time complexity of quicksort, and when does it occur?

   • a. O(n log n), on random input
   • b. O(n²), when partitioning is maximally unbalanced (e.g. sorted input with first-element pivot)
   • c. O(n²), only when all elements are negative
   • d. O(log n), on nearly-sorted input
   Show answer & explanation

   Answer: B. O(n²), when partitioning is maximally unbalanced (e.g. sorted input with first-element pivot)

   If every partition puts 0 elements on one side (already-sorted input with a first/last-element pivot), the recurrence becomes T(n) = T(n−1) + n = O(n²). Randomised or median-of-three pivots make this case astronomically unlikely, which is why quicksort is fast in practice.

3. Q3. How many edges does the complete undirected graph K₈ (8 vertices) have?

   Show answer & explanation

   Answer: 28

   A complete graph on n vertices has n(n−1)/2 edges: 8 × 7 ÷ 2 = 28 — one edge per unordered vertex pair, i.e. C(8,2). This formula also bounds the edge count of any simple graph.

4. Q4. An in-order traversal of a binary search tree visits the keys in:

   • a. Ascending sorted order
   • b. Descending sorted order
   • c. Level order
   • d. Insertion order
   Show answer & explanation

   Answer: A. Ascending sorted order

   In-order (left, root, right) on a BST yields ascending order, because everything smaller sits in the left subtree and everything larger in the right. This property is also the standard O(n) test of whether a tree is a valid BST.

5. Q5. A max-heap contains the elements 50, 30, 40, 10, 20, 35. After deleting the maximum, what is the new maximum?

   • a. 35
   • b. 40
   • c. 30
   • d. 20
   Show answer & explanation

   Answer: B. 40

   Deleting the max (50) leaves 30, 40, 10, 20, 35, whose largest element is 40 — extract-max always surfaces the next-largest after re-heapifying. Note the answer needs no heap trace at all: the new max of a heap is simply the largest remaining value.

6. Q6. Which of the following sorting algorithms have average-case time complexity O(n log n)? (Select all that apply.)

   • a. Merge sort
   • b. Heap sort
   • c. Quicksort
   • d. Bubble sort
   Show answer & explanation

   Answer: A. Merge sort · B. Heap sort · C. Quicksort

   Merge sort and heap sort are O(n log n) in every case; quicksort is O(n log n) on average (O(n²) worst case). Bubble sort averages O(n²). MSQ items like this reward knowing the full best/average/worst table for the classic sorts.

7. Q7. Starting from an empty stack, these operations run in order: push(5), push(3), pop(), push(7), push(1), pop(), pop(). What value is on top of the stack at the end?

   Show answer & explanation

   Answer: 5

   Trace: [5] → [5,3] → pop 3 → [5] → [5,7] → [5,7,1] → pop 1 → pop 7 → [5]. Only 5 remains, so it's the top. Writing the stack contents after each operation is faster and safer than tracking pops mentally.

8. Q8. Processes P1, P2, P3 arrive at times 0, 2, 4 with burst times 7, 4, 1. Under preemptive SRTF scheduling, what is the average waiting time?

   Show answer & explanation

   Answer: 2

   P1 runs 0–2 (5 left); P2 arrives with 4 < 5 and runs 2–4 (2 left); P3 arrives with 1 < 2 and runs 4–5; P2 finishes 5–7; P1 finishes 7–12. Waiting = turnaround − burst: P1 = 12−0−7 = 5, P2 = 7−2−4 = 1, P3 = 0. Average = 6/3 = 2.

9. Q9. Increasing the number of page frames can INCREASE the number of page faults under which replacement policy?

   • a. LRU
   • b. Optimal
   • c. FIFO
   • d. Working-set
   Show answer & explanation

   Answer: C. FIFO

   This is Belady's anomaly, and it afflicts FIFO because eviction order ignores usage. LRU and Optimal are stack algorithms — their k-frame content is always a subset of their (k+1)-frame content — so more memory can never hurt them.

10. Q10. For the reference string 1,2,3,4,1,2,5,1,2,3,4,5 with 3 page frames under FIFO replacement, how many page faults occur?

    Show answer & explanation

    Answer: 9

    Faults: 1,2,3 (cold), 4 evicts 1, then 1 evicts 2, 2 evicts 3, 5 evicts 4; hits on 1 and 2; then 3 evicts 5's oldest co-resident 1... tracing fully gives faults on 1,2,3,4,1,2,5,3,4 and hits on 1,2,5 — 9 faults. This exact string is famous: with 4 frames FIFO faults 10 times, demonstrating Belady's anomaly.

11. Q11. A counting semaphore is initialised to 4. Six processes execute wait() on it and three execute signal(). What is its final value?

    • a. 0
    • b. 1
    • c. 2
    • d. −2
    Show answer & explanation

    Answer: B. 1

    Each wait() decrements and each signal() increments: 4 − 6 + 3 = 1. Intermediate values went negative (processes blocked), but the arithmetic holds regardless of ordering — a GATE staple because the order-independence surprises people.

12. Q12. Which of the following is NOT shared between the threads of a single process?

    • a. Global variables
    • b. Heap memory
    • c. Open file descriptors
    • d. Stack
    Show answer & explanation

    Answer: D. Stack

    Each thread has a private stack (its own call frames and locals) and register set; code, globals, heap and open files are shared process-wide. That privacy is what makes local variables thread-safe by default while globals need locks.

13. Q13. Relation R(A, B, C, D) has functional dependencies A → B and B → C. What is the candidate key of R?

    • a. A
    • b. AD
    • c. ABD
    • d. D
    Show answer & explanation

    Answer: B. AD

    D appears on no right-hand side, so every key must contain D; likewise A is never determined, so keys must contain A. Closure of AD = {A, B, C, D} — all attributes — and neither A nor D alone suffices, so AD is the (unique, minimal) candidate key.

14. Q14. Relation R(A, B, C) has FDs AB → C and C → B. What is the highest normal form R satisfies?

    • a. 1NF
    • b. 2NF
    • c. 3NF
    • d. BCNF
    Show answer & explanation

    Answer: C. 3NF

    Candidate keys are AB and AC, so every attribute is prime — 2NF and 3NF hold automatically (3NF permits X → Y when Y is prime). But C → B has a non-superkey determinant, violating BCNF. This AB→C, C→B pattern is THE canonical 3NF-but-not-BCNF example.

15. Q15. Employees has 100 rows, Departments has 10 rows, and every employee's dept_id references a valid department. How many rows does Employees LEFT JOIN Departments ON dept_id return?

    Show answer & explanation

    Answer: 100

    dept_id is a key of Departments, so each employee matches exactly one department row: 100 × 1 = 100 rows, and (every FK being valid) the LEFT JOIN behaves identically to an inner join here. Row-count questions hinge on whether the join column is unique on the other side.

16. Q16. Strict two-phase locking (strict 2PL) guarantees:

    • a. Serializability only
    • b. Serializability and freedom from cascading aborts
    • c. Freedom from deadlock
    • d. Minimum lock contention
    Show answer & explanation

    Answer: B. Serializability and freedom from cascading aborts

    Strict 2PL holds all exclusive locks until commit, so no transaction ever reads uncommitted data — cascading aborts become impossible, on top of 2PL's conflict-serializability. It still does NOT prevent deadlock; option c is the standard trap.

17. Q17. How many usable host addresses are available in a /28 IPv4 subnet?

    Show answer & explanation

    Answer: 14

    /28 leaves 4 host bits → 2⁴ = 16 addresses, minus network and broadcast = 14 usable. For any prefix /p, usable hosts = 2^(32−p) − 2 — worth having memorised as a formula for NAT-style numeric answers.

18. Q18. How many segments are exchanged to establish a TCP connection?

    • a. 2
    • b. 3
    • c. 4
    • d. 1
    Show answer & explanation

    Answer: B. 3

    Connection setup is the three-way handshake: SYN, SYN-ACK, ACK. Teardown, by contrast, normally takes four segments (FIN/ACK in each direction) — the 3-vs-4 asymmetry is a favourite GATE detail.

19. Q19. A link has bandwidth 2 Mbps and round-trip time 50 ms. What is the bandwidth-delay product in bits?

    Show answer & explanation

    Answer: 100000

    BDP = bandwidth × RTT = 2×10⁶ bits/s × 0.05 s = 100,000 bits — the amount of data that fills the "pipe". A sender's window must be at least this size to keep the link busy; smaller windows waste capacity waiting for ACKs.

20. Q20. In CSMA/CD (classic Ethernet), the minimum frame size is determined by:

    • a. The maximum cable length's round-trip propagation delay
    • b. The size of the MAC address
    • c. The receiver's buffer size
    • d. The IP header length
    Show answer & explanation

    Answer: A. The maximum cable length's round-trip propagation delay

    A sender must still be transmitting when a collision signal returns from the far end, or it would miss the collision — so transmission time ≥ 2 × propagation delay, which fixes a minimum frame size (64 bytes in classic Ethernet). Frame size and network diameter are locked together.

21. Q21. int f(int n) { return n <= 1 ? 1 : f(n-1) + f(n-2); } — how many total calls to f (including the first) are made when computing f(4)?

    Show answer & explanation

    Answer: 9

    Calls C(n) = 1 + C(n−1) + C(n−2) with C(0) = C(1) = 1: C(2) = 3, C(3) = 5, C(4) = 9. The call tree grows roughly like the Fibonacci numbers themselves — the standard argument for why naive Fibonacci is exponential and needs memoisation.

22. Q22. What does this C snippet print? int a[] = {2, 4, 6, 8}; int *p = a; printf("%d", *(p + 2));

    • a. 4
    • b. 6
    • c. 8
    • d. A garbage address
    Show answer & explanation

    Answer: B. 6

    Pointer arithmetic scales by element size: p + 2 points at a[2], so *(p + 2) is 6 — identical to p[2]. The equivalence *(p+i) ≡ p[i] ≡ a[i] is the single most reused fact in GATE pointer questions.

23. Q23. Calling an overridden method through a base-class pointer and having the derived class's version execute at runtime is called:

    • a. Function overloading
    • b. Runtime polymorphism (dynamic dispatch)
    • c. Encapsulation
    • d. Multiple inheritance
    Show answer & explanation

    Answer: B. Runtime polymorphism (dynamic dispatch)

    Choosing the method implementation by the object's actual type at runtime is dynamic dispatch — runtime polymorphism, implemented in C++ via virtual functions and vtables. Overloading, by contrast, is resolved at compile time from the argument types.

24. Q24. Which statements about static data members of a class are true? (Select all that apply.)

    • a. One copy is shared by all objects of the class
    • b. They can be accessed without creating any object
    • c. Each object gets its own independent copy
    • d. They must be constant
    Show answer & explanation

    Answer: A. One copy is shared by all objects of the class · B. They can be accessed without creating any object

    A static member belongs to the class, not to instances: one shared copy, accessible as ClassName.member (or ClassName::member) with zero objects alive. It's fully mutable — "static" here means shared lifetime and storage, not immutability.

25. Q25. After int i = 5; int j = i++ * 2; what are the values of i and j?

    • a. i = 6, j = 10
    • b. i = 6, j = 12
    • c. i = 5, j = 10
    • d. i = 5, j = 12
    Show answer & explanation

    Answer: A. i = 6, j = 10

    Post-increment yields the OLD value to the expression, then increments: j = 5 × 2 = 10, and i becomes 6 afterwards. With pre-increment (++i × 2) the answer would be j = 12 — the old/new distinction is the entire question.