GATE CSE 2020 question paper with solutions

GATE CSE 2020 answer key

General Aptitude GA Q.1 to Q.10

1. GA Q.1MCQ · 1 markOfficial answer: D
2. GA Q.2MCQ · 1 markOfficial answer: A
3. GA Q.3MCQ · 1 markOfficial answer: A
4. GA Q.4MCQ · 1 markOfficial answer: D
5. GA Q.5MCQ · 1 markOfficial answer: B
6. GA Q.6MCQ · 2 marksOfficial answer: D
7. GA Q.7MCQ · 2 marksOfficial answer: C
8. GA Q.8MCQ · 2 marksOfficial answer: A
9. GA Q.9MCQ · 2 marksOfficial answer: B
10. GA Q.10MCQ · 2 marksOfficial answer: C

Computer Science and Information Technology Q.1 to Q.55

1. Q.1MCQ · 1 markOfficial answer: A
2. Q.2MCQ · 1 markOfficial answer: A

   Data Structures and Algorithms › Complexity

   Substituting $m={\log }_{b}n$ turns the "take a-th root of the argument" recurrence $T(n)=T(n^{1/a})+1$ into the familiar "divide the exponent by $a$" recurrence $S(m)=S(m/a)+1$, whose solution is $\Theta ({\log }_{a}m)$; undoing the substitution gives the nested double logarithm $\Theta ({\log }_a{\log }_{b}n)$.

   WATCH OUT FOR

   Treating the two parameters $a$ and $b$ as combinable into a single log base (picking option (B), $\Theta ({\log }_{ab}n)$) instead of recognizing that $a$ controls how many times you must take roots (an outer log) while $b$ sets the base at which the argument bottoms out (an inner log) — the two play structurally different roles and cannot be merged into one log base.

   Full solution →
3. Q.3MCQ · 1 markOfficial answer: C

   Computer Organization and Architecture › I/O, interrupts & DMA

   Vectored interrupts let the device self-identify to the CPU (no polling needed); polling is only for non-vectored/software-poll schemes. Daisy chaining is a hardware priority-resolution mechanism. DMA requires exclusive bus mastership handed off from the CPU — never shared simultaneously.

   WATCH OUT FOR

   Confusing "vectored" with requiring polling (students sometimes think the CPU still must poll to confirm the vector), and assuming DMA and CPU can share the bus concurrently since both are "active" during a DMA transfer — in reality bus mastership is exclusive at any instant.

   Full solution →
4. Q.4MCQ · 1 markOfficial answer: C

   Computer Organization and Architecture › ALU & control unit

   In this single-bus datapath, the ALU has two inputs: one comes directly (combinationally) off the bus, the other from the latched register TEMP1. So whichever step places a value into TEMP1 must execute before the step that uses TEMP1 as an ALU input. Similarly, a memory read (MEMr) takes time to complete, so the step that issues it must finish before the step that consumes its result from MDR.

   WATCH OUT FOR

   Assuming the four steps that don't obviously belong to "fetch" (1, 2, 4) can be freely reordered as long as they come after the fetch pair, and picking option (D) by reading step 1 before step 2 in numeric order — without checking that step 1 needs TEMP1 to already hold R1, which only step 2 provides.

   Full solution →
5. Q.5MCQ · 1 markOfficial answer: B

   Data Structures and Algorithms › Trees & heaps

   A BST's preorder uniquely determines its shape: the root is first, and the remaining elements split into two contiguous runs — those less than the root (left subtree preorder) and those greater (right subtree preorder), recursively. Once the tree is reconstructed, postorder = left subtree postorder, then right subtree postorder, then root, applied recursively.

   WATCH OUT FOR

   Confusing preorder-to-postorder conversion with just reversing the preorder sequence (which would wrongly suggest something like 19,16,18,20,11,12,10,15, option D) — reversing preorder only produces a valid postorder-like listing for specific tree shapes, not in general; the visit order of left/right children must actually be respected via correct BST reconstruction.

   Full solution →
