We reached the station late, and _______ missed the train.

B. Answer: (B) nearly "nearly missed" means almost missed — the idiomatically and grammatically correct adverb here. "near" is not an adverb in this sense, and "utterly"/"mostly" do not fit.

Kind : _______ :: Often : Frequently (By word meaning)

B. Answer: GATE awarded Marks To All (MTA) for this question. "Often" and "Frequently" are synonyms. "Kind" as a noun means a sort/category, whose synonym would be "Type" (B). However, "Kind" as an adjective (benevolent) has no synonym among the options ("Cruel" is its antonym), making the analogy ambiguous. Because of this ambiguity, GATE 2023 awarded marks to all candidates.

A series of natural numbers F_1,F_2,\dots obeys F_{n+1}=F_n+F_{n-1} for all n\ge2. If F_6=37 and F_7=60, what is F_1?

A. Answer: (A) 4 Work backwards with F_{n-1}=F_{n+1}-F_n: F5 = 60-37 = 23 F4 = 37-23 = 14 F3 = 23-14 = 9 F2 = 14-9 = 5 F1 = 9-5 = 4

A survey found 90% of pregnant women received medical care at least once before birth. Of these, 60% received care from doctors, 40% from other providers. Which statement can be inferred with certainty?

A. Answer: (A) Fraction receiving care from a doctor =90\%\times60\%=54\%>50\%. So more than half of all pregnant women received care at least once from a doctor.

Looking at the surface of a smooth 3-dimensional object from the outside, which one is TRUE?

C. Answer: (C) A smooth 3D object can have both convex regions (e.g. a bump) and concave regions (e.g. a dent), so in general the surface may be concave in some places and convex in others.

Zombieland's government gives monetary incentives to those who ride bicycles to work, to address the health issues caused by lack of physical exercise. Which statement can be logically inferred with certainty?

D. Answer: (D) The government incentivizes cycling specifically to counter the lack of physical exercise, which logically means it treats cycling as a form of physical exercise. The other options overreach beyond what the passage states.

Let f(t)=0.01t^2 and g(t)=4t for 0 0, g(t)>f(t). (ii) There exists T such that f(t)>g(t) for all t>T. Which is TRUE?

C. Answer: (C) both (i) and (ii) are correct For small t, g(t)=4t exceeds f(t)=0.01t^2 (e.g. t=1: 4>0.01) -> (i) true. They cross at 0.01t^2=4t\Rightarrow t=400; beyond that the quadratic dominates the linear, so f(t)>g(t) for all t>400 -> (ii) true.

Which sentence sequence creates a coherent narrative? (i) Once on the terrace, on her way to her small room in the corner, she notices the man right away. (ii) She begins to pant by the time she has climbed all the stairs. (iii) Mina has bought vegetables and rice at the market, so her bags are heavy. (iv) He was leaning against the parapet, watching the traffic below.

D. Answer: (D) (iii), (ii), (i), (iv) (iii) sets up heavy bags, (ii) she pants climbing stairs, (i) reaching the terrace she notices the man, (iv) describes the man. Order: iii -> ii -> i -> iv.

f(x) and g(y) are functions of x and y respectively, and f(x)=g(y) for all real x and y. Which one is necessarily TRUE for all x and y?

B. Answer: (B) f(x)=g(y)= constant If f(x)=g(y) for all independent x and y, vary x with y fixed: f cannot change, so f is a constant; likewise g is a constant, and the two constants are equal. Hence both equal the same constant.

Which option best describes the transformation of the 2-D figure P to Q, and then to R, as shown?

A. Answer: (A) Comparing P to Q, the star is rotated 90 degrees clockwise (about an axis perpendicular to the page). Comparing Q to R, the figure is reflected across a horizontal line. So Operation 1 is a clockwise 90-degree rotation and Operation 2 is a horizontal reflection.

Consider statements about a compiler. S1: The front-end includes phases independent of the target hardware. S2: The back-end includes phases specific to the target hardware. S3: The back-end includes phases specific to the programming language of the source code. Identify the CORRECT option.

B. Answer: (B) Only S1 and S2 are TRUE The front-end (lexical/syntax/semantic analysis, IR generation) is machine-independent -> S1 true. The back-end (code generation, machine-specific optimization) is target-hardware specific -> S2 true. The back-end is NOT source-language specific (it works on IR) -> S3 false.

Which sequence stored at A[1..10] forms a max-heap?

B. Answer: (B) 23, 17, 14, 7, 13, 10, 1, 5, 6, 12 A max-heap requires A[i]\ge A[2i] and A[i]\ge A[2i+1]. Checking (B): 23>=17,14 | 17>=7,13 | 14>=10,1 | 7>=5,6 | 13>=12 all hold. In (A) 13<14 (A[5]<A[6])? A[2]=17\ge A[5]=13 ok, but A[3]=10<A[6]=14 fails. (C) A[5]=13<A[10]=15 fails. (D) A[2]=14<A[3]=17? root ok but A[4]=1<A[7]=16... fails. Only (B) is a valid max-heap.

SLLdel deletes a node in a singly-linked list given a pointer to the node and to the head. DLLdel does the same for a doubly-linked list. With n nodes, what is the worst-case time complexity?

D. Answer: (D) SLLdel is O(n) and DLLdel is O(1) In a singly-linked list, deleting a given node needs its predecessor; the copy-next trick works except for the last node, so the worst case is O(n) (traverse from head). In a doubly-linked list, the node has a prev pointer, so deletion adjusts prev/next in O(1).

Consider the DFA A shown over \{0,1\} with states \{s,p,q,r\}, start state s, and p the only final state. Which regular expression describes L(A)?

C. Answer: (C) 1(0+11)^* From s, only a leading 1 reaches the final state p. From p, reading a 0 keeps you in the accepting cycle, and reading 11 (via q and back) returns to p; any other symbol goes to the dead state r. So accepted strings are a 1 followed by any sequence of 0's and 11's: 1(0+11)^*.

The Lucas sequence L_n=L_{n-1}+L_{n-2} for n\ge3, with L_1=1 and L_2=3. Which is TRUE?

A. Answer: (A) The characteristic equation x^2=x+1 has roots \phi=\tfrac{1+\sqrt5}{2} and \psi=\tfrac{1-\sqrt5}{2}. The Lucas numbers have the closed form L_n=\phi^n+\psi^n. Checking: L_1=\phi+\psi=1 and L_2=\phi^2+\psi^2=3. Matches option (A).

Which one refers to the degree (arity) of a relation in relational database systems?

A. Answer: (A) Number of attributes of its relation schema The degree (arity) of a relation is the number of attributes (columns) in its schema. The number of tuples is the cardinality, not the degree.

Two hosts use Stop-and-Wait over a point-to-point link. In which scenario is link utilization the LOWEST?

B. Answer: (B) Longer link length and higher transmission rate Utilization =\dfrac{T_t}{T_t+2T_p}. It is lowest when the transmission time T_t is small relative to the propagation time T_p. Higher transmission rate reduces T_t, and longer link increases T_p — together they minimize utilization.

A and B are 4\times4 matrices where B is obtained from A by a row rearrangement (A is the circulant with first row 1,2,3,4; B with first row 3,4,1,2). Which is TRUE?

B. Answer: (B) \det(B)=-\det(A) A and B are 4\times4 matrices whose rows are the vector (1,2,3,4) arranged differently; B is obtained from A by swapping two rows (rows 1 and 3). A single row swap negates the determinant, so \det(B)=-\det(A). \det(A) is not 0 (as a circulant with first row 1,2,3,4 its eigenvalues multiply to -160), so (C) is false; (A) and (D) are also false.

Given letter -> [A-Za-z], digit -> [0-9], id -> letter (letter | digit)*, which NFA with epsilon-transitions (shown as options A-D) accepts the set of valid identifiers?

C. Answer: (C) A valid identifier matches letter (letter | digit)*. The correct NFA reads exactly one letter to reach the accepting (double-circle) state, then has an epsilon-structured loop that consumes any number of further letters or digits and returns to the accepting state. Option (C) is the automaton whose epsilon-transitions correctly implement the (letter | digit)* loop after the first letter. The others either accept the empty string or wire the epsilon-loop so it does not faithfully real

An adversary generates keys to maximize collisions in a hash table (k keys, m slots, k>m). Which is the best hashing strategy?

C. Answer: (C) Universal hashing method For any fixed hash function (division or multiplication), an adversary who knows it can choose keys that all collide. Universal hashing picks the hash function randomly from a family, so no adversary (choosing keys before the function is drawn) can force many collisions — the expected number of collisions is bounded.

The output of a 2-input multiplexer is connected back to one of its inputs (input 0), with the other input being data and S the select line, as shown. This circuit is functionally equivalent to a

B. Answer: (B) D Latch When S=1 the mux passes the data input (transparent), and when S=0 it passes the fed-back output (holds the previous value). This level-sensitive "pass when enabled, hold otherwise" behaviour is exactly a D latch (not an edge-triggered flip-flop).

Which need to be saved on a context switch from one thread T1 to another thread T2 of the SAME process?

B, C, D. Answer: (B), (C) and (D) Threads of the same process share the address space, so the page-table base register does NOT change -> (A) not needed. Each thread has its own execution context: stack pointer (B), program counter (C), and general-purpose registers (D) must be saved and restored.

Which guarantee a transition from user mode to kernel mode?

