GATE CSE 2023 question paper with solutions

GATE CSE 2023 answer key

General Aptitude Q.1 to Q.10

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

Computer Science and Information Technology Q.11 to Q.65

1. Q.11MCQ · 1 markOfficial answer: B
2. Q.12MCQ · 1 markOfficial answer: B

   Data Structures and Algorithms › Trees & heaps

   In a 1-indexed array max-heap, node $i$'s children sit at $2i$ and $2i+1$, and the heap property requires every parent's value to be greater than or equal to both of its children's values, everywhere in the array — checking this level by level (or bottom-up from the last internal node) is enough to rule options in or out.

   WATCH OUT FOR

   Treating the array as 0-indexed (children at $2i+1,2i+2$) instead of 1-indexed, which shifts every parent-child pair and can make a genuine violation look fine, or a valid heap look broken.

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

   Data Structures and Algorithms › Linear structures

   To unlink a node from a linked list you must update the predecessor's link field. A singly-linked node stores no back-pointer, so given only the node itself, finding its predecessor forces a scan from the head — O(n) worst case. A doubly-linked node already stores prev, so the predecessor is known instantly and unlinking (fixing prev->next and next->prev) is O(1).

   WATCH OUT FOR

   Assuming that since we're "given a pointer to the node," deletion can always be done in O(1) by copying the next node's data into the given node and deleting the next node (a common trick for other problems) — but here it must actually delete the node given (e.g., if it's the last node in an SLL, that trick fails, and worst case still requires finding the predecessor via head traversal since a plain singly-linked node has no back-link).

   Full solution →
4. Q.14MCQ · 1 markOfficial answer: C
5. Q.15MCQ · 1 markOfficial answer: A
6. Q.16MCQ · 1 markOfficial answer: A
7. Q.17MCQ · 1 markOfficial answer: B
8. Q.18MCQ · 1 markOfficial answer: B
9. Q.19MCQ · 1 markOfficial answer: C
10. Q.20MCQ · 1 markOfficial answer: C

    Data Structures and Algorithms › Sorting & hashing

    Any fixed (deterministic) hash function can be defeated by an adversary who knows it in advance: since $k>m$, by pigeonhole the adversary can always choose $k$ keys that all map to the same slot under a known fixed function, forcing worst-case $\Theta (k)$ collisions. Universal hashing defeats this by choosing the hash function randomly at run time from a well-designed family, independent of and unknown to the adversary when the keys are chosen — giving a provable expected-collision guarantee no matter what keys are picked.

    WATCH OUT FOR

    Assuming that any single, fixed hash function (division method, multiplication method, or a rule like option D that just switches between two fixed functions based on a property of k) is safe merely because it "spreads keys well on average" — an adversary who knows the fixed function in advance can always construct k > m keys that collide, regardless of how good the function looks statistically.

    Full solution →
11. Q.21MCQ · 1 markOfficial answer: B
12. Q.22MSQ · 1 markOfficial answer: B, C, D
13. Q.23MSQ · 1 markOfficial answer: C, D
14. Q.24MSQ · 1 markOfficial answer: A, C, D
15. Q.25MSQ · 1 markOfficial answer: A, C
16. Q.26MSQ · 1 markOfficial answer: B, C
17. Q.27MSQ · 1 markOfficial answer: A, C, D or C, D
18. Q.28MSQ · 1 markOfficial answer: B, D
19. Q.29MSQ · 1 markOfficial answer: A, C

    Data Structures and Algorithms › Complexity

    Compare growth rates of $f(n)=n$ and $g(n)=n^2$ using the formal definitions of $O$, $\Omega$, $o$, and $\Theta$: since $n$ grows strictly slower than $n^2$, $f$ is an upper-bounded-by (in fact strictly dominated, i.e. little-o) function of $g$, but not a lower bound, so $\Omega$ and $\Theta$ fail.

    WATCH OUT FOR

    Assuming that because $f\in O(g)$ holds, $f\in \Theta (g)$ must also hold (treating $O$ as if it already implied a tight bound), or forgetting that $o(g)$ (strict, limit-zero domination) is a stronger and still-true statement here, not something mutually exclusive with $O(g)$.

    Full solution →
20. Q.30NAT · 1 markOfficial answer: 2, or 4
21. Q.31NAT · 1 markOfficial answer: 0
22. Q.32NAT · 1 markOfficial answer: 110
23. Q.33NAT · 1 markOfficial answer: 2040

    Computer Organization and Architecture › Pipelining

    In a k-stage pipeline with no hazards, the cycle time is set by the slowest stage, and n instructions (one issued per cycle) finish in (k + n − 1) cycles — k−1 cycles to fill the pipeline plus n cycles for the n issues.

    WATCH OUT FOR

    Using the sum of all stage delays (10+20+14 = 44 ns) as the cycle time instead of the maximum stage delay (20 ns) — a pipelined cycle time is bounded by the slowest single stage, not the total latency of one instruction.

    Full solution →
24. Q.34NAT · 1 markOfficial answer: 10.2

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

    Compute the total time spent per second under each scheme (polling overhead + one keystroke-processing event per second, versus one interrupt-service event per second), express each as a fraction of a second, and take the ratio.

    WATCH OUT FOR

    Forgetting to add the 200 μs keystroke-processing time to the polling cost (giving T1 = 0.01, ratio 10.0), or forgetting that the 200 μs is added only once per second (since only one keystroke occurs per second), not per poll.

    Full solution →
25. Q.35NAT · 1 markOfficial answer: 7

    Programming in C › Functions & scope

    A static local variable inside a function keeps its value across calls (initialized only once, at first entry) and is completely distinct from any same-named variable in the calling function; only reads (never a write) of a variable elsewhere in the same full expression are safe to reason about without worrying about C's unsequenced evaluation order.

    WATCH OUT FOR

    Confusing funcp's static x with main's local x and re-computing main's x using the static variable's latest value (e.g. wrongly taking main's x as 3 during the second call instead of the 2 it was already assigned), or assuming C's unspecified evaluation order makes y = funcp() + x undefined — it is not, because x is only read here, not modified, in this expression.

    Full solution →
26. Q.36MCQ · 2 marksOfficial answer: A

    Programming in C › Recursion

    An activation (call) tree mirrors the actual sequence of function calls made during execution, nested exactly as calls are made: if function P calls Q, Q becomes a child of P's node at that call site, in left-to-right call order — it is not the same as the static call graph, and repeated/recursive calls to the same function name create separate, deeper nodes rather than being merged or flattened.

    WATCH OUT FOR

    Treating "f2 calls f3 then recursively calls f2" as if it collapses into one extra level (option B) or flattens all of f2's descendants into siblings of f2 (option D), instead of correctly nesting each recursive call one level deeper as its own node with its own children — losing track of exactly how many times f2 recurses (here once, from X=2 down to X=1) and forgetting that f3() is called again inside each new invocation of f2.

    Full solution →
27. Q.37MCQ · 2 marksOfficial answer: D
28. Q.38MCQ · 2 marksOfficial answer: C
29. Q.39MCQ · 2 marksOfficial answer: B
30. Q.40MCQ · 2 marksOfficial answer: A
31. Q.41MCQ · 2 marksOfficial answer: B

    Computer Organization and Architecture › Instructions & addressing

    Translate the C loop into the assembly skeleton line by line: the shift amount for *8 is log2(8)=3, and pointer increments in a byte-addressable memory must equal the element size (sizeof(int) = 4 bytes here), not 1.

    WATCH OUT FOR

    Picking U1 = 8 (using the multiplier itself as the shift amount) instead of log2(8) = 3, or forgetting that int is 4 bytes so the byte-addressable pointer increments (U2, U3) must be 4, not 1.

    Full solution →
32. Q.42MCQ · 2 marksOfficial answer: C

    Computer Organization and Architecture › Memory & cache

    The 10-bit Addr port of every block is fed by all address lines EXCEPT IA4 and IA3, which instead go to a 2-to-4 decoder that generates the chip-select for each block. So "starting location" (Addr port = 0) only forces the ten bus bits to 0; IA4 and IA3 are free to vary block-to-block since they only pick which block is selected — and their contribution to the 12-bit address is $2^4$ and $2^3$, not the top two (MSB) bits.

    WATCH OUT FOR

    Assuming the two lines going to the decoder must be the two MSBs (IA11, IA10), which would wrongly give offsets in multiples of 1024 (option B) — or assuming a decoder always implies a simple linear block order 0,1,2,3 (option A). The trap is that IA4 and IA3 sit in the middle of the address, not at either end, so their weight is $2^4=16$ and $2^3=8$.

    Full solution →
33. Q.43MCQ · 2 marksOfficial answer: A
34. Q.44MCQ · 2 marksOfficial answer: C
35. Q.45MCQ · 2 marksOfficial answer: C
36. Q.46MCQ · 2 marksOfficial answer: B

    Data Structures and Algorithms › Trees & heaps

    A binary (max-)heap stored as a nearly complete binary tree has height $\Theta (\log (n))$; both INSERT (sift-up from a new leaf) and EXTRACT-MAX (move last element to root, then sift-down/max-heapify) do work proportional to the tree's height, so both are $O(\log (n))$ in the worst case — reading the max itself is $O(1)$, but restoring the heap property after removing it is not.

    WATCH OUT FOR

    Assuming EXTRACT-MAX is $O(1)$ overall because "the maximum is right at the root" (options C/D) — this only covers locating/reading the max. Removing it still requires refilling the root (with the last array element) and sifting it down through up to $\Theta (\log (n))$ levels to restore the max-heap property, so the operation as a whole costs $O(\log (n))$, not $O(1)$.

    Full solution →
37. Q.47MCQ · 2 marksOfficial answer: C

    Programming in C › Recursion

    Each call to foo(p) first recurses into both children (left, then right) and only after both have returned does it compute retval = p->val + foo(left) + foo(right) and print it — so this is a post-order traversal, but what gets printed at each node is the sum of the entire subtree rooted there, not the node's own stored value.

    WATCH OUT FOR

    Assuming the printf prints the node's own value at the moment of visiting it (as in a plain post-order traversal print), giving 3 8 5 13 11 10 (option A) — instead of recognizing that retval accumulates the subtree sum before printing, since the printf statement executes only after both recursive calls have already returned and retval has already been updated.

    Full solution →
38. Q.48MCQ · 2 marksOfficial answer: D
39. Q.49MSQ · 2 marksOfficial answer: B, C, D
40. Q.50MSQ · 2 marksOfficial answer: B, C, D
41. Q.51MSQ · 2 marksOfficial answer: A, D
42. Q.52MSQ · 2 marksOfficial answer: C, D
43. Q.53MSQ · 2 marksOfficial answer: C, D
44. Q.54MSQ · 2 marksOfficial answer: A, D

    Data Structures and Algorithms › Complexity

    Trace each loop's exact iteration count rather than guessing from loop nesting depth: Function_1's outer while halves n each pass while the inner for runs the current n, giving a geometric series that sums to $\Theta (n)$ — the same order as Function_2's single pass of $100n$ iterations. Two functions of the same $\Theta$ order satisfy $\Theta$ (tight bound) and $O$ (upper bound) with each other, but never $o$ or $\omega$ (which require the ratio to actually vanish or blow up).

    WATCH OUT FOR

    Assuming Function_1's nested while+for structure must be $\Theta (n\log n)$ or $\Theta (n^2)$ just because it looks like two loops, without summing the geometric series $n+n/2+n/4+\cdots$ (which totals $\Theta (n)$, not $\Theta (n\log n)$); a second common slip is treating "same $\Theta$ order" as automatically implying little-$o$ or little-$\omega$, when those need the ratio of the two functions to tend to $0$ or $\infty$ respectively, not merely to be unequal.

    Full solution →
45. Q.55MSQ · 2 marksOfficial answer: A, B

    Data Structures and Algorithms › Design techniques

    Sequential greedy coloring always produces a proper coloring, and it never uses more than $\Delta (G)+1$ colors — but this bound is not always tight ($\Delta (G)$ alone can fail), and the actual number of colors greedy uses depends on the vertex order, so it need not equal $\chi (G)$.

    WATCH OUT FOR

    Confusing the proved greedy bound $\Delta (G)+1$ with a tighter, unproven bound of $\Delta (G)$, and assuming the greedy result equals the chromatic number $\chi (G)$ just because the algorithm is "optimal-looking" — the number of colors greedy uses is order-dependent and can exceed $\chi (G)$.

    Full solution →
46. Q.56NAT · 2 marksOfficial answer: 5040

    Data Structures and Algorithms › Graph algorithms

    $\varnothing$ is a proper subset of every one of the other 7 subsets of $U$, so in $G$ it is adjacent to all of them simultaneously. A BFS starting at $\varnothing$ therefore has only two levels: level 0 = $\{\varnothing \}$ and level 1 = all remaining 7 vertices. Since BFS's traversal order is not fixed for vertices within the same level (the specification leaves the order neighbors are discovered/enqueued unconstrained), every one of the $7!$ permutations of the 7 level-1 vertices is a valid BFS visiting order following $\varnothing$, and no further choices arise once they are enqueued (all vertices are already visited by then).

    WATCH OUT FOR

    Treating "adjacent iff proper subset" as only the Hasse-diagram cover relation (i.e., only edges to immediate subsets/supersets), which would make $\varnothing$ adjacent to just $\{1\},\{2\},\{3\}$ and force a multi-level BFS with far fewer orderings than $7!$. The problem states the FULL comparability relation ($A⊊B$ or $B⊊A$, any degree of nesting), not just cover edges, so $\varnothing$ is directly adjacent to all 7 other vertices.

    Full solution →
47. Q.57NAT · 2 marksOfficial answer: 4096
48. Q.58NAT · 2 marksOfficial answer: 5
49. Q.59NAT · 2 marksOfficial answer: 8

    Data Structures and Algorithms › Linear structures

    Simulate the stack and queue step by step exactly in the order the operations are listed, tracking the full contents (not just the top/front) so each subsequent pop/dequeue references the correct element.

    WATCH OUT FOR

    Losing track of the moving front of Q while three separate dequeue-and-push actions happen in operation VIII (mixing up which element is currently at the front of Q), or forgetting that operation III pops before operation IV dequeues, so mis-ordering the interleaving of pops/dequeues against pushes/enqueues.

    Full solution →
50. Q.60NAT · 2 marksOfficial answer: 2.374 to 2.376
51. Q.61NAT · 2 marksOfficial answer: 2
52. Q.62NAT · 2 marksOfficial answer: 6
53. Q.63NAT · 2 marksOfficial answer: 4
54. Q.64NAT · 2 marksOfficial answer: 19

    Computer Organization and Architecture › Memory & cache

    In a set-associative cache, $\text{Cache size}=\text{Number of sets}\times \text{Ways}\times \text{Block size}$, so $\text{Number of sets}\times \text{Block size}=\frac{\text{Cache size}}{\text{Ways}}$, a quantity independent of block size. Since $\text{INDEX bits}+\text{OFFSET bits}={\log }_2(\text{Number of sets}\times \text{Block size})$, this sum is fixed even though the block size itself is never stated in the question — only $\text{TAG bits}=\text{Address width}-(\text{INDEX}+\text{OFFSET})$ needs to be found, and it comes out the same for every possible block size.

    WATCH OUT FOR

    Assuming a block/line size must be given and getting stuck, or (wrongly) assuming a specific block size such as 32 or 64 bytes and computing a TAG value that depends on that unstated assumption; also forgetting to divide by the associativity (8-way) when computing the number of sets, which gives INDEX+OFFSET = 16 and TAG = 16 instead of 19.

    Full solution →
55. Q.65NAT · 2 marksOfficial answer: 3