6. Q.6MCQ · 1 markOfficial answer: C

   Data Structures and Algorithms › Trees & heaps

   Each AVL insertion costs Θ(log m) where m is the current tree size; since the tree size stays between n and n²+n throughout the process, log m is Θ(log n) for every single one of the n² insertions (because log(n²) = 2log n is still just a constant multiple of log n), so the n² insertions together cost Θ(n² log n) — not Θ(n² log(n²)), because Θ absorbs the constant factor of 2.

   WATCH OUT FOR

   Writing the final tree size as n²+n and concluding the last insertions cost Θ(log(n²)) = Θ(2 log n²) and then sloppily treating the exponent as if it must appear explicitly, sometimes leading to Θ(n² log n²) being (wrongly) simplified to Θ(n⁴) or left as a distinct-looking but numerically identical expression to n² log n — since Θ(log n²) = Θ(2 log n) = Θ(log n) exactly, both forms are the same complexity class, and no additional factor of n or n² should appear.

   Full solution →
7. Q.7MCQ · 1 markOfficial answer: Marks to all
8. Q.8MCQ · 1 markOfficial answer: D
9. Q.9MCQ · 1 markOfficial answer: D
10. Q.10MCQ · 1 markOfficial answer: C
11. Q.11MCQ · 1 markOfficial answer: C
12. Q.12MCQ · 1 markOfficial answer: C
13. Q.13MCQ · 1 markOfficial answer: A
14. Q.14MCQ · 1 markOfficial answer: A
15. Q.15MCQ · 1 markOfficial answer: D
16. Q.16MCQ · 1 markOfficial answer: C

    Data Structures and Algorithms › Linear structures

    Maintaining sorted order in a linked list forces a linear scan from the head to find each element's correct position (no random access, so no binary search); summing the worst-case traversal cost 0+1+2+...+(n-1) over n insertions gives Θ(n²).

    WATCH OUT FOR

    Assuming a sorted linked list allows binary search (as with a sorted array), giving a false O(n log n) answer — binary search requires random access, which a linked list does not have, so each insertion's search for position is inherently linear in the current list size.

    Full solution →
17. Q.17NAT · 1 markOfficial answer: 0.125
18. Q.18NAT · 1 markOfficial answer: 7
19. Q.19NAT · 1 markOfficial answer: 5
20. Q.20NAT · 1 markOfficial answer: 1034

    Computer Organization and Architecture › Memory & cache

    A decoder that uniquely addresses every byte of a 1 KB RAM needs one output line per byte and enough input (address) lines to select among all outputs of a full binary decoder ($n=2^m$).

    WATCH OUT FOR

    Confusing "byte addressable 1 KB" with the number of address bits alone (giving m + m = 20) or forgetting that n must equal the full 1024 output lines (one per addressable byte), not some smaller count.

    Full solution →
21. Q.21NAT · 1 markOfficial answer: 13.3, or 13.5

    Computer Organization and Architecture › Memory & cache

    Average memory access time (AMAT) combines the cache's own access time with the extra time paid only on a miss: $\text{AMAT}=\text{Hit time}+\text{Miss rate}\times \text{Miss penalty}$, where the miss penalty for a block transfer is (time for first word) + (words remaining) $\times$ (time per subsequent word).

    WATCH OUT FOR

    Using the wrong word size to compute words per block (e.g. forgetting to convert 64 bits to 8 bytes), or forgetting to subtract 1 from the word count when computing the miss penalty (the first word already costs 20 ns, so only the remaining 31 words cost 5 ns each) — this pair of slips is exactly why the answer key accepts two nearby values.

    Full solution →
22. Q.22NAT · 1 markOfficial answer: 19

    Programming in C › Pointers & arrays

    For a 2D array int a[4][5], a decays to a pointer of type int(*)[5] (pointer to a row), so a + k skips k whole rows. Inside a row, ordinary pointer arithmetic on an int* skips single ints. Evaluate the expression from the innermost * outward, tracking the type at each step.

    WATCH OUT FOR

    Confusing **a (which decays through two levels to give a[0][0] = 1, an int) with *a (which is a[0], decaying to a pointer to int), and then applying the wrong pointer arithmetic scale (rows of size 5 vs. single ints) at each step of *(*(a+**a+2)+3).

    Full solution →