C, D. Answer: (C) and (D) A page fault is a trap handled by the kernel -> always enters kernel mode (C). A system call explicitly traps to the kernel (D). An ordinary function call stays in user mode (A); malloc is a library routine that usually runs in user space and only sometimes makes a system call, so it does not always transition (B).

Which statements are CORRECT?

A, C, D. Answer: (A), (C) and (D) Regular, recursive, and recursively enumerable languages are all closed under intersection -> (A),(C),(D) true. Context-free languages are NOT closed under intersection (e.g. a^nb^nc^n is the intersection of two CFLs but is not context-free) -> (B) false.

Which statements about OSPF are INCORRECT?

A, C. Answer: (A) and (C) OSPF is a link-state protocol that uses Dijkstra's algorithm (so B is correct, A is incorrect). OSPF is an INTRA-domain (interior gateway) protocol, not inter-domain (so C is incorrect; BGP is inter-domain). OSPF does support hierarchical routing via areas (D correct). The incorrect statements are A and C.

Geetha's conjecture is \forall x\,(P(x)\Rightarrow\exists y\,Q(x,y)). Which option(s) would imply it?

B, C. Answer: (B) and (C) - (B) \forall x\forall y\,Q(x,y) makes \exists y\,Q(x,y) true for every x, hence the conjecture holds. Implies. - (C) \exists y\forall x\,(P(x)\Rightarrow Q(x,y)): a single y works for all x, so in particular each x has such a y. Implies. - (A),(D) only assert something for SOME x, which does not establish the universally-quantified conjecture.

Which CPU scheduling algorithms can potentially cause starvation?

A, C, D. Answer: (A), (C) and (D) (the official key accepted both {A,C,D} and {C,D}) Priority scheduling can indefinitely postpone low-priority processes (C), and Shortest Job First can starve long jobs when short jobs keep arriving (D). Round Robin is starvation-free (B). FIFO serves strictly in arrival order; GATE's key accepted answers both including and excluding (A), so the marked set is {A, C, D}.

Let f(x)=x^3+15x^2-33x-36. Which statements are TRUE?

B, D. Answer: (B) and (D) f'(x)=3x^2+30x-33=3(x+11)(x-1), so critical points at x=-11,1. f''(x)=6x+30: f''(-11)=-36 local maximum at x=-11 (B); f''(1)=36>0 -> local minimum at x=1 (D).

f(n)=n and g(n)=n^2. Which statements are TRUE?

A, C. Answer: (A) and (C) n\le n^2 so f\in O(g) (A). \lim_{n\to\infty}\tfrac{n}{n^2}=0 so f\in o(g) (C), which also rules out \Omega(g) (B) and \Theta(g) (D).

Let A be the adjacency matrix of the graph shown on vertices \{1,2,3,4,5\} (note the self-loops). The value of \lambda_1+\lambda_2+\lambda_3+\lambda_4+\lambda_5 is __________

2 to 4. Answer: 2 (GATE also accepted 4) The sum of all eigenvalues equals the trace of A, i.e. the sum of its diagonal entries. The diagonal is nonzero only where a vertex has a self-loop — here vertices 3 and 4. Under the convention that a self-loop contributes 1 to the diagonal, trace =2; under the convention that an undirected self-loop contributes 2, trace =4. GATE accepted both 2 and 4.

The value of \displaystyle\int_{-3}^{3}\int_{-2}^{2}\int_{-1}^{1}(4x^2y-z^3)\,dz\,dy\,dx (rounded to nearest integer) is __________

0. Answer: 0 Integrate over z\in[-1,1]: \int_{-1}^1(4x^2y-z^3)dz=8x^2y-0=8x^2y (the odd z^3 integrates to 0). Then \int_{-2}^2 8x^2y\,dy=0 (odd in y over symmetric limits). So the whole integral is 0.

A number is written as 132 in radix-4. The same number in radix-5 is __________

110. Answer: 110 132_4=1\cdot16+3\cdot4+2=16+12+2=30. Convert 30 to base 5: 30=1\cdot25+1\cdot5+0=110_5.

A 3-stage pipeline has stage delays 10 ns, 20 ns, 14 ns. No hazards, one instruction fetched per cycle. The total execution time for 100 instructions is __________ ns

2040. Answer: 2040 Clock period =\max(10,20,14)=20 ns. Time for N instructions in a k-stage pipeline =(k+N-1)\times\text{clock}=(3+100-1)\times20=102\times20=2040 ns.

Keyboard: 1 keystroke/sec. Polling every 10 ms costs 100 us/poll; a detected key costs 200 us extra. T_1 = fraction of a second in polling+processing. Interrupts: 1 ms to service+process each keystroke; T_2 = fraction of a second. The ratio T_1/T_2 (one decimal) is __________

10.2. Answer: 10.2 Polling: 100 polls/sec \times100\,\mu s=10000\,\mu s, plus 1 keystroke \times200\,\mu s=200\,\mu s. T_1=10200\,\mu s=0.0102 s. Interrupts: 1 keystroke \times1 ms =1000\,\mu s. T_2=0.001 s. T_1/T_2=10200/1000=10.2.

The integer printed by the C program (funcp uses static int x=1; x++; return x;, called twice in main) is __________ int funcp(){ static int x = 1; x++; return x; } int main(){ int x,y; x = funcp(); y = funcp()+x; printf("%d\n", (x+y)); }

7. Answer: 7 x = funcp(): static x becomes 2, returns 2, so x=2. y = funcp()+x: static x becomes 3, returns 3, so y=3+2=5. Print x+y = 2+5 = 7.

For the given program (main calls f1(); f2(2); f3();, where f2 calls f3() then recurses), which option represents the activation tree of main?

A. Answer: (A) main calls f1, then f2(2), then f3. Inside f2(2): it first calls f3, then (since X!=1) calls f2(1); f2(1) calls f3 then f1. So under f2 the children are f3 and f2(1), and under f2(1) are f3 and f1. The activation tree with main's children {f1, f2, f3}, f2's children {f3, f2}, and the inner f2's children {f3, f1} matches option (A).

For the control flow graph shown (blocks B1-B4, with B1: i=m-1, j=n, a=10; B2: i=i+1, j=j-1; B3: a=20; B4: i=a+1), which choice lists the live variables at the EXIT of each basic block?

D. Answer: (D) B1: {a,i,j}, B2: {a,j}, B3: {a,j}, B4: {a,i,j} Compute live variables backward (a variable is live at a point if it is used later before being redefined). Tracing the uses — B4 uses a (and loops back using i,j), B2 uses i,j, B3 defines a used in B4 — gives the live-out sets B1:{a,i,j}, B2:{a,j}, B3:{a,j}, B4:{a,i,j}, matching option (D).

incr/decr each do wait(s); X=X±1; signal(s). 5 threads call incr, 3 call decr, initial X=10. I-1: s binary semaphore =1. I-2: s counting semaphore =2. V_1,V_2 are final X values. Which gives the MINIMUM possible V_1,V_2?

C. Answer: (C) 12, 7 5 threads call incr (X+1), 3 call decr (X-1); initial X=10. - I-1 (binary semaphore = 1): mutual exclusion holds, so every update applies: V_1=10+5-3=12 (fixed; its minimum is 12). - I-2 (counting semaphore = 2): up to two threads are in the critical section at once, so increments can be lost through races. Minimizing by losing increments while keeping decrements, the smallest reachable value is V_2=7. Hence (V_1,V_2)=(12,7).

Consider G: S\to aSb\mid X, X\to aX\mid Xb\mid a\mid b. Which statement is CORRECT?

B. Answer: (B) L(G)=a^*(a+b)b^* X generates a^*(a+b)b^* (any number of leading a's, one middle symbol, any number of trailing b's — at least one symbol). The rule S\to aSb wraps matched a's and b's around, but these are absorbed into the a^*\dots b^* form. So L(G)=a^*(a+b)b^*, which is regular.

The PDA P shown (states s,p,q, start s, accepts by empty stack) runs on \{a,b\}. Which language does it accept?

A. Answer: (A) \{a^m b^n \mid 1\le m \text{ and } n<m\} In state s each 'a' pushes an A (so at least one a is needed, m\ge1). Reading 'b' moves to p/q and pops one A per b. To empty the stack and accept, at least one A must still be removed by an epsilon-transition after the b's - so there must be strictly more a's than b's, i.e. n<m. Hence the language is \{a^m b^n \mid m\ge1,\ n<m\}.

For a[i]=b[i]*8 (int = 32-bit, byte-addressable), the assembly uses shl r5,r5,U1, add r3,r3,U2, add r4,r4,U3, jmp U4. Which replaces (U1,U2,U3,U4)?

B. Answer: (B) (3, 4, 4, L01) Multiplying by 8 is a left shift by 3 -> U1=3. Arrays a and b hold 32-bit ints (4 bytes), so advancing to the next element adds 4 to each base pointer -> U2=4, U3=4. The loop jumps back to the comparison at the top -> U4=L01. So (3,4,4,L01).

A 4 KB memory uses four 1 KB blocks. Address lines IA4, IA3 go to a decoder driving the chip-selects (active high); the remaining ten of IA11-IA0 go to the 10-bit address port. What are the starting addresses (IA11-IA0 in decimal) of blocks X1, X2, X3, X4?