23. Q.23NAT · 1 markOfficial answer: 13

    Data Structures and Algorithms › Sorting & hashing

    Double hashing: the probe sequence address at step $i$ is $\text{address}(i)=\left(h_1(k)+i\cdot h_2(k)\right)\mathrm{mod}m$, where probe 0 is the first probe ($i=0$).

    WATCH OUT FOR

    Numbering probe 0 as $i=1$ (an off-by-one), which would compute probe 1 as $i=2$ and give the wrong address; or computing $h_2(k)$ without the $+1$ offset.

    Full solution →
24. Q.24NAT · 1 markOfficial answer: 7
25. Q.25NAT · 1 markOfficial answer: 6
26. Q.26MCQ · 2 marksOfficial answer: A
27. Q.27MCQ · 2 marksOfficial answer: C
28. Q.28MCQ · 2 marksOfficial answer: B
29. Q.29MCQ · 2 marksOfficial answer: B

    Computer Organization and Architecture › ALU & control unit

    To divide two IEEE-754 single-precision numbers, decode each into sign, exponent (unbiased), and significand, do the arithmetic in decimal, then re-encode the result back into IEEE-754 bits.

    WATCH OUT FOR

    Forgetting to un-bias the exponent (subtracting 127) before combining, or mis-tracking the sign bit when one operand is negative, leading to a wrong-magnitude or wrong-sign final hex encoding.

    Full solution →
30. Q.30MCQ · 2 marksOfficial answer: B

    Computer Organization and Architecture › Memory & cache

    Split the 24-bit physical address (since main memory $=16\text{ MB}=2^{24}\text{ B}$) into Tag | Set Index | Block Offset. Block offset width = ${\log }_2(\text{block size})$. Number of cache sets = (cache size / block size) / associativity, so set-index width = ${\log }_2(\text{sets})$. Two addresses collide in the cache iff their set-index bits are equal, regardless of their tag bits.

    WATCH OUT FOR

    Miscounting the number of index bits by using ${\log }_2(\text{cache size}/\text{block size})$ (giving 8 bits) instead of dividing by the associativity first to get the number of SETS ($64\text{KB}/256\text{B}=256$ blocks, $256/4=64$ sets $\Rightarrow 6$ index bits), which shifts every set number and can flip which addresses collide.

    Full solution →
31. Q.31MCQ · 2 marksOfficial answer: D

    Data Structures and Algorithms › Graph algorithms

    By the MST cycle property, adding an edge $(u,v)$ keeps $T$ an MST iff the new edge's weight is not less than the weight of the maximum-weight edge on the unique tree path between $u$ and $v$; since $T$ has only $|V|-1$ edges, finding that path and its max edge by a traversal restricted to $T$ costs $\Theta (|V|)$, independent of $|E|$.

    WATCH OUT FOR

    Assuming the check must scan the whole graph $G$ (all $|E|$ edges) or rerun a full MST algorithm such as Kruskal's ($\Theta (|E|\log |V|)$), instead of noticing that only the tree $T$ — with exactly $|V|-1$ edges — needs to be traversed.

    Full solution →