C. Answer: (C) (0, 8, 16, 24) A block is selected by the decoder from (IA4, IA3), while its internal start (Addr=0) sets the ten address-port bits to 0. So the starting address of each block is determined solely by its (IA4,IA3) code: X1: IA4IA3=00 -> 0 X2: IA4IA3=01 -> 2^3 = 8 X3: IA4IA3=10 -> 2^4 = 16 X4: IA4IA3=11 -> 2^4+2^3 = 24

A circuit uses T, D, T flip-flops with outputs Q1, Q2, Q3 (initially 0,1,1). Which value of (Q1,Q2,Q3) can NEVER be obtained?

A. Answer: (A) (0, 0, 1) Deriving the next-state equations from the flip-flop connections and simulating the state sequence starting from (0,1,1) shows the circuit cycles through a fixed set of states. The state (0,0,1) never appears in that reachable sequence, so it can never be obtained.

Two 4-input MUXes (M1, M2) and one 2-input MUX (M3), with select lines A, B, C as shown, realize a function. Which set of inputs (X_0,\dots,X_7) realises \overline{A}+\overline{A}.C+A.\overline{B}.C?

C. Answer: (C) (1, 1, 0, 1, 1, 1, 0, 0) Simplify the target: \overline{A}+\overline{A}C+A\overline{B}C=\overline{A}+A\overline{B}C=\overline{A}+\overline{B}C. Building the truth table of F over (A,B,C) and mapping each minterm to the corresponding multiplexer data input (M3 selects between M1 and M2 via A, each selecting via B,C) assigns the input values (X_0..X_7)=(1,1,0,1,1,1,0,0), matching option (C).

IEEE-754 single precision P=\text{0xC1800000} and Q=\text{0x3F5C2EF4}. Which is P\times Q in single precision?

C. Answer: (C) 0xC15C2EF4 P=\text{0xC1800000} decodes to -1.0\times2^{4}=-16 (sign 1, exponent 131, mantissa 1.0). Multiplying Q by -16=-2^{4} just flips the sign and adds 4 to Q's exponent, leaving Q's mantissa unchanged. Q's exponent 126\to130, sign 0\to1, so the result is \text{0xC15C2EF4}.

A priority queue A is a max-heap. Extract-Max deletes the max; Insert adds a key; both preserve the heap. With n elements, the worst-case running times are

B. Answer: (B) Both O(log n) Insert appends at the end and sifts up — O(\log n). Extract-Max removes the root, moves the last element to the root, and sifts down — O(\log n). Both are O(\log n) in the worst case.

foo(p) returns p->val + foo(p->left) + foo(p->right) and prints that sum. For the binary tree shown (root 10; left subtree root 5 with children 3,8; right subtree root 11 with right child 13), what does foo print when called on the root?

C. Answer: (C) 3 8 16 13 24 50 foo computes subtree sums and prints each AFTER recursing (post-order), printing the subtree sum: foo(3)=3 -> prints 3 foo(8)=8 -> prints 8 foo(5)=5+3+8=16 -> prints 16 foo(13)=13 -> prints 13 foo(11)=11+0+13=24 -> prints 24 foo(10)=10+16+24=50 -> prints 50 Output: 3 8 16 13 24 50.

U=\{1,\dots,n\}, A,B\subseteq U with |A|=|B|=k, A\cap B=\varnothing. A permutation separates A from B if all of A precede all of B, or all of B precede all of A. How many permutations of U separate A from B?

D. Answer: (D) 2\binom{n}{2k}(n-2k)!(k!)^2 Choose the 2k positions for A\cup B: \binom{n}{2k} ways; arrange the other n-2k elements in the rest: (n-2k)!. Within the chosen 2k ordered slots, put the A-block before the B-block (or vice versa): factor 2; order the k elements of A (k!) and of B (k!). Total =2\binom{n}{2k}(n-2k)!(k!)^2.

f:A\to B is onto. Define a_1\sim a_2 if f(a_1)=f(a_2), with equivalence classes E. Define F:E\to B by F([x])=f(x). Which statements are TRUE?

B, C, D. Answer: (B), (C) and (D) F is well-defined (any two representatives of a class map to the same f-value) -> (A) false. F is onto because f is onto (B). F is injective: distinct classes have distinct f-values by construction (C). Being both injective and surjective, F is a bijection (D).

myTCP runs over 100 Mbps with RTT 150 ms and maximum segment lifetime 2 minutes. Which are valid lengths of the Sequence Number field?

B, C, D. Answer: (B), (C) and (D) The sequence number must not wrap within the maximum segment lifetime (120 s). Bytes sent in 120 s =\dfrac{100\times10^6}{8}\times120=1.5\times10^9 bytes. We need 2^{\text{bits}}\ge1.5\times10^9, i.e. bits \ge31. So 32, 34, 36 bits are valid; 30 bits (2^{30}\approx1.07\times10^9) is too small.

X is a set, 2^X its powerset, with operation A\,\Delta\,B=(A-B)\cup(B-A). H=(2^X,\Delta). Which statements are correct?

A, D. Answer: (A) and (D) \Delta (symmetric difference) is associative and commutative, the identity is \varnothing (A\,\Delta\,\varnothing=A), and each A is its own inverse since A\,\Delta\,A=\varnothing. So H is a group (A), and the inverse of A is A (D), not its complement (C).

GATE CS 2023 — All 65 Questions with Solutions

Computer Science (CS). Every question from this paper with the official answer key and a step-by-step solution. 100 marks total.

Attempt in GATE exam mode →All papers

Question 1General Aptitudemcq1 mark
We reached the station late, and _______ missed the train.
- A.
  near
- B.
  nearly
  ✓
- C.
  utterly
- D.
  mostly
Answer: B
Solution
Answer: (B) nearly "nearly missed" means almost missed — the idiomatically and grammatically correct adverb here. "near" is not an adverb in this sense, and "utterly"/"mostly" do not fit.
Question 2General Aptitudemcq1 mark
Kind : _______ :: Often : Frequently (By word meaning)
- A.
  Mean
- B.
  Type
  ✓
- C.
  Cruel
- D.
  Kindly
Answer: B
Solution
Answer: GATE awarded Marks To All (MTA) for this question. "Often" and "Frequently" are synonyms. "Kind" as a noun means a sort/category, whose synonym would be "Type" (B). However, "Kind" as an adjective (benevolent) has no synonym among the options ("Cruel" is its antonym), making the analogy ambiguous. Because of this ambiguity, GATE 2023 awarded marks to all candidates.
Question 3General Aptitudemcq1 mark
A series of natural numbers $F_{1}, F_{2}, \dots$ obeys $F_{n + 1} = F_{n} + F_{n - 1}$ for all $n \geq 2$ . If $F_{6} = 37$ and $F_{7} = 60$ , what is $F_{1}$ ?
- A.
  4
  ✓
- B.
  5
- C.
  8
- D.
  9
Answer: A
Solution
Answer: (A) 4 Work backwards with $F_{n - 1} = F_{n + 1} - F_{n}$ :
```
F5 = 60-37 = 23
F4 = 37-23 = 14
F3 = 23-14 = 9
F2 = 14-9  = 5
F1 = 9-5   = 4
```
Question 4General Aptitudemcq1 mark
A survey found 90% of pregnant women received medical care at least once before birth. Of these, 60% received care from doctors, 40% from other providers. Which statement can be inferred with certainty?
- A.
  More than half of the pregnant women received medical care at least once from a doctor.
  ✓
- B.
  Less than half of the pregnant women received medical care at least once from a doctor.
- C.
  More than half received medical care at most once from a doctor.
- D.
  Less than half received medical care at most once from a doctor.
Answer: A
Solution
Answer: (A) Fraction receiving care from a doctor $= 90% \times 60% = 54% > 50%$ . So more than half of all pregnant women received care at least once from a doctor.
Question 5General Aptitudemcq1 mark
Looking at the surface of a smooth 3-dimensional object from the outside, which one is TRUE?
- A.
  The surface must be concave everywhere.
- B.
  The surface must be convex everywhere.
- C.
  The surface may be concave in some places and convex in other places.
  ✓
- D.
  The object can have edges, but no corners.
Answer: C
Solution
Answer: (C) A smooth 3D object can have both convex regions (e.g. a bump) and concave regions (e.g. a dent), so in general the surface may be concave in some places and convex in others.
Question 6General Aptitudemcq2 marks
Zombieland's government gives monetary incentives to those who ride bicycles to work, to address the health issues caused by lack of physical exercise. Which statement can be logically inferred with certainty?
- A.
  All the working population will henceforth ride bicycles to work.
- B.
  Riding bicycles will ensure all of the working population is free of health issues.
- C.
  The health experts suggested declaring cycling mandatory.
- D.
  The Government believes that riding bicycles is a form of physical exercise.
  ✓
Answer: D
Solution
Answer: (D) The government incentivizes cycling specifically to counter the lack of physical exercise, which logically means it treats cycling as a form of physical exercise. The other options overreach beyond what the passage states.
Question 7General Aptitudemcq2 marks
Let $f (t) = 0.01 t^{2}$ and $g (t) = 4 t$ for $0 < t < \infty$ . Statements: (i) For some $t > 0$ , $g (t) > f (t)$ . (ii) There exists $T$ such that $f (t) > g (t)$ for all $t > T$ . Which is TRUE?
- A.
  only (i) is correct
- B.
  only (ii) is correct
- C.
  both (i) and (ii) are correct
  ✓
- D.
  neither (i) nor (ii) is correct
Answer: C
Solution
Answer: (C) both (i) and (ii) are correct For small $t$ , $g (t) = 4 t$ exceeds $f (t) = 0.01 t^{2}$ (e.g. $t = 1$ : $4 > 0.01$ ) -> (i) true. They cross at $0.01 t^{2} = 4 t \Rightarrow t = 400$ ; beyond that the quadratic dominates the linear, so $f (t) > g (t)$ for all $t > 400$ -> (ii) true.
Question 8General Aptitudemcq2 marks
Which sentence sequence creates a coherent narrative? (i) Once on the terrace, on her way to her small room in the corner, she notices the man right away. (ii) She begins to pant by the time she has climbed all the stairs. (iii) Mina has bought vegetables and rice at the market, so her bags are heavy. (iv) He was leaning against the parapet, watching the traffic below.
- A.
  (i), (ii), (iv), (iii)
- B.
  (ii), (iii), (i), (iv)
- C.
  (iv), (ii), (i), (iii)
- D.
  (iii), (ii), (i), (iv)
  ✓
Answer: D
Solution
Answer: (D) (iii), (ii), (i), (iv) (iii) sets up heavy bags, (ii) she pants climbing stairs, (i) reaching the terrace she notices the man, (iv) describes the man. Order: iii -> ii -> i -> iv.
Question 9General Aptitudemcq2 marks
$f (x)$ and $g (y)$ are functions of $x$ and $y$ respectively, and $f (x) = g (y)$ for all real $x$ and $y$ . Which one is necessarily TRUE for all $x$ and $y$ ?
- A.
  $f (x) = 0$ and $g (y) = 0$
- B.
  $f (x) = g (y) =$ constant
  ✓
- C.
  $f (x) =$ constant and $g (y) =$ constant (possibly different)
- D.
  $f (x) / g (y) = f (x) + g (y)$
Answer: B
Solution
Answer: (B) $f (x) = g (y) =$ constant If $f (x) = g (y)$ for all independent $x$ and $y$ , vary $x$ with $y$ fixed: $f$ cannot change, so $f$ is a constant; likewise $g$ is a constant, and the two constants are equal. Hence both equal the same constant.
Question 10General Aptitudemcq2 marks
Which option best describes the transformation of the 2-D figure P to Q, and then to R, as shown?
- A.
  Op1: Clockwise rotation by 90 deg (axis perpendicular to plane); Op2: reflection along a horizontal line
  ✓
- B.
  Op1: Counter-clockwise rotation by 90 deg; Op2: reflection along a horizontal line
- C.
  Op1: Clockwise rotation by 90 deg; Op2: reflection along a vertical line
- D.
  Op1: Counter-clockwise rotation by 180 deg; Op2: reflection along a vertical line
Answer: A
Solution
Answer: (A) Comparing P to Q, the star is rotated 90 degrees clockwise (about an axis perpendicular to the page). Comparing Q to R, the figure is reflected across a horizontal line. So Operation 1 is a clockwise 90-degree rotation and Operation 2 is a horizontal reflection.
Question 11Compiler Designmcq1 mark
Consider statements about a compiler. S1: The front-end includes phases independent of the target hardware. S2: The back-end includes phases specific to the target hardware. S3: The back-end includes phases specific to the programming language of the source code. Identify the CORRECT option.
- A.
  Only S1 is TRUE.
- B.
  Only S1 and S2 are TRUE.
  ✓
- C.
  S1, S2, and S3 are all TRUE.
- D.
  Only S1 and S3 are TRUE.
Answer: B
Solution
Answer: (B) Only S1 and S2 are TRUE The front-end (lexical/syntax/semantic analysis, IR generation) is machine-independent -> S1 true. The back-end (code generation, machine-specific optimization) is target-hardware specific -> S2 true. The back-end is NOT source-language specific (it works on IR) -> S3 false.
Question 12Programming & Data Structuresmcq1 mark
Which sequence stored at $A [1..10]$ forms a max-heap?
- A.
  23, 17, 10, 6, 13, 14, 1, 5, 7, 12
- B.
  23, 17, 14, 7, 13, 10, 1, 5, 6, 12
  ✓
- C.
  23, 17, 14, 6, 13, 10, 1, 5, 7, 15
- D.
  23, 14, 17, 1, 10, 13, 16, 12, 7, 5
Answer: B
Solution
Answer: (B) 23, 17, 14, 7, 13, 10, 1, 5, 6, 12 A max-heap requires $A [i] \geq A [2 i]$ and $A [i] \geq A [2 i + 1]$ . Checking (B):
```
23>=17,14 | 17>=7,13 | 14>=10,1 | 7>=5,6 | 13>=12
```
all hold. In (A) 13<14 (A[5]<A[6])? $A [2] = 17 \geq A [5] = 13$ ok, but $A [3] = 10 < A [6] = 14$ fails. (C) $A [5] = 13 < A [10] = 15$ fails. (D) $A [2] = 14 < A [3] = 17$ ? root ok but $A [4] = 1 < A [7] = 16$ ... fails. Only (B) is a valid max-heap.
Question 13Programming & Data Structuresmcq1 mark
SLLdel deletes a node in a singly-linked list given a pointer to the node and to the head. DLLdel does the same for a doubly-linked list. With $n$ nodes, what is the worst-case time complexity?
- A.
  SLLdel is O(1) and DLLdel is O(n)
- B.
  Both are O(log n)
- C.
  Both are O(1)
- D.
  SLLdel is O(n) and DLLdel is O(1)
  ✓
Answer: D
Solution
Answer: (D) SLLdel is O(n) and DLLdel is O(1) In a singly-linked list, deleting a given node needs its predecessor; the copy-next trick works except for the last node, so the worst case is $O (n)$ (traverse from head). In a doubly-linked list, the node has a prev pointer, so deletion adjusts prev/next in $O (1)$ .
Question 14Theory of Computationmcq1 mark
Consider the DFA $A$ shown over ${0, 1}$ with states ${s, p, q, r}$ , start state $s$ , and $p$ the only final state. Which regular expression describes $L (A)$ ?
- A.
  $1 (0^{*} 11)^{*}$
- B.
  $0 (0 + 1)^{*}$
- C.
  $1 (0 + 11)^{*}$
  ✓
- D.
  $1 (11 0^{*})^{*}$
Answer: C
Solution
Answer: (C) $1 (0 + 11)^{*}$ From $s$ , only a leading $1$ reaches the final state $p$ . From $p$ , reading a $0$ keeps you in the accepting cycle, and reading $11$ (via $q$ and back) returns to $p$ ; any other symbol goes to the dead state $r$ . So accepted strings are a $1$ followed by any sequence of $0$ 's and $11$ 's: $1 (0 + 11)^{*}$ .
Question 15Discrete Mathematicsmcq1 mark
The Lucas sequence $L_{n} = L_{n - 1} + L_{n - 2}$ for $n \geq 3$ , with $L_{1} = 1$ and $L_{2} = 3$ . Which is TRUE?
- A.
  $L_{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{2})^{n}$
  ✓
- B.
  $L_{n} = (\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{3})^{n}$
- C.
  $L_{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{3})^{n}$
- D.
  $L_{n} = (\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}$
Answer: A
Solution
Answer: (A) The characteristic equation $x^{2} = x + 1$ has roots $ϕ = \frac{1 + 5}{2}$ and $ψ = \frac{1 - 5}{2}$ . The Lucas numbers have the closed form $L_{n} = ϕ^{n} + ψ^{n}$ . Checking: $L_{1} = ϕ + ψ = 1$ and $L_{2} = ϕ^{2} + ψ^{2} = 3$ . Matches option (A).
Question 16Databasesmcq1 mark
Which one refers to the degree (arity) of a relation in relational database systems?
- A.
  Number of attributes of its relation schema.
  ✓
- B.
  Number of tuples stored in the relation.
- C.
  Number of entries in the relation.
- D.
  Number of distinct domains of its relation schema.
Answer: A
Solution
Answer: (A) Number of attributes of its relation schema The degree (arity) of a relation is the number of attributes (columns) in its schema. The number of tuples is the cardinality, not the degree.
Question 17Computer Networksmcq1 mark
Two hosts use Stop-and-Wait over a point-to-point link. In which scenario is link utilization the LOWEST?
- A.
  Longer link length and lower transmission rate
- B.
  Longer link length and higher transmission rate
  ✓
- C.
  Shorter link length and lower transmission rate
- D.
  Shorter link length and higher transmission rate
Answer: B
Solution
Answer: (B) Longer link length and higher transmission rate Utilization $= \frac{T _{t}}{T _{t} + 2 T _{p}}$ . It is lowest when the transmission time $T_{t}$ is small relative to the propagation time $T_{p}$ . Higher transmission rate reduces $T_{t}$ , and longer link increases $T_{p}$ — together they minimize utilization.
Question 18Engineering Mathematicsmcq1 mark
$A$ and $B$ are $4 \times 4$ matrices where $B$ is obtained from $A$ by a row rearrangement (A is the circulant with first row 1,2,3,4; B with first row 3,4,1,2). Which is TRUE?
- A.
  $det (A) = det (B)$
- B.
  $det (B) = - det (A)$
  ✓
- C.
  $det (A) = 0$
- D.
  $det (A B) = det (A) + det (B)$