32. Q.32MCQ · 2 marksOfficial answer: A
33. Q.33MCQ · 2 marksOfficial answer: B
34. Q.34MCQ · 2 marksOfficial answer: A
35. Q.35MCQ · 2 marksOfficial answer: B
36. Q.36MCQ · 2 marksOfficial answer: A
37. Q.37MCQ · 2 marksOfficial answer: A
38. Q.38MCQ · 2 marksOfficial answer: B
39. Q.39MCQ · 2 marksOfficial answer: C
40. Q.40MCQ · 2 marksOfficial answer: A

    Data Structures and Algorithms › Graph algorithms

    Reweighting every edge (u,v) by w'(u,v) = w(u,v) + f(u) - f(v) changes the total weight of ANY path P from a fixed u to a fixed v by exactly the same constant f(u) - f(v) (the intermediate f-terms telescope away), regardless of which internal vertices P visits. Since a constant additive shift applied identically to every competing u-to-v path can never change which of them has the smallest total weight, the set of shortest paths between any pair of vertices is identical under w and under w' -- for every choice of f, with no sign restriction and no special construction required.

    WATCH OUT FOR

    Students assume Johnson's algorithm's specific choice of f (the shortest-distance-from-an-added-source construction, option D) is necessary for shortest paths to be preserved, because that is the f used in practice. In fact that construction is only needed to make w' nonnegative so Dijkstra becomes usable -- a separate, additional goal. Preservation of shortest paths itself holds for every f with no restriction, since the endpoint-only additive shift is order-preserving regardless of its sign.

    Full solution →
41. Q.41MCQ · 2 marksOfficial answer: B

    Data Structures and Algorithms › Trees & heaps

    A 1-D range query $[a,b]$ on a balanced BST is answered by (i) locating the "split node" where the search paths for $a$ and $b$ diverge — $O(\log n)$ since the tree has height $O(\log n)$ — and then (ii) walking the two boundary paths down from the split node toward $a$ and $b$; at every point along these two paths where the path stays inside the range, the entire subtree hanging off on the "safe" side is wholly within $[a,b]$ and can be dumped by an in-order traversal in time proportional to its own size. Steps (i) plus the two boundary-path walks cost $O(\log n)$ total, independent of how many elements qualify; dumping all the qualifying subtrees costs $O(k)$ total, since every node visited during a subtree dump is itself reported. Hence total time is $\Theta (\log n+k)$ — no augmentation (like a range tree or order-statistics fields) is even required for this bound.

    WATCH OUT FOR

    Assuming that because there are $O(\log n)$ "candidate" root-to-node paths involved, each of the $k$ reported elements must additionally cost $O(\log n)$ to reach (giving the trap answer $\Theta (k\log n)$, choice C). This double-counts: once a qualifying subtree is identified in $O(1)$ time relative to the boundary walk, its elements are read off by a plain linear in-order traversal at $O(1)$ amortized cost per element, not by a fresh search from the root for each one. A second common mistake is picking $\Theta (\log n)$ (choice A), which forgets that actually writing out $k$ elements to the output cannot be free when $k$ can be as large as $n$.

    The question and its official answer →
42. Q.42NAT · 2 marksOfficial answer: 12
43. Q.43NAT · 2 marksOfficial answer: 2.15 to 2.18

    Computer Organization and Architecture › Pipelining

    Speedup from pipelining = (time per instruction, non-pipelined) / (time per instruction, pipelined), where each "time per instruction" = CPI × clock cycle time, and the pipelined CPI must include average stall cycles contributed by each instruction class weighted by its frequency and its own stall probability.

    WATCH OUT FOR

    Forgetting that the branch instruction fraction is the remainder (100% − 30% − 60% = 10%), not 30% again, or adding the base CPI of 1 after computing average stall cycles incorrectly instead of before multiplying by cycle time; also mixing up which processor's cycle time (0.4 ns vs 0.5 ns) goes with which CPI.

    Full solution →
44. Q.44NAT · 2 marksOfficial answer: 14

    Computer Organization and Architecture › Instructions & addressing

    Because opcodes of two different bit-lengths share one fixed-width instruction word, the decoder must be able to tell them apart just by reading bits left to right — the set of all opcodes must form a prefix-free (instantaneous) code, exactly as in Huffman/variable-length coding. Kraft's inequality $\sum 2^{-{\ell }_i}\le 1$ (equivalently, counting reserved leaf slots in a binary code-tree) then bounds how many short codewords can coexist with the given long ones.

    WATCH OUT FOR

    Treating the R-type opcode field size (4 bits) as directly giving $2^4=16$ possible R-type opcodes, ignoring that some of those 4-bit patterns must be excluded because they would otherwise be indistinguishable, as prefixes, from the 6-bit I-type opcodes sharing the same instruction word.

    Full solution →