Answer: B
Solution
Answer: (B) $det (B) = - det (A)$ $A$ and $B$ are $4 \times 4$ matrices whose rows are the vector $(1, 2, 3, 4)$ arranged differently; $B$ is obtained from $A$ by swapping two rows (rows 1 and 3). A single row swap negates the determinant, so $det (B) = - det (A)$ . $det (A)$ is not $0$ (as a circulant with first row $1, 2, 3, 4$ its eigenvalues multiply to $- 160$ ), so (C) is false; (A) and (D) are also false.
Question 19Compiler Designmcq1 mark
Given letter -> [A-Za-z], digit -> [0-9], id -> letter (letter | digit)*, which NFA with epsilon-transitions (shown as options A-D) accepts the set of valid identifiers?
- A.
  (A)
- B.
  (B)
- C.
  (C)
  ✓
- D.
  (D)
Answer: C
Solution
Answer: (C) A valid identifier matches letter (letter | digit)*. The correct NFA reads exactly one letter to reach the accepting (double-circle) state, then has an epsilon-structured loop that consumes any number of further letters or digits and returns to the accepting state. Option (C) is the automaton whose epsilon-transitions correctly implement the (letter | digit)* loop after the first letter. The others either accept the empty string or wire the epsilon-loop so it does not faithfully realize (letter | digit)*.
Question 20Algorithmsmcq1 mark
An adversary generates keys to maximize collisions in a hash table ( $k$ keys, $m$ slots, $k > m$ ). Which is the best hashing strategy?
- A.
  Division method h(k)=k mod m.
- B.
  Multiplication method.
- C.
  Universal hashing method.
  ✓
- D.
  If k is prime use Division, else Multiplication.
Answer: C
Solution
Answer: (C) Universal hashing method For any fixed hash function (division or multiplication), an adversary who knows it can choose keys that all collide. Universal hashing picks the hash function randomly from a family, so no adversary (choosing keys before the function is drawn) can force many collisions — the expected number of collisions is bounded.
Question 21Digital Logicmcq1 mark
The output of a 2-input multiplexer is connected back to one of its inputs (input 0), with the other input being data and S the select line, as shown. This circuit is functionally equivalent to a
- A.
  D Flip-flop
- B.
  D Latch
  ✓
- C.
  Half-adder
- D.
  Demultiplexer
Answer: B
Solution
Answer: (B) D Latch When $S = 1$ the mux passes the data input (transparent), and when $S = 0$ it passes the fed-back output (holds the previous value). This level-sensitive "pass when enabled, hold otherwise" behaviour is exactly a D latch (not an edge-triggered flip-flop).
Question 22Operating Systemsmsq1 mark
Which need to be saved on a context switch from one thread T1 to another thread T2 of the SAME process?
- A.
  Page table base register
- B.
  Stack pointer
  ✓
- C.
  Program counter
  ✓
- D.
  General purpose registers
  ✓
Answer: B, C, D
Solution
Answer: (B), (C) and (D) Threads of the same process share the address space, so the page-table base register does NOT change -> (A) not needed. Each thread has its own execution context: stack pointer (B), program counter (C), and general-purpose registers (D) must be saved and restored.
Question 23Operating Systemsmsq1 mark
Which guarantee a transition from user mode to kernel mode?
- A.
  Function Call
- B.
  malloc Call
- C.
  Page Fault
  ✓
- D.
  System Call
  ✓
Answer: C, D
Solution
Answer: (C) and (D) A page fault is a trap handled by the kernel -> always enters kernel mode (C). A system call explicitly traps to the kernel (D). An ordinary function call stays in user mode (A); malloc is a library routine that usually runs in user space and only sometimes makes a system call, so it does not always transition (B).
Question 24Theory of Computationmsq1 mark
Which statements are CORRECT?
- A.
  The intersection of two regular languages is regular.
  ✓
- B.
  The intersection of two context-free languages is context-free.
- C.
  The intersection of two recursive languages is recursive.
  ✓
- D.
  The intersection of two recursively enumerable languages is recursively enumerable.
  ✓
Answer: A, C, D
Solution
Answer: (A), (C) and (D) Regular, recursive, and recursively enumerable languages are all closed under intersection -> (A),(C),(D) true. Context-free languages are NOT closed under intersection (e.g. $a^{n} b^{n} c^{n}$ is the intersection of two CFLs but is not context-free) -> (B) false.
Question 25Computer Networksmsq1 mark
Which statements about OSPF are INCORRECT?
- A.
  OSPF implements Bellman-Ford algorithm to find shortest paths.
  ✓
- B.
  OSPF uses Dijkstra's shortest path algorithm.
- C.
  OSPF is used as an inter-domain routing protocol.
  ✓
- D.
  OSPF implements hierarchical routing.
Answer: A, C
Solution
Answer: (A) and (C) OSPF is a link-state protocol that uses Dijkstra's algorithm (so B is correct, A is incorrect). OSPF is an INTRA-domain (interior gateway) protocol, not inter-domain (so C is incorrect; BGP is inter-domain). OSPF does support hierarchical routing via areas (D correct). The incorrect statements are A and C.
Question 26Discrete Mathematicsmsq1 mark
Geetha's conjecture is $\forall x (P (x) \Rightarrow \exists y Q (x, y))$ . Which option(s) would imply it?
- A.
  $\exists x (P (x) \land \forall y Q (x, y))$
- B.
  $\forall x \forall y Q (x, y)$
  ✓
- C.
  $\exists y \forall x (P (x) \Rightarrow Q (x, y))$
  ✓
- D.
  $\exists x (P (x) \land \exists y Q (x, y))$
Answer: B, C
Solution
Answer: (B) and (C) - (B) $\forall x \forall y Q (x, y)$ makes $\exists y Q (x, y)$ true for every $x$ , hence the conjecture holds. Implies. - (C) $\exists y \forall x (P (x) \Rightarrow Q (x, y))$ : a single $y$ works for all $x$ , so in particular each $x$ has such a $y$ . Implies. - (A),(D) only assert something for SOME $x$ , which does not establish the universally-quantified conjecture.
Question 27Operating Systemsmsq1 mark
Which CPU scheduling algorithms can potentially cause starvation?
- A.
  First-in First-Out
  ✓
- B.
  Round Robin
- C.
  Priority Scheduling
  ✓
- D.
  Shortest Job First
  ✓
Answer: A, C, D
Solution
Answer: (A), (C) and (D) (the official key accepted both {A,C,D} and {C,D}) Priority scheduling can indefinitely postpone low-priority processes (C), and Shortest Job First can starve long jobs when short jobs keep arriving (D). Round Robin is starvation-free (B). FIFO serves strictly in arrival order; GATE's key accepted answers both including and excluding (A), so the marked set is {A, C, D}.
Question 28Engineering Mathematicsmsq1 mark
Let $f (x) = x^{3} + 15 x^{2} - 33 x - 36$ . Which statements are TRUE?
- A.
  f(x) does not have a local maximum.
- B.
  f(x) has a local maximum.
  ✓
- C.
  f(x) does not have a local minimum.
- D.
  f(x) has a local minimum.
  ✓
Answer: B, D
Solution
Answer: (B) and (D) $f^{'} (x) = 3 x^{2} + 30 x - 33 = 3 (x + 11) (x - 1)$ , so critical points at $x = - 11, 1$ . $f^{''} (x) = 6 x + 30$ : $f^{''} (- 11) = - 36 < 0$ -> local maximum at $x = - 11$ (B); $f^{''} (1) = 36 > 0$ -> local minimum at $x = 1$ (D).
Question 29Algorithmsmsq1 mark
$f (n) = n$ and $g (n) = n^{2}$ . Which statements are TRUE?
- A.
  $f \in O (g)$
  ✓
- B.
  $f \in Ω (g)$
- C.
  $f \in o (g)$
  ✓
- D.
  $f \in Θ (g)$
Answer: A, C
Solution
Answer: (A) and (C) $n \leq n^{2}$ so $f \in O (g)$ (A). $lim_{n \to \infty} \frac{n}{n ^{2}} = 0$ so $f \in o (g)$ (C), which also rules out $Ω (g)$ (B) and $Θ (g)$ (D).
Question 30Engineering Mathematicsnat1 mark
Let $A$ be the adjacency matrix of the graph shown on vertices ${1, 2, 3, 4, 5}$ (note the self-loops). The value of $λ_{1} + λ_{2} + λ_{3} + λ_{4} + λ_{5}$ is __________
Answer: 2 to 4
Solution
Answer: 2 (GATE also accepted 4) The sum of all eigenvalues equals the trace of $A$ , i.e. the sum of its diagonal entries. The diagonal is nonzero only where a vertex has a self-loop — here vertices 3 and 4. Under the convention that a self-loop contributes $1$ to the diagonal, trace $= 2$ ; under the convention that an undirected self-loop contributes $2$ , trace $= 4$ . GATE accepted both $2$ and $4$ .
Question 31Engineering Mathematicsnat1 mark
The value of $\int_{- 3}^{3} \int_{- 2}^{2} \int_{- 1}^{1} (4 x^{2} y - z^{3}) d z d y d x$ (rounded to nearest integer) is __________
Answer: 0
Solution
Answer: 0 Integrate over $z \in [- 1, 1]$ : $\int_{- 1}^{1} (4 x^{2} y - z^{3}) d z = 8 x^{2} y - 0 = 8 x^{2} y$ (the odd $z^{3}$ integrates to 0). Then $\int_{- 2}^{2} 8 x^{2} y d y = 0$ (odd in $y$ over symmetric limits). So the whole integral is $0$ .
Question 32Digital Logicnat1 mark
A number is written as 132 in radix-4. The same number in radix-5 is __________
Answer: 110
Solution
Answer: 110 $13 2_{4} = 1 \cdot 16 + 3 \cdot 4 + 2 = 16 + 12 + 2 = 30$ . Convert $30$ to base 5: $30 = 1 \cdot 25 + 1 \cdot 5 + 0 = 11 0_{5}$ .
Question 33Computer Organization & Architecturenat1 mark
A 3-stage pipeline has stage delays 10 ns, 20 ns, 14 ns. No hazards, one instruction fetched per cycle. The total execution time for 100 instructions is __________ ns
Answer: 2040
Solution
Answer: 2040 Clock period $= max (10, 20, 14) = 20$ ns. Time for $N$ instructions in a $k$ -stage pipeline $= (k + N - 1) \times clock = (3 + 100 - 1) \times 20 = 102 \times 20 = 2040$ ns.
Question 34Computer Organization & Architecturenat1 mark
Keyboard: 1 keystroke/sec. Polling every 10 ms costs 100 us/poll; a detected key costs 200 us extra. $T_{1}$ = fraction of a second in polling+processing. Interrupts: 1 ms to service+process each keystroke; $T_{2}$ = fraction of a second. The ratio $T_{1} / T_{2}$ (one decimal) is __________
Answer: 10.2
Solution
Answer: 10.2 Polling: 100 polls/sec $\times 100 μ s = 10000 μ s$ , plus 1 keystroke $\times 200 μ s = 200 μ s$ . $T_{1} = 10200 μ s = 0.0102$ s. Interrupts: 1 keystroke $\times 1$ ms $= 1000 μ s$ . $T_{2} = 0.001$ s. $T_{1} / T_{2} = 10200/1000 = 10.2$ .
Question 35Programming & Data Structuresnat1 mark
The integer printed by the C program (funcp uses static int x=1; x++; return x;, called twice in main) is __________
```
int funcp(){ static int x = 1; x++; return x; }
int main(){
   int x,y;
   x = funcp();
   y = funcp()+x;
   printf("%d\n", (x+y));
}
```
Answer: 7
Solution
Answer: 7 x = funcp(): static x becomes 2, returns 2, so x=2. y = funcp()+x: static x becomes 3, returns 3, so y=3+2=5. Print x+y = 2+5 = 7.
Question 36Compiler Designmcq2 marks
For the given program (main calls f1(); f2(2); f3();, where f2 calls f3() then recurses), which option represents the activation tree of main?
- A.
  (A)
  ✓
- B.
  (B)
- C.
  (C)
- D.
  (D)
Answer: A
Solution
Answer: (A) main calls f1, then f2(2), then f3. Inside f2(2): it first calls f3, then (since X!=1) calls f2(1); f2(1) calls f3 then f1. So under f2 the children are f3 and f2(1), and under f2(1) are f3 and f1. The activation tree with main's children {f1, f2, f3}, f2's children {f3, f2}, and the inner f2's children {f3, f1} matches option (A).
Question 37Compiler Designmcq2 marks
For the control flow graph shown (blocks B1-B4, with B1: i=m-1, j=n, a=10; B2: i=i+1, j=j-1; B3: a=20; B4: i=a+1), which choice lists the live variables at the EXIT of each basic block?
- A.
  B1: {}, B2: {a}, B3: {a}, B4: {a}
- B.
  B1: {i,j}, B2: {a}, B3: {a}, B4: {i}
- C.
  B1: {a,i,j}, B2: {a,i,j}, B3: {a,i}, B4: {a}
- D.
  B1: {a,i,j}, B2: {a,j}, B3: {a,j}, B4: {a,i,j}
  ✓
Answer: D
Solution
Answer: (D) B1: {a,i,j}, B2: {a,j}, B3: {a,j}, B4: {a,i,j} Compute live variables backward (a variable is live at a point if it is used later before being redefined). Tracing the uses — B4 uses $a$ (and loops back using $i, j$ ), B2 uses $i, j$ , B3 defines $a$ used in B4 — gives the live-out sets B1:{a,i,j}, B2:{a,j}, B3:{a,j}, B4:{a,i,j}, matching option (D).
Question 38Operating Systemsmcq2 marks
incr/decr each do wait(s); X=X±1; signal(s). 5 threads call incr, 3 call decr, initial X=10. I-1: s binary semaphore =1. I-2: s counting semaphore =2. $V_{1}, V_{2}$ are final X values. Which gives the MINIMUM possible $V_{1}, V_{2}$ ?
- A.
  15, 7
- B.
  7, 7
- C.
  12, 7
  ✓
- D.
  12, 8
Answer: C
Solution
Answer: (C) 12, 7 5 threads call incr (X+1), 3 call decr (X-1); initial X=10. - I-1 (binary semaphore = 1): mutual exclusion holds, so every update applies: $V_{1} = 10 + 5 - 3 = 12$ (fixed; its minimum is 12). - I-2 (counting semaphore = 2): up to two threads are in the critical section at once, so increments can be lost through races. Minimizing by losing increments while keeping decrements, the smallest reachable value is $V_{2} = 7$ . Hence $(V_{1}, V_{2}) = (12, 7)$ .
Question 39Theory of Computationmcq2 marks
Consider $G$ : $S \to a S b ∣ X$ , $X \to a X ∣ X b ∣ a ∣ b$ . Which statement is CORRECT?
- A.
  $L (G) = (a + b)^{*}$
- B.
  $L (G) = a^{*} (a + b) b^{*}$
  ✓
- C.
  $L (G) = a^{*} b^{*} (a + b)$
- D.
  $L (G)$ is not a regular language
Answer: B
Solution
Answer: (B) $L (G) = a^{*} (a + b) b^{*}$ $X$ generates $a^{*} (a + b) b^{*}$ (any number of leading $a$ 's, one middle symbol, any number of trailing $b$ 's — at least one symbol). The rule $S \to a S b$ wraps matched $a$ 's and $b$ 's around, but these are absorbed into the $a^{*} \dots b^{*}$ form. So $L (G) = a^{*} (a + b) b^{*}$ , which is regular.
Question 40Theory of Computationmcq2 marks
The PDA $P$ shown (states $s, p, q$ , start $s$ , accepts by empty stack) runs on ${a, b}$ . Which language does it accept?
- A.
  ${a^{m} b^{n} ∣ 1 \leq m, n < m}$
  ✓
- B.
  ${a^{m} b^{n} ∣ 0 \leq n \leq m}$
- C.
  ${a^{m} b^{n} ∣ 0 \leq m, 0 \leq n}$
- D.
  ${a^{m} ∣ 0 \leq m} \cup {b^{n} ∣ 0 \leq n}$
Answer: A
Solution
Answer: (A) ${a^{m} b^{n} ∣ 1 \leq m and n < m}$ In state $s$ each 'a' pushes an $A$ (so at least one $a$ is needed, $m \geq 1$ ). Reading 'b' moves to $p / q$ and pops one $A$ per $b$ . To empty the stack and accept, at least one $A$ must still be removed by an epsilon-transition after the $b$ 's - so there must be strictly more $a$ 's than $b$ 's, i.e. $n < m$ . Hence the language is ${a^{m} b^{n} ∣ m \geq 1, n < m}$ .
Question 41Computer Organization & Architecturemcq2 marks
For a[i]=b[i]*8 (int = 32-bit, byte-addressable), the assembly uses shl r5,r5,U1, add r3,r3,U2, add r4,r4,U3, jmp U4. Which replaces (U1,U2,U3,U4)?
- A.
  (8, 4, 1, L02)
- B.
  (3, 4, 4, L01)
  ✓
- C.
  (8, 1, 1, L02)
- D.
  (3, 1, 1, L01)
Answer: B
Solution
Answer: (B) (3, 4, 4, L01) Multiplying by 8 is a left shift by 3 -> U1=3. Arrays a and b hold 32-bit ints (4 bytes), so advancing to the next element adds 4 to each base pointer -> U2=4, U3=4. The loop jumps back to the comparison at the top -> U4=L01. So (3,4,4,L01).
Question 42Computer Organization & Architecturemcq2 marks
A 4 KB memory uses four 1 KB blocks. Address lines IA4, IA3 go to a decoder driving the chip-selects (active high); the remaining ten of IA11-IA0 go to the 10-bit address port. What are the starting addresses (IA11-IA0 in decimal) of blocks X1, X2, X3, X4?
- A.
  (0, 1, 2, 3)
- B.
  (0, 1024, 2048, 3072)
- C.
  (0, 8, 16, 24)
  ✓
- D.
  (0, 0, 0, 0)
Answer: C
Solution
Answer: (C) (0, 8, 16, 24) A block is selected by the decoder from (IA4, IA3), while its internal start (Addr=0) sets the ten address-port bits to 0. So the starting address of each block is determined solely by its (IA4,IA3) code:
```
X1: IA4IA3=00 -> 0
X2: IA4IA3=01 -> 2^3 = 8
X3: IA4IA3=10 -> 2^4 = 16
X4: IA4IA3=11 -> 2^4+2^3 = 24
```
Question 43Digital Logicmcq2 marks
A circuit uses T, D, T flip-flops with outputs Q1, Q2, Q3 (initially 0,1,1). Which value of (Q1,Q2,Q3) can NEVER be obtained?
- A.
  (0, 0, 1)
  ✓
- B.
  (1, 0, 0)
- C.
  (1, 0, 1)
- D.
  (1, 1, 1)
Answer: A
Solution
Answer: (A) (0, 0, 1) Deriving the next-state equations from the flip-flop connections and simulating the state sequence starting from $(0, 1, 1)$ shows the circuit cycles through a fixed set of states. The state $(0, 0, 1)$ never appears in that reachable sequence, so it can never be obtained.
Question 44Digital Logicmcq2 marks
Two 4-input MUXes (M1, M2) and one 2-input MUX (M3), with select lines A, B, C as shown, realize a function. Which set of inputs $(X_{0}, \dots, X_{7})$ realises $A + A . C + A . B . C$ ?
- A.
  (1, 1, 0, 0, 1, 1, 1, 0)
- B.
  (1, 1, 0, 0, 1, 1, 0, 1)
- C.
  (1, 1, 0, 1, 1, 1, 0, 0)
  ✓
- D.
  (0, 0, 1, 1, 0, 1, 1, 1)
Answer: C
Solution
Answer: (C) (1, 1, 0, 1, 1, 1, 0, 0) Simplify the target: $A + A C + A B C = A + A B C = A + B C$ . Building the truth table of $F$ over $(A, B, C)$ and mapping each minterm to the corresponding multiplexer data input (M3 selects between M1 and M2 via A, each selecting via B,C) assigns the input values $(X_{0} .. X_{7}) = (1, 1, 0, 1, 1, 1, 0, 0)$ , matching option (C).
Question 45Computer Organization & Architecturemcq2 marks
IEEE-754 single precision $P = 0xC1800000$ and $Q = 0x3F5C2EF4$ . Which is $P \times Q$ in single precision?
- A.
  0x404C2EF4
- B.
  0x405C2EF4
- C.
  0xC15C2EF4
  ✓
- D.
  0xC14C2EF4
Answer: C
Solution
Answer: (C) 0xC15C2EF4 $P = 0xC1800000$ decodes to $- 1.0 \times 2^{4} = - 16$ (sign 1, exponent 131, mantissa 1.0). Multiplying $Q$ by $- 16 = - 2^{4}$ just flips the sign and adds 4 to $Q$ 's exponent, leaving $Q$ 's mantissa unchanged. $Q$ 's exponent $126 \to 130$ , sign $0 \to 1$ , so the result is $0xC15C2EF4$ .
Question 46Programming & Data Structuresmcq2 marks
A priority queue $A$ is a max-heap. Extract-Max deletes the max; Insert adds a key; both preserve the heap. With $n$ elements, the worst-case running times are
- A.
  Both O(1).
- B.
  Both O(log n).
  ✓
- C.
  Extract-Max O(1), Insert O(n).
- D.
  Extract-Max O(1), Insert O(log n).
Answer: B
Solution
Answer: (B) Both O(log n) Insert appends at the end and sifts up — $O (lo g n)$ . Extract-Max removes the root, moves the last element to the root, and sifts down — $O (lo g n)$ . Both are $O (lo g n)$ in the worst case.
Question 47Programming & Data Structuresmcq2 marks
foo(p) returns p->val + foo(p->left) + foo(p->right) and prints that sum. For the binary tree shown (root 10; left subtree root 5 with children 3,8; right subtree root 11 with right child 13), what does foo print when called on the root?
- A.
  3 8 5 13 11 10
- B.
  3 5 8 10 11 13
- C.
  3 8 16 13 24 50
  ✓
- D.
  3 16 8 50 24 13
Answer: C
Solution
Answer: (C) 3 8 16 13 24 50 foo computes subtree sums and prints each AFTER recursing (post-order), printing the subtree sum:
```
foo(3)=3        -> prints 3
foo(8)=8        -> prints 8
foo(5)=5+3+8=16 -> prints 16
foo(13)=13      -> prints 13
foo(11)=11+0+13=24 -> prints 24
foo(10)=10+16+24=50 -> prints 50
```
Output: 3 8 16 13 24 50.
Question 48Discrete Mathematicsmcq2 marks
$U = {1, \dots, n}$ , $A, B \subseteq U$ with $∣ A ∣ = ∣ B ∣ = k$ , $A \cap B = \emptyset$ . A permutation separates A from B if all of A precede all of B, or all of B precede all of A. How many permutations of U separate A from B?
- A.
  $n!$
- B.
  $(2 k n) (n - 2 k)!$
- C.
  $(2 k n) (n - 2 k)! (k!)^{2}$
- D.
  $2 (2 k n) (n - 2 k)! (k!)^{2}$
  ✓
Answer: D
Solution
Answer: (D) $2 (2 k n) (n - 2 k)! (k!)^{2}$ Choose the $2 k$ positions for $A \cup B$ : $(2 k n)$ ways; arrange the other $n - 2 k$ elements in the rest: $(n - 2 k)!$ . Within the chosen $2 k$ ordered slots, put the $A$ -block before the $B$ -block (or vice versa): factor $2$ ; order the $k$ elements of $A$ ( $k!$ ) and of $B$ ( $k!$ ). Total $= 2 (2 k n) (n - 2 k)! (k!)^{2}$ .
Question 49Discrete Mathematicsmsq2 marks
$f : A \to B$ is onto. Define $a_{1} \sim a_{2}$ if $f (a_{1}) = f (a_{2})$ , with equivalence classes $E$ . Define $F : E \to B$ by $F ([x]) = f (x)$ . Which statements are TRUE?
- A.
  F is NOT well-defined.
- B.
  F is an onto (surjective) function.
  ✓
- C.
  F is a one-to-one (injective) function.
  ✓
- D.
  F is a bijective function.
  ✓
Answer: B, C, D
Solution
Answer: (B), (C) and (D) $F$ is well-defined (any two representatives of a class map to the same $f$ -value) -> (A) false. $F$ is onto because $f$ is onto (B). $F$ is injective: distinct classes have distinct $f$ -values by construction (C). Being both injective and surjective, $F$ is a bijection (D).
Question 50Computer Networksmsq2 marks
myTCP runs over 100 Mbps with RTT 150 ms and maximum segment lifetime 2 minutes. Which are valid lengths of the Sequence Number field?
- A.
  30 bits
- B.
  32 bits
  ✓
- C.
  34 bits
  ✓
- D.
  36 bits
  ✓
Answer: B, C, D
Solution
Answer: (B), (C) and (D) The sequence number must not wrap within the maximum segment lifetime (120 s). Bytes sent in 120 s $= \frac{100 \times 1 0 ^{6}}{8} \times 120 = 1.5 \times 1 0^{9}$ bytes. We need $2^{bits} \geq 1.5 \times 1 0^{9}$ , i.e. bits $\geq 31$ . So 32, 34, 36 bits are valid; 30 bits ( $2^{30} \approx 1.07 \times 1 0^{9}$ ) is too small.
Question 51Discrete Mathematicsmsq2 marks
$X$ is a set, $2^{X}$ its powerset, with operation $A Δ B = (A - B) \cup (B - A)$ . $H = (2^{X}, Δ)$ . Which statements are correct?
- A.
  H is a group.
  ✓
- B.
  Every element has an inverse, but H is NOT a group.
- C.
  For every A, the inverse of A is the complement of A.
- D.
  For every A, the inverse of A is A.
  ✓
Answer: A, D
Solution
Answer: (A) and (D) $Δ$ (symmetric difference) is associative and commutative, the identity is $\emptyset$ ( $A Δ \emptyset = A$ ), and each $A$ is its own inverse since $A Δ A = \emptyset$ . So $H$ is a group (A), and the inverse of $A$ is $A$ (D), not its complement (C).
Question 52Computer Networksmsq2 marks
Clicking www.gate-2023.in triggers an iterative DNS lookup over a 3-tier hierarchy (nothing cached). RTT is the same to DNS servers and to the web server. The HTML has negligible transmission/rendering time and references 10 small objects on the same server. Which are CORRECT about the minimum elapsed time to fully render?
- A.
  7 RTTs, non-persistent HTTP with 5 parallel TCP connections.
- B.
  5 RTTs, persistent HTTP with pipelining.
- C.
  9 RTTs, non-persistent HTTP with 5 parallel TCP connections.
  ✓
- D.
  6 RTTs, persistent HTTP with pipelining.
  ✓
Answer: C, D
Solution
Answer: (C) and (D) DNS (iterative, 3-tier) takes 3 RTTs (local server queries root, TLD, authoritative). Then: - Persistent HTTP with pipelining: 1 RTT for TCP handshake + 1 RTT to fetch the HTML + 1 RTT to pipeline all 10 objects $= 3$ more RTTs. Total $3 + 3 = 6$ RTTs -> (D). - Non-persistent with 5 parallel connections: 1 RTT (connect) + 1 RTT (HTML), then 10 objects in 2 rounds of 5 parallel connections, each round costing 2 RTTs (connect + fetch) $= 4$ RTTs. Total $3 + 2 + 4 = 9$ RTTs -> (C).
Question 53Engineering Mathematicsmsq2 marks
Two fair coins are tossed. A = HEAD on both; B = HEAD on first; C = HEAD on second. Which statements are TRUE?
- A.
  A and B are independent.
- B.
  A and C are independent.
- C.
  B and C are independent.
  ✓
- D.
  Prob(B|C) = Prob(B)
  ✓
Answer: C, D
Solution
Answer: (C) and (D) $P (B) = P (C) = \frac{1}{2}$ , $P (B \cap C) = \frac{1}{4} = P (B) P (C)$ -> B and C independent (C), and $P (B ∣ C) = \frac{1/4}{1/2} = \frac{1}{2} = P (B)$ (D). But $P (A \cap B) = P (H H) = \frac{1}{4} \neq = P (A) P (B) = \frac{1}{4} \cdot \frac{1}{2}$ , so A,B not independent (A false); similarly A,C not independent (B false).
Question 54Algorithmsmsq2 marks
Function 1: while n>1: for i=1..n: x++; n=floor(n/2). Function 2: for i=1..100*n: x++. $f_{1} (n), f_{2} (n)$ count the x++ executions. Which statements are TRUE?
- A.
  $f_{1} (n) \in Θ (f_{2} (n))$
  ✓
- B.
  $f_{1} (n) \in o (f_{2} (n))$
- C.
  $f_{1} (n) \in ω (f_{2} (n))$
- D.
  $f_{1} (n) \in O (n)$
  ✓
Answer: A, D
Solution
Answer: (A) and (D) $f_{1} (n) = n + ⌊ n /2 ⌋ + ⌊ n /4 ⌋ + \dots \approx 2 n = Θ (n)$ . $f_{2} (n) = 100 n = Θ (n)$ . Since both are $Θ (n)$ : $f_{1} \in Θ (f_{2})$ (A) and $f_{1} \in O (n)$ (D). They are the same order, so (B) and (C) are false.
Question 55Discrete Mathematicsmsq2 marks
Greedy coloring assigns each $v_{i}$ the smallest color not used by its already-colored neighbours. $Δ (G)$ is the maximum degree. Which statements are TRUE?
- A.
  This procedure results in a proper vertex coloring.
  ✓
- B.
  The number of colors used is at most Delta(G)+1.
  ✓
- C.
  The number of colors used is at most Delta(G).
- D.
  The number of colors used equals the chromatic number.
Answer: A, B
Solution
Answer: (A) and (B) Greedy coloring never gives two adjacent vertices the same color -> proper coloring (A). A vertex has at most $Δ (G)$ neighbours, so among colors $1, \dots, Δ (G) + 1$ at least one is free -> at most $Δ (G) + 1$ colors (B). It may use more than $Δ (G)$ and more than the chromatic number (greedy is not optimal), so (C),(D) false.
Question 56Discrete Mathematicsnat2 marks
$U = {1, 2, 3}$ , $G$ has vertex set $2^{U}$ ; $(A, B)$ is an edge iff $A \neq = B$ and ( $A ⊊ B$ or $B ⊊ A$ ). $B (A)$ is the set of BFS visit orderings from $A$ . The cardinality of $B (\emptyset)$ is __________
Answer: 5040
Solution
Answer: 5040 Starting BFS from $\emptyset$ (which is a subset of every other set, so $\emptyset$ is adjacent to all 7 other vertices), all 7 remaining vertices are at BFS level 1 and can be visited in any order. The number of orderings is $7! = 5040$ .
Question 57Operating Systemsnat2 marks
int D[128][128] is row-major; each frame holds 512 elements; 30 frames; LRU. The code does for i: for j: D[j][i]*=10 (column-major access). The number of page faults is __________
Answer: 4096
Solution
Answer: 4096 $D$ has $128 \times 128 = 16384$ elements, $512$ per frame, so $16384/512 = 32$ pages; each page holds 4 full rows (since a row is 128 elements, $512/128 = 4$ rows per page). The access pattern D[j][i] sweeps a whole column (all 128 rows) for each $i$ , touching all 32 pages each time. With only 30 frames (LRU), every access to a page that was evicted faults. The total works out to $128 \times 32 = 4096$ page faults.
Question 58Operating Systemsnat2 marks
57-bit virtual addressing, multi-level page tables with L levels, page size 4 KB, each PTE 8 bytes. The value of L is __________
Answer: 5
Solution
Answer: 5 Page offset $= lo g_{2} (4 K) = 12$ bits, so the VPN is $57 - 12 = 45$ bits. One page holds $\frac{4096}{8} = 512 = 2^{9}$ entries, so each level indexes 9 bits. Levels $= ⌈ 45/9 ⌉ = 5$ .
Question 59Programming & Data Structuresnat2 marks
Sequence $a = (1, 5, 7, 8, 9, 2)$ . Push $a_{0} .. a_{5}$ into stack S; enqueue $a_{0} .. a_{5}$ into queue Q; then: pop S, dequeue Q, pop S, dequeue Q; dequeue Q and push into S (repeat 3 times); pop S; pop S. The top element of S afterwards is __________
Answer: 8
Solution
Answer: 8 After the pushes S (top->bottom) = 2,9,8,7,5,1 and Q (front->back)=1,5,7,8,9,2.
```
pop S -> 2        (S: 9 8 7 5 1)
dequeue Q -> 1    (Q: 5 7 8 9 2)
pop S -> 9        (S: 8 7 5 1)
dequeue Q -> 5    (Q: 7 8 9 2)
dequeue+push x4: move 7,8,9,2 from Q onto S
  -> S: 2 9 8 7 8 7 5 1   (pushes 7, then 8, then 9, then 2 on top)
pop S -> 2        (S: 9 8 7 8 7 5 1)
pop S -> 9        (S: 8 7 8 7 5 1)
```
Top of S is 8.
Question 60Compiler Designnat2 marks
For the SDT computing a signed binary value (N -> I # F), the value computed for input "10#011" (rounded to three decimals) is __________
Answer: 2.374 to 2.376
Solution
Answer: 2.375 $I$ before # is the integer part "10" $= 2$ ; $F$ after # is the fraction ".011" $= 0 \cdot \frac{1}{2} + 1 \cdot \frac{1}{4} + 1 \cdot \frac{1}{8} = 0.375$ . $N . v a l = I . v a l + F . v a l = 2 + 0.375 = 2.375$ .
Question 61Databasesnat2 marks
For the Student table (rows: 1 Naman M 62, 2 Aliya F 70, 3 Aliya F 80, 4 James M 82, 5 Swati F 65), the query SELECT * FROM Student WHERE gender='F' AND marks>65 returns __________ rows
Answer: 2
Solution
Answer: 2 Female students: Aliya(70), Aliya(80), Swati(65). Of these, marks $> 65$ : Aliya(70) and Aliya(80). Swati(65) is not $> 65$ . So 2 rows.
Question 62Databasesnat2 marks
A primary-indexed ordered file has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). Block size 1024 bytes, block pointer 5 bytes. Binary search on the index takes ceil(log2 b) accesses for b index blocks. The worst-case block accesses to find the block possibly containing a key is __________
Answer: 6
Solution
Answer: 6 Records per data block $= ⌊ 1024/100 ⌋ = 10$ , so data blocks $= 25000/10 = 2500$ . A primary (sparse) index has one entry per data block; each index entry $= 15 + 5 = 20$ bytes, so entries per index block $= ⌊ 1024/20 ⌋ = 51$ . Index blocks $= ⌈ 2500/51 ⌉ = 50$ . Binary search $= ⌈ lo g_{2} 50 ⌉ = 6$ block accesses.
Question 63Theory of Computationnat2 marks
The minimum number of states in a DFA for $L = {w \in {0, 1}^{*} ∣ w$ does not contain three or more consecutive 1's $}$ is __________
Answer: 4
Solution
Answer: 4 Track the number of trailing 1's: state $q_{0}$ (0 trailing 1's / reset), $q_{1}$ (one trailing 1), $q_{2}$ (two trailing 1's) — all accepting — and a dead state $q_{d}$ reached on the third consecutive 1. That is 4 states, and they are pairwise distinguishable, so 4 is minimum.
Question 64Computer Organization & Architecturenat2 marks
An 8-way set associative cache of size 64 KB is used with a 32-bit address (TAG, INDEX, BLOCK OFFSET). The number of TAG bits is __________
Answer: 19
Solution
Answer: 19 Cache size $= 64 KB = 2^{16}$ bytes, 8-way ( $2^{3}$ ). The sets-times-block portion is $\frac{2 ^{16}}{2 ^{3}} = 2^{13}$ , so INDEX $+$ OFFSET $= 13$ bits. TAG $= 32 - 13 = 19$ bits (independent of the specific block size).
Question 65Computer Networksnat2 marks
The router's forwarding table: 200.150.0.0/16->1, 200.150.64.0/19->2, 200.150.68.0/24->3, 200.150.68.64/27->4, Default->0. A packet to 200.150.68.118 is forwarded to interface ID __________
Answer: 3
Solution
Answer: 3 Check matches (longest prefix wins):
```
/16  200.150.0.0      -> matches (iface 1)
/19  200.150.64.0     -> 68 in 64..95? yes third-octet range -> matches (iface 2)
/24  200.150.68.0     -> third octet 68 matches -> matches (iface 3)
/27  200.150.68.64    -> host range 64..95; 118 > 95 -> NO match
```
Longest matching prefix is /24 -> interface 3.

Practice the full paper with a timer

Attempt GATE CS 2023 in the exact GATE interface and get a detailed score and topic-wise analysis — free.

Create free account →