45. Q.45NAT · 2 marksOfficial answer: 0.5
46. Q.46NAT · 2 marksOfficial answer: 55

    Programming in C › Recursion

    Each function has its OWN static variable, shared across every recursive call to that function (not per-call). fun1's static i accumulates once per call to fun1, so fun1(n) returns the running total after n more increments. fun2's static i accumulates fun1(k)'s return value at each level and is returned unchanged by every subsequent (deeper) fun2 call, since nothing decrements it afterward.

    WATCH OUT FOR

    Treating fun1's static i as reset to 0 on every fresh call from fun2 (as if it were an ordinary local variable), which makes each fun1(k) call return only k instead of the running cumulative total — this undercounts every term after the first and gives an answer far smaller than 55.

    Full solution →
47. Q.47NAT · 2 marksOfficial answer: 511

    Data Structures and Algorithms › Trees & heaps

    In a min-heap, every parent is ≤ its children, so the maximum element can only be among the leaf nodes (an internal node always has a descendant chain going down to a leaf with values ≥ it, so it can never be the largest). Finding the maximum of any set of $k$ unordered elements needs exactly $k-1$ comparisons in the best case (tournament method), and no heap-order information helps distinguish among the leaves since min-heap order says nothing about relative order among sibling subtrees.

    WATCH OUT FOR

    Assuming the maximum can be found using standard heap operations, or forgetting that in a min-heap the maximum could be any one of the leaf nodes — leading to miscounting the leaves (e.g., using floor(n/2) instead of ceil(n/2)) or forgetting the k−1 lower bound for finding a maximum among unordered elements.

    Full solution →
48. Q.48NAT · 2 marksOfficial answer: 81

    Programming in C › Pointers & arrays

    tob(b,arr) writes the binary representation of b into arr[], least-significant bit first, and returns the bit count. pp(a,b) then uses those bits to compute $a^b$ by repeated squaring: ex holds $a^{2^i}$ at loop iteration i, and it is multiplied into tot exactly when bit i of b is 1 — this is the standard fast-exponentiation-by-squaring algorithm, so pp(a,b) returns $a^b$.

    WATCH OUT FOR

    Forgetting that tob stores bits LSB-first (not MSB-first) and pairing the wrong bit with the wrong power of ex; or applying the final unused ex = ex*ex update after the loop has already produced tot, mistakenly squaring it again. Also common: stopping the trace of tob(4,arr) at i=2 instead of correctly returning i=3 (the increment happens before the loop condition is re-tested to false).

    Full solution →
49. Q.49NAT · 2 marksOfficial answer: 99

    Data Structures and Algorithms › Graph algorithms

    G is a complete graph on 100 vertices with edge weight |i-j|; since every edge weight is a positive integer ≥ 1, any spanning tree (which needs exactly n-1 = 99 edges) has weight ≥ 99, and the path v_1-v_2-...-v_100 (using only consecutive-index edges of weight 1) achieves this bound, so it is the MST with weight 99.

    WATCH OUT FOR

    Trying to compute the MST by only considering "adjacent index" edges without proving optimality, or miscounting edges (using 100 instead of 99), or assuming the MST must use edges of weight exactly matching some formula like sum of 1 to 99 rather than recognizing all path edges have weight exactly 1.

    Full solution →
50. Q.50NAT · 2 marksOfficial answer: 5.25
51. Q.51NAT · 2 marksOfficial answer: 6
52. Q.52NAT · 2 marksOfficial answer: 7
53. Q.53NAT · 2 marksOfficial answer: 154.5 to 155.5
54. Q.54NAT · 2 marksOfficial answer: 4
55. Q.55NAT · 2 marksOfficial answer: 44