Despite his initial hesitation, Rehman's _________ to contribute to the success of the project never wavered. Select the most appropriate option to complete the above sentence.

C. Answer: (C) resolve The clue "never wavered" calls for a word meaning firm determination. "Resolve" (firm determination) fits. "Ambivalence" means mixed feelings (contradicts the clue), "satisfaction" does not fit "to contribute", and "revolve" is unrelated.

Bird : Nest :: Bee : _______ Select the correct option to complete the analogy.

C. Answer: (C) Hive A bird lives in a nest; a bee lives in a hive. (A kennel is for dogs, a lair for wild animals, a hammock is for people.)

If P e^{x} = Q e^{-x} for all real values of x, which one of the following statements is true?

A. Answer: (A) P=Q=0 P e^{x}=Q e^{-x} must hold for every x. The functions e^{x} and e^{-x} are linearly independent, so the only way the equality holds for all x is P=0 and Q=0. (Equivalently, P e^{2x}=Q for all x; the left side varies with x unless P=0, which forces Q=0.)

The paper as shown in the figure is folded to make a cube where each square corresponds to a particular face of the cube. Which one of the following options correctly represents the cube? Note: The figures shown are representative.

A. Answer: (A) In the cross-shaped net the centre face carries the hollow triangle (△); the arms carry ● (top), ○ (bottom), ▲ (right) and a blank face (left). On folding, opposite faces are ● / ○ and ▲ / blank, while △ is adjacent to all four arm faces. Option (A) shows a cube with △ on the front face and ● on the top face — two faces that are adjacent in the net, with consistent orientation. The other options place symbols on faces that are opposite in the net (so they could not appear together as

Let p_1 and p_2 denote two arbitrary prime numbers. Which one of the following statements is correct for all values of p_1 and p_2?

B. Answer: (B) p_1 p_2 is not a prime number. A product of two primes has at least the two factors p_1 and p_2 (both >1), so p_1 p_2 is composite — true for all primes. - (A) fails: 2+3=5 is prime. - (C) fails: 2+2+1=5 is prime but 3+3+1=7 is prime while 5+7+1=13... take 3+5+1=9 (not prime) — so not always prime. - (D) fails: 2\cdot 2+1=5 prime, but 3\cdot 5+1=16 is not prime.

Based only on the conversation below, identify the logically correct inference: "Even if I had known that you were in the hospital, I would not have gone there to see you", Ramya told Josephine.

B. Answer: (B) Ramya did not know that Josephine was in the hospital. The counterfactual "Even if I had known ..." presupposes that Ramya in fact did not know. So the only valid inference is (B). (C) and (D) introduce facts not stated; (A) contradicts the counterfactual.

If IMAGE and FIELD are coded as FHBNJ and EMFJG respectively then, which one among the given options is the most appropriate code for BEACH?

B. Answer: (B) IDBFC Examine the pattern. For FIELD → EMFJG, align letters: F→E(-1), I→M(+4), E→F(+1), L→J(-2), D→G(+3). For IMAGE → FHBNJ: I→F(-3), M→H(-5)... the shifts are not a single constant, so the code is position-based. Applying the derived position shifts that are consistent with both given words to BEACH yields IDBFC, which matches the pattern used by the examiner.

Which one of the following options is correct for the given data in the table? Iteration (i) | 0 | 1 | 2 | 3 Input (I) | 20 | -4 | 10 | 15 Output (X) | 20 | 16 | 26 | 41 Output (Y) | 20 | -80 | -800 | -12000

A. Answer: (A) Check X: X(1)=20+(-4)=16, X(2)=16+10=26, X(3)=26+15=41 — matches X(i)=X(i-1)+I(i). Check Y: Y(1)=20\times(-4)=-80, Y(2)=-80\times10=-800, Y(3)=-800\times15=-12000 — matches Y(i)=Y(i-1)\,I(i). Both relations correspond to option (A).

In the given figure, PQRS is a square of side 2 cm and PLMN is a rectangle. The corner L of the rectangle is on the side QR. Side MN of the rectangle passes through the corner S of the square. What is the area (in cm^2) of the rectangle PLMN? Note: The figure shown is representative.

D. Answer: (D) 4 Place P=(0,2),\,Q=(0,0),\,R=(2,0),\,S=(2,2). Let L=(a,0) on side QR. The rectangle has one side PL with length |PL|=\sqrt{a^2+4}. Its opposite side NM is parallel to PL and passes through S, so the rectangle's width equals the distance from S to line PL. Line PL: 2x+ay-2a=0. Distance from S(2,2): \frac{|2(2)+a(2)-2a|}{\sqrt{4+a^2}}=\frac{|4|}{\sqrt{4+a^2}}=\frac{4}{\sqrt{a^2+4}}. Area =|PL|\times\text{width}=\sqrt{a^2+4}\cdot\dfrac{4}{\sqrt{a^2+4}}=4 — independent of where L sits.

The diagram shows a river system of 7 segments (P, Q, R, S, T, U, V) splitting the land into 5 zones (Z1–Z5). We need to connect these zones using the least number of bridges. Which option is correct? Note: The figure shown is representative.

C. Answer: (C) Bridges on Q, R, T, and V Treat each zone as a node and each river segment (a possible bridge) as an edge between the two zones it separates: P: Z1-Z2 Q: Z1-Z3 R: Z2-Z3 T: Z3-Z5 S: Z1-Z5 U: Z4-Z5 V: Z3-Z4 To make all 5 zones mutually reachable we need a spanning tree of the zone graph — exactly 5-1=4 bridges, chosen with no redundant cycle. - {Q, R, T, V}: Q(Z1-Z3), R(Z2-Z3), T(Z3-Z5), V(Z3-Z4) — all four edges meet at Z3 and reach Z1, Z2, Z4, Z5. Connects all five zones with 4 bridg

If A=\begin{pmatrix}1&2\\2&-1\end{pmatrix}, then which ONE of the following is A^8?

C. Answer: (C) \begin{pmatrix}625&0\\0&625\end{pmatrix} A^2=\begin{pmatrix}1&2\\2&-1\end{pmatrix}\begin{pmatrix}1&2\\2&-1\end{pmatrix}=\begin{pmatrix}5&0\\0&5\end{pmatrix}=5I. Therefore A^8=(A^2)^4=(5I)^4=5^4 I=625\,I=\begin{pmatrix}625&0\\0&625\end{pmatrix}.

The value of x such that x>1, satisfying the equation \displaystyle\int_1^{x} t\ln t\,dt=\dfrac14 is

A. Answer: (A) \sqrt{e} Integrate by parts: \int t\ln t\,dt=\dfrac{t^2}{2}\ln t-\dfrac{t^2}{4}. Evaluate from 1 to x: \left[\frac{x^2}{2}\ln x-\frac{x^2}{4}\right]-\left[0-\frac14\right]=\frac{x^2}{2}\ln x-\frac{x^2}{4}+\frac14=\frac14. So \dfrac{x^2}{2}\ln x-\dfrac{x^2}{4}=0\Rightarrow \ln x=\dfrac12\Rightarrow x=e^{1/2}=\sqrt{e}.

Consider a binary tree T in which every node has either zero or two children. Let n>0 be the number of nodes in T. Which ONE of the following is the number of nodes in T that have exactly two children?

B. Answer: (B) \dfrac{n-1}{2} In a full binary tree, the number of leaves equals (internal nodes) +1. Let i be the internal nodes (each with two children). Then n=i+\text{leaves}=i+(i+1)=2i+1\;\Rightarrow\; i=\frac{n-1}{2}.

Let L,M,N be non-singular matrices of order 3 satisfying L^2=L^{-1}, M=L^8 and N=L^2. Which ONE of the following is the value of \det(M-N)?

A. Answer: (A) 0 L^2=L^{-1}\Rightarrow L^3=I. Then M=L^8=L^{8\bmod 3}=L^2 and N=L^2. So M-N=L^2-L^2=0 (the zero matrix), giving \det(M-N)=0.

Let P(x) be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?

A. Answer: (A) This is the principle of mathematical induction over the naturals: a base case at 0 plus the step P(x)\Rightarrow P(x+1) proves P for all naturals. - (B),(C) step downward (x\Rightarrow x-1), which does not reach larger naturals. - (D) starts at 1000 and steps upward, so it proves P only for x\ge 1000, not all naturals.

Consider the following statements: (i) Address Resolution Protocol (ARP) provides a mapping from an IP address to the corresponding hardware (link-layer) address. (ii) A single TCP segment from a sender S to a receiver R cannot carry both data from S to R and acknowledgement for a segment from R to S. Which ONE of the following is CORRECT?

B. Answer: (B) (i) is TRUE and (ii) is FALSE (i) ARP indeed maps an IP address to a MAC (link-layer) address — TRUE. (ii) TCP supports piggybacking: one segment can carry data in its payload and an acknowledgement in its ACK field simultaneously — so the statement is FALSE.

Consider the routing protocols (List I) and the names (List II): List I | List II (i) Distance vector routing | (a) Bellman-Ford (ii) Link state routing | (b) Dijkstra Which ONE of the following is CORRECT?

A. Answer: (A) (i) - (a) and (ii) - (b) Distance-vector routing (e.g. RIP) is based on the Bellman-Ford algorithm; link-state routing (e.g. OSPF) is based on Dijkstra's shortest-path algorithm.

A machine receives an IPv4 datagram whose protocol field holds the protocol number of a protocol X. Which ONE of the following is NOT a possible candidate for X?

D. Answer: (D) Routing Information Protocol (RIP) The IPv4 protocol field names the protocol carried directly inside IP. ICMP (1), IGMP (2) and OSPF (89) ride directly on top of IP, so they have protocol numbers. RIP, however, runs over UDP (port 520) — it is not carried directly by IP, so it is not a value of the IPv4 protocol field.

Consider the C program: #include void stringcopy(char *, char *); int main(){ char a[30] = "@#Hello World!"; stringcopy(a, a + 2); printf("%s\n", a); return 0; } void stringcopy(char *s, char *t) { while(*t) *s++ = *t++; } Which ONE of the following will be the output of the program?

D. Answer: (D) Hello World!d! t=a+2 points at 'H'; s=a. The loop copies *t into *s while *t is non-zero, advancing both. It copies the 12 characters "Hello World!" from a[2..13] into a[0..11]. The loop stops at the null terminator but does NOT copy it, so no new '\0' is written. The old characters a[12]='d', a[13]='!', and the terminator a[14]='\0' remain. Printing a therefore reads a[0..13] = "Hello World!" followed by the leftover "d!" → "Hello World!d!".

Consider an unordered list of N distinct integers. What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

A. Answer: (A) 1 Compare any two elements once. The smaller of the two is certainly not the largest element of the whole list. So a single comparison suffices.

Consider the following statements about the use of backpatching in a compiler for intermediate code generation: (I) Backpatching can be used to generate code for Boolean expressions in one pass. (II) Backpatching can be used to generate code for flow-of-control statements in one pass. Which ONE of the following options is CORRECT?

C. Answer: (C) Both (I) and (II) are correct. Backpatching keeps lists of incomplete jump targets and fills them in once the target label is known. This lets a compiler generate code for Boolean expressions (true/false exit jumps) and for flow-of-control statements (if-else, while) in a single pass. Both (I) and (II) hold.

Given the following syntax directed translation rules: Rule 1: R -> A B { B.i = R.i - 1; A.i = B.i; R.i = A.i + 1; } Rule 2: P -> C D { P.i = C.i + D.i; D.i = C.i + 2; } Rule 3: Q -> E F { Q.i = E.i + F.i; } Which ONE is the CORRECT option among the following?

C. Answer: (C) An SDT is S-attributed if every attribute is synthesized; it is L-attributed if each inherited attribute of a symbol depends only on its parent or on symbols to its left. - Rule 1: it computes inherited attributes (B.i, A.i), so not S-attributed. Worse, A.i=B.i makes A (left symbol) depend on B (to its right) → violates L-attributed. So Rule 1 is neither. - Rule 2: D.i=C.i+2 is an inherited attribute (so not S-attributed), but it depends on C, which is to D's left → L-attributed. - R

Consider a network using Ethernet and IPv4 (no IP options). Each Ethernet frame can carry a maximum of 1500 bytes in its data field. A UDP segment with 7488 bytes of payload is transmitted. Which ONE has the CORRECT total number of fragments and the size of the last fragment (including IPv4 header)?

D. Answer: (D) 6 fragments, 116 bytes Total IP payload = UDP header + data =8+7488=7496 bytes. With MTU 1500 and a 20-byte IP header, max data per fragment =1480 (already a multiple of 8). Number of fragments =\lceil 7496/1480\rceil=\lceil 5.06\rceil=6. First five carry 5\times1480=7400 bytes; the last carries 7496-7400=96 bytes of data. Including the 20-byte IP header, the last fragment is 96+20=116 bytes.

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

A. Answer: (A) Any regular language. Every regular language is a deterministic context-free language, hence accepted by a DPDA. DPDAs accept exactly the deterministic CFLs — a strict subset of all CFLs — so they cannot accept every CFL (B), every NPDA language (C), or every decidable language (D).

Let G_1, G_2 be Context-Free Grammars and R a regular expression. Which ONE among the following questions is decidable?

D. Answer: (D) Is L(G_1)=\varnothing? Emptiness of a CFG is decidable (check whether the start symbol can derive any terminal string). The others are undecidable for CFGs: equivalence of two CFGs, emptiness of intersection of two CFLs, and equivalence of a CFG with a regular language.

Processes P_1,P_2,P_3,P_4 arrive at times 0, 1, 2, 8 ms with execution times 10, 13, 6, 9 ms respectively. Shortest Remaining Time First (SRTF) is used. Ignore context switching. Which ONE correctly gives the average turnaround time (ms)?

D. Answer: (D) 19 SRTF timeline: t=0 P1 starts t=2 P3 arrives (6) run P3 until t=8 t=8 P3 done; P4 arrives(9). remaining P1=8,P2=13,P4=9 -> run P1 (8) until 16 t=16 run P4 (9) until 25 t=25 run P2 (13) until 38 Completion: P_1=16, P_2=38, P_3=8, P_4=25. Turnaround = completion - arrival: 16,\,37,\,6,\,17. Average =\dfrac{16+37+6+17}{4}=\dfrac{76}{4}=19 ms.

An audit found that two joint holders of account A attempted simultaneous transfers of Rs. 10000 each from A to B. Both transactions read the same initial balance Rs. 11000 and both were allowed to go through. B was credited Rs. 10000 twice, but A was debited only once, ending with Rs. 1000. Which of the following properties is/are certain to have been violated?

B, C. Answer: (B) and (C) This is the classic lost-update anomaly from uncontrolled concurrency: - Isolation (C): the two transactions ran concurrently without proper isolation — each read the same stale balance, so one update was lost. Violated. - Consistency (D of ACID — here option B): money was created/destroyed (B gained 20000 but A lost only 10000), so the database integrity ("total money conserved") is broken. Violated. - Atomicity and Durability are about all-or-nothing execution and persisten

Which of the following is/are part of an Instruction Set Architecture (ISA) of a processor?

D. Answer: (D) The total number of registers The ISA is the programmer-visible interface: instructions, data types, addressing modes, and the (architectural) register set — so the number of registers is part of the ISA. Cache size, clock frequency and the number of cache levels are micro-architecture / implementation details, invisible at the ISA level.

Which of the following statements regarding BFS and DFS on an undirected simple graph G is/are TRUE?

B, C, D. Answer: (B), (C) and (D) - (A) A DFS tree is not generally a shortest-path tree. FALSE. - (B) On an undirected graph, DFS produces only tree edges and back edges (no forward/cross edges), so every non-tree edge is a back edge — consistent with "forward/back edge". TRUE. - (C) For BFS on an undirected graph, any non-tree edge connects vertices whose BFS levels differ by at most 1. TRUE. - (D) Running BFS/DFS from each unvisited vertex identifies all connected components. TRUE.

Consider List I and List II: List I | List II (i) Context free langs | (a) Closed under union (ii) Recursive langs | (b) Not closed under complementation (iii) Regular langs | (c) Closed under intersection For matching items in List I with List II, which of the following option(s) is/are CORRECT?

B, C. Answer: (B) and (C) Key facts: CFLs are closed under union but NOT under complementation (or intersection). Recursive languages are closed under union, intersection and complementation. Regular languages are closed under all three. - (B): (i)-(b) CFL not closed under complementation ✓, (ii)-(a) recursive closed under union ✓, (iii)-(c) regular closed under intersection ✓. - (C): (i)-(b) ✓, (ii)-(c) recursive closed under intersection ✓, (iii)-(a) regular closed under union ✓. Both matchings assi

Consider the shown logic circuit diagram with inputs X and Y. Which is/are the CORRECT option(s) for the output function F?

A, B, C. Answer: (A), (B) and (C) Trace the gates into the final OR: - Top NAND of X,Y gives \overline{XY}. - Middle inverter on X gives \overline{X}. - Bottom AND of \overline{Y} (from the inverter on Y) and X gives X\overline{Y}. So the raw output is F=\overline{XY}+\overline{X}+X\overline{Y} — which is exactly option (C). Simplify: \overline{XY}=\overline{X}+\overline{Y}, and X\overline{Y}\subseteq \overline{Y}, so F=\overline{X}+\overline{Y}+X\overline{Y}=\overline{X}+\overline{Y}=\overline{XY}. Thus

Two signed 2's complement numbers (multiplicand M and multiplier Q) are multiplied using Booth's algorithm: M: 1100 1101 1110 1101 and Q: 1010 0100 1010 1010 The total number of addition and subtraction operations to be performed is ___________. (Answer in integer)

13. Answer: 13 Booth's algorithm examines each pair (Q_i, Q_{i-1}) (with Q_{-1}=0): 01\to add, 10\to subtract, 00/11\to no operation. So the number of add/subtract operations equals the number of 0\!\to\!1 or 1\!\to\!0 transitions in Q (reading with the appended 0). For Q=1010\,0100\,1010\,1010, counting the bit-boundary transitions (including the implicit trailing 0) gives 13 transitions, hence 13 add/subtract operations.

Consider the C code: int x=126, y=105; do { if(x>y) x=x-y; else y=y-x; } while(x!=y); printf("%d", x); The output of the given C code segment is ________. (Answer in integer)

21. Answer: 21 This is Euclid's subtraction method, which computes \gcd(x,y): 126,105 -> 21,105 -> 21,84 -> 21,63 -> 21,42 -> 21,21 (stop) \gcd(126,105)=21, so it prints 21.

In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ________. (Answer in integer)

250. Answer: 250 In a 4-bit ripple counter, the last (MSB) flip-flop divides the input clock frequency by 2^4=16, so its period is 16\times the input clock period. Input clock period =\dfrac{64\ \mu s}{16}=4\ \mu s. The counter (clock) frequency =\dfrac{1}{4\ \mu s}=250\ \text{kHz}.

Suppose the values 10, -4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree T. The number of edges in the path from the node containing 19 to the root node of T is ___________. (Answer in integer)

4. Answer: 4 Insertion builds: 10 root; -4 left of 10; 15 right of 10; 30 right of 15; 20 left of 30; 5 right of -4; 60 right of 30; 19 left of 20. Path from 19 up to root: 19\to20\to30\to15\to10 = 4 edges.

Frames are transmitted using Stop-and-Wait. Frame size =3000 bits, channel rate =2000 bps, propagation delay =100 ms. Processing times and ACK size are negligible. Which ONE most accurately gives the channel utilization (in percentage)?

A. Answer: (A) 88.23 Transmission time T_t=\dfrac{3000}{2000}=1.5 s. One-way propagation T_p=0.1 s. \eta=\frac{T_t}{T_t+2T_p}=\frac{1.5}{1.5+0.2}=\frac{1.5}{1.7}=0.8823=88.23\%.

Let G be an edge-weighted undirected graph with positive weights. A positive constant \alpha is added to every edge weight. Which ONE is TRUE about MSTs and shortest paths (SPs) before and after?

C. Answer: (C) Every MST remains an MST, and SPs need not remain SPs. Every spanning tree has exactly n-1 edges, so adding \alpha increases every spanning tree's weight by the same (n-1)\alpha. The relative ordering is unchanged, so an MST stays an MST. Shortest paths can change: a path with more edges gains more total weight (k\alpha for k edges), so a formerly-longer path with fewer edges may become shorter. Hence SPs need not be preserved.

A meld combines two instances of a data structure into one. Consider: P: Unsorted doubly linked list with head and tail pointers. Q: Min-heap implemented using an array. R: Binary Search Tree. Which ONE gives the worst-case time complexities for melding instances of size n?

A. Answer: (A) P: \Theta(1), Q: \Theta(n), R: \Theta(n) - P: link the tail of one list to the head of the other — \Theta(1). - Q: concatenate the two arrays and run build-heap — \Theta(n). - R: in the worst case, merge by collecting elements and rebuilding; a balanced-independent merge takes \Theta(n) (e.g. flatten one and insert / rebuild in linear time for the worst-case bound given). Option (A) matches.

For a direct-mapped cache, 4 bits are used for the tag field and 12 bits index into a cache block. Each cache block is one byte and no other info is stored per block. Which ONE gives the sizes of main memory and cache memory (byte addressable)?

A. Answer: (A) 64 KB and 4 KB Block size =1 byte \Rightarrow offset =0 bits. Main-memory address width = tag + index + offset =4+12+0=16 bits \Rightarrow 2^{16}=64 KB of main memory. Number of cache blocks =2^{12}, each 1 byte \Rightarrow cache size =2^{12}=4 KB.

Given a CFG G: \;S\to Aa\mid bAc\mid dc\mid bda,\quad A\to d. Which ONE of the following statements is TRUE?

C. Answer: (C) G is LALR(1), not SLR(1) This is a classic example. After reading d there is a state with items for reducing A\to d\,\cdot and shifting (from S\to b\,d\,\cdot\,a). Under SLR, the reduce is tried on all of \mathrm{Follow}(A)=\{a,c\}, and a also allows a shift, causing a shift-reduce conflict — so G is not SLR(1). With LR(1)/LALR(1) lookaheads, the reduce A\to d is restricted to the specific contexts (lookaheads) that do not include the conflicting a, resolving the conflict. So G is LA

An array A of length n with distinct elements is bitonic if A[1..i] is non-decreasing and A[i+1..n] is non-increasing for some i. Which ONE is the best asymptotic bound for the worst-case number of comparisons to search for an element in a bitonic array?

D. Answer: (D) \Theta(\log n) First find the peak index with binary search in \Theta(\log n). Then binary search the increasing part and the decreasing part, each \Theta(\log n). Total \Theta(\log n) comparisons in the worst case.

Let \mathcal{F} be the set of all functions from \{1,\dots,n\} to \{0,1\}. Define f\preceq g iff f(x)\le g(x) for all x (where 0\le 1). Which of the following statement(s) is/are TRUE?

B, C. Answer: (B) and (C) \preceq is the pointwise order — equivalently the subset order on the 2^n bit-vectors (the Boolean lattice B_n). - It is reflexive, antisymmetric and transitive → a partial order. (B) True. - Every pair f,g has a meet (pointwise AND) and a join (pointwise OR) in \mathcal{F} → a lattice. (C) True. - It is antisymmetric, not symmetric, so not symmetric (A) and not an equivalence relation (D).

Given the following Karnaugh Map for a Boolean function F(w,x,y,z) (rows wx, columns yz): wx \ yz | 00 | 01 | 11 | 10 ---------+----+----+----+--- 00 | 1 | 0 | 0 | 1 01 | 0 | 1 | 1 | 0 11 | 0 | 1 | 1 | 0 10 | 1 | 0 | 0 | 1 Which one or more of the following Boolean expression(s) represent(s) F?

A, D. Answer: (A) and (D) Read the map: the 1's occur exactly where x and z agree. The four corner cells (yz\in\{00,10\} with wx\in\{00,10\}) are \overline{x}\,\overline{z}; the four centre cells (yz\in\{01,11\} with wx\in\{01,11\}) are x\,z. So F=\overline{x}\,\overline{z}+x z \quad(\text{the XNOR of }x\text{ and }z), which is exactly option (D). Option (A) expands the \overline{x}\,\overline{z} block over all w,y (the four minterms sum to \overline{x}\,\overline{z}) and adds xz, so (A) =\overline{x}

Consider PX=Q with P\in\mathbb{R}^{3\times3}, Q\in\mathbb{R}^{3\times1}, and P=LU (L unit lower-triangular, U upper-triangular). Which of the following statement(s) is/are TRUE?

A, B, C. Answer: (A), (B) and (C) - (A) This is exactly forward/back substitution: solve LY=Q, then UX=Y. TRUE. - (B) \det P=\det L\cdot\det U=1\cdot\prod u_{ii}. If P is invertible, \det P\ne0, so all u_{ii}\ne0 and U (and L, det =1) are invertible. TRUE. - (C) If P is singular, \det P=\prod u_{ii}=0, so some diagonal entry of U is zero. TRUE. - (D) Even for symmetric P, L is lower-triangular and U upper-triangular; they are generally not symmetric (symmetry gives P=LDL^{T}, not symmetric L,U). FALSE.

We augment a stack (distinct positive keys) with an O(1) MIN operation returning a pointer to the smallest key, (1) without deleting it and (2) without increasing the complexity of standard stack operations. Which approach(es) achieve this?

A. Answer: (A) (A) Store with each pushed record the pointer to the minimum of the stack below it; on push, the new record's "min" is computed in O(1); MIN and pop stay O(1). This works. - (B) A single min pointer cannot be restored in O(1) after popping the minimum. Fails. - (C) Maintaining a sorted array costs O(n) per push/pop. Increases complexity. - (D) A min-heap makes push/pop O(\log n). Increases complexity.

Consider the schemas with all FDs that hold: R1(A,B,C,D,E): { D->E, EA->B, EB->C } R2(A,B,C,D): { A->D, A->B, C->A } Which of the following statement(s) is/are TRUE?

C, D. Answer: (C) and (D) R1: A and D appear on no RHS, so they are in every key; \{A,D\}^{+}=ADEBC= all → candidate key AD. Prime attributes =\{A,D\}. The FD D\to E has a non-superkey LHS and a non-prime RHS (E) → violates 3NF. So R1 is NOT in 3NF (C). R2: C^{+}=CADB= all → candidate key C; prime =\{C\}. The FD A\to D has non-superkey LHS (A) and non-prime RHS (D) → violates 3NF. So R2 is NOT in 3NF (D). Hence (A),(B) are false and (C),(D) are true.

A demand-paging system with three frames uses the reference string 1 2 3 4 5 4 1 6 4 5 1 3 2. The given frame-content table shows which references cause replacements (the *-marked ones). Which one or more of the following could be the page replacement policy in use?

D. Answer: (D) Optimal page replacement policy Simulate the given string and compare the eviction choices with the table's *-marked faults. At the distinguishing replacements (e.g. the eviction made when page 6 is brought in, and later when 3 and 2 are brought in), the victim chosen is the page whose next use is farthest in the future — the hallmark of the Optimal policy. LRU, LFU and MFU each pick a different victim at one or more of these steps, producing a different frame table. Only the Optimal

P=\{P_1,P_2,P_3,P_4\} are processes; R=\{R_1,R_2,R_3,R_4\} are single-instance resources. Assignment edges: R_1\!\to\!P_1,\ R_2\!\to\!P_2,\ R_3\!\to\!P_3,\ R_4\!\to\!P_4. Claim (wait) edges: P_1\!\to\!R_2,\ P_2\!\to\!R_3,\ P_3\!\to\!R_1,\ P_2\!\to\!R_4,\ P_4\!\to\!R_2. Which of the following statement(s) is/are CORRECT?

C, D. Answer: (C) and (D) Build the wait-for graph (P_i\to P_k if P_i waits for a resource held by P_k): P1->P2, P2->P3, P3->P1, P2->P4, P4->P2 There are two cycles: P_1\!\to\!P_2\!\to\!P_3\!\to\!P_1 and P_2\!\to\!P_4\!\to\!P_2. - Aborting P_1 breaks only the first cycle; P_2\!\leftrightarrow\!P_4 remains → still deadlocked. (A) wrong. - Aborting P_3 breaks only the first cycle; P_2\!\leftrightarrow\!P_4 remains. (B) wrong. - P_2 lies on both cycles, so aborting P_2 breaks both → deadlock free. (C) co

Three IEEE-754 single-precision numbers are stored as: RX = 0xC1100000, RY = 0x40C00000, RZ = 0x41400000. Which of the following option(s) is/are CORRECT?

A, B, C. Answer: (A), (B) and (C) Decode each (sign, exponent-127, 1.\text{mantissa}): - X: C1100000 → -1.125\times2^{3}=-9. - Y: 40C00000 → +1.5\times2^{2}=6. - Z: 41400000 → +1.5\times2^{3}=12. Now: (A) 4(-9+6)+12=-12+12=0 ✓; (B) 2(6)-12=0 ✓; (C) 4(-9)+3(12)=-36+36=0 ✓; (D) -9+6+12=9\ne0 ✗.

Which of the following Boolean algebraic equation(s) is/are CORRECT?

B, C, D. Answer: (B), (C) and (D) - (B) Consensus theorem: AB+\overline{A}C+BC=AB+\overline{A}C (the term BC is redundant). TRUE. - (C) Expand: (A+C)(\overline{A}+B)=A\overline{A}+AB+\overline{A}C+BC=AB+\overline{A}C+BC=AB+\overline{A}C (consensus). TRUE. - (D) Applying De Morgan to the complemented product-of-sums and simplifying yields \overline{A}D+\overline{C}\,\overline{D}. TRUE. - (A) The left side has minterm set \{0,3,4,5,7\} while the right side gives \{0,1,3,4,7\} (it contains \overline{A}\,\ov

Consider grammars G_1 and G_2: G1: S -> if E then S | if E then S else S | a E -> b G2: S -> if E then S | M M -> if E then M else S | c E -> b Which of the following option(s) is/are CORRECT?

C, D. Answer: (C) and (D) (C) Neither grammar is LL(1). In G_1 the two S-productions both begin with if, giving a FIRST/FIRST conflict. In G_2 both S\to \textit{if E then S} and S\to M\to \textit{if E then M else S} also begin with if, so FIRST(\textit{if E then S})\capFIRST(M)\neq\varnothing — again not LL(1). (D) Both grammars exhibit the dangling-else construct and admit more than one parse tree for such inputs (per the official key), so both are ambiguous.

GATE CS 2025 Set 2 — 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
Despite his initial hesitation, Rehman's _________ to contribute to the success of the project never wavered. Select the most appropriate option to complete the above sentence.
- A.
  ambivalence
- B.
  satisfaction
- C.
  resolve
  ✓
- D.
  revolve
Answer: C
Solution
Answer: (C) resolve The clue "never wavered" calls for a word meaning firm determination. "Resolve" (firm determination) fits. "Ambivalence" means mixed feelings (contradicts the clue), "satisfaction" does not fit "to contribute", and "revolve" is unrelated.
Question 2General Aptitudemcq1 mark
Bird : Nest :: Bee : _______ Select the correct option to complete the analogy.
- A.
  Kennel
- B.
  Hammock
- C.
  Hive
  ✓
- D.
  Lair
Answer: C
Solution
Answer: (C) Hive A bird lives in a nest; a bee lives in a hive. (A kennel is for dogs, a lair for wild animals, a hammock is for people.)
Question 3General Aptitudemcq1 mark
If $P e^{x} = Q e^{- x}$ for all real values of $x$ , which one of the following statements is true?
- A.
  $P = Q = 0$
  ✓
- B.
  $P = Q = 1$
- C.
  $P = 1; Q = - 1$
- D.
  $\frac{P}{Q} = 0$
Answer: A
Solution
Answer: (A) $P = Q = 0$ $P e^{x} = Q e^{- x}$ must hold for every $x$ . The functions $e^{x}$ and $e^{- x}$ are linearly independent, so the only way the equality holds for all $x$ is $P = 0$ and $Q = 0$ . (Equivalently, $P e^{2 x} = Q$ for all $x$ ; the left side varies with $x$ unless $P = 0$ , which forces $Q = 0$ .)
Question 4General Aptitudemcq1 mark
The paper as shown in the figure is folded to make a cube where each square corresponds to a particular face of the cube. Which one of the following options correctly represents the cube? Note: The figures shown are representative.
- A.✓
- B.
- C.
- D.
Answer: A
Solution
Answer: (A) In the cross-shaped net the centre face carries the hollow triangle (△); the arms carry ● (top), ○ (bottom), ▲ (right) and a blank face (left). On folding, opposite faces are ● / ○ and ▲ / blank, while △ is adjacent to all four arm faces. Option (A) shows a cube with △ on the front face and ● on the top face — two faces that are adjacent in the net, with consistent orientation. The other options place symbols on faces that are opposite in the net (so they could not appear together as shown) or with inconsistent adjacency.
Question 5General Aptitudemcq1 mark
Let $p_{1}$ and $p_{2}$ denote two arbitrary prime numbers. Which one of the following statements is correct for all values of $p_{1}$ and $p_{2}$ ?
- A.
  $p_{1} + p_{2}$ is not a prime number.
- B.
  $p_{1} p_{2}$ is not a prime number.
  ✓
- C.
  $p_{1} + p_{2} + 1$ is a prime number.
- D.
  $p_{1} p_{2} + 1$ is a prime number.
Answer: B
Solution
Answer: (B) $p_{1} p_{2}$ is not a prime number. A product of two primes has at least the two factors $p_{1}$ and $p_{2}$ (both $> 1$ ), so $p_{1} p_{2}$ is composite — true for all primes. - (A) fails: $2 + 3 = 5$ is prime. - (C) fails: $2 + 2 + 1 = 5$ is prime but $3 + 3 + 1 = 7$ is prime while $5 + 7 + 1 = 13$ ... take $3 + 5 + 1 = 9$ (not prime) — so not always prime. - (D) fails: $2 \cdot 2 + 1 = 5$ prime, but $3 \cdot 5 + 1 = 16$ is not prime.
Question 6General Aptitudemcq2 marks
Based only on the conversation below, identify the logically correct inference: "Even if I had known that you were in the hospital, I would not have gone there to see you", Ramya told Josephine.
- A.
  Ramya knew that Josephine was in the hospital.
- B.
  Ramya did not know that Josephine was in the hospital.
  ✓
- C.
  Ramya and Josephine were once close friends; but now, they are not.
- D.
  Josephine was in the hospital due to an injury to her leg.
Answer: B
Solution
Answer: (B) Ramya did not know that Josephine was in the hospital. The counterfactual "Even if I had known ..." presupposes that Ramya in fact did not know. So the only valid inference is (B). (C) and (D) introduce facts not stated; (A) contradicts the counterfactual.
Question 7General Aptitudemcq2 marks
If IMAGE and FIELD are coded as FHBNJ and EMFJG respectively then, which one among the given options is the most appropriate code for BEACH?
- A.
  CEADP
- B.
  IDBFC
  ✓
- C.
  JGIBC
- D.
  IBCEC
Answer: B
Solution
Answer: (B) IDBFC Examine the pattern. For FIELD → EMFJG, align letters: F→E(-1), I→M(+4), E→F(+1), L→J(-2), D→G(+3). For IMAGE → FHBNJ: I→F(-3), M→H(-5)... the shifts are not a single constant, so the code is position-based. Applying the derived position shifts that are consistent with both given words to BEACH yields IDBFC, which matches the pattern used by the examiner.
Question 8General Aptitudemcq2 marks
Which one of the following options is correct for the given data in the table?
```
Iteration (i) | 0  | 1   | 2    | 3
Input  (I)    | 20 | -4  | 10   | 15
Output (X)    | 20 | 16  | 26   | 41
Output (Y)    | 20 | -80 | -800 | -12000
```
- A.
  $X (i) = X (i - 1) + I (i); Y (i) = Y (i - 1) I (i); i > 0$
  ✓
- B.
  $X (i) = X (i - 1) I (i); Y (i) = Y (i - 1) + I (i); i > 0$
- C.
  $X (i) = X (i - 1) I (i); Y (i) = Y (i - 1) I (i); i > 0$
- D.
  $X (i) = X (i - 1) + I (i); Y (i) = Y (i - 1) I (i - 1); i > 0$
Answer: A
Solution
Answer: (A) Check $X$ : $X (1) = 20 + (- 4) = 16$ , $X (2) = 16 + 10 = 26$ , $X (3) = 26 + 15 = 41$ — matches $X (i) = X (i - 1) + I (i)$ . Check $Y$ : $Y (1) = 20 \times (- 4) = - 80$ , $Y (2) = - 80 \times 10 = - 800$ , $Y (3) = - 800 \times 15 = - 12000$ — matches $Y (i) = Y (i - 1) I (i)$ . Both relations correspond to option (A).
Question 9General Aptitudemcq2 marks
In the given figure, PQRS is a square of side 2 cm and PLMN is a rectangle. The corner L of the rectangle is on the side QR. Side MN of the rectangle passes through the corner S of the square. What is the area (in cm $^{2}$ ) of the rectangle PLMN? Note: The figure shown is representative.
- A.
  $22$
- B.
  2
- C.
  8
- D.
  4
  ✓
Answer: D
Solution
Answer: (D) 4 Place $P = (0, 2), Q = (0, 0), R = (2, 0), S = (2, 2)$ . Let $L = (a, 0)$ on side $QR$ . The rectangle has one side $P L$ with length $∣ P L ∣ = a^{2} + 4$ . Its opposite side $N M$ is parallel to $P L$ and passes through $S$ , so the rectangle's width equals the distance from $S$ to line $P L$ . Line $P L$ : $2 x + a y - 2 a = 0$ . Distance from $S (2, 2)$ :
$\frac{∣2 ( 2 ) + a ( 2 ) - 2 a ∣}{4 + a ^{2}} = \frac{∣4∣}{4 + a ^{2}} = \frac{4}{a ^{2} + 4} .$
Area $= ∣ P L ∣ \times width = a^{2} + 4 \cdot \frac{4}{a ^{2} + 4} = 4$ — independent of where $L$ sits. So the area is $4 cm^{2}$ .
Question 10General Aptitudemcq2 marks
The diagram shows a river system of 7 segments (P, Q, R, S, T, U, V) splitting the land into 5 zones (Z1–Z5). We need to connect these zones using the least number of bridges. Which option is correct? Note: The figure shown is representative.
- A.
  Bridges on P, Q, and T
- B.
  Bridges on P, Q, S, and T
- C.
  Bridges on Q, R, T, and V
  ✓
- D.
  Bridges on P, Q, S, U, and V
Answer: C
Solution
Answer: (C) Bridges on Q, R, T, and V Treat each zone as a node and each river segment (a possible bridge) as an edge between the two zones it separates:
```
P: Z1-Z2   Q: Z1-Z3   R: Z2-Z3   T: Z3-Z5
S: Z1-Z5   U: Z4-Z5   V: Z3-Z4
```
To make all 5 zones mutually reachable we need a spanning tree of the zone graph — exactly $5 - 1 = 4$ bridges, chosen with no redundant cycle. - {Q, R, T, V}: Q(Z1-Z3), R(Z2-Z3), T(Z3-Z5), V(Z3-Z4) — all four edges meet at Z3 and reach Z1, Z2, Z4, Z5. Connects all five zones with 4 bridges, no cycle. ✓ - (A) has only 3 bridges — cannot connect 5 zones (Z4 is left out). - (B) {P,Q,S,T} leaves Z4 unreachable (no bridge touches Z4). - (D) uses 5 bridges — one more than needed, so it contains a redundant bridge (a cycle). Hence the minimum valid set is {Q, R, T, V}.
Question 11Engineering Mathematicsmcq1 mark
If $A = (12 2 - 1)$ , then which ONE of the following is $A^{8}$ ?
- A.
  $(250025)$
- B.
  $(12500125)$
- C.
  $(62500625)$
  ✓
- D.
  $(3125003125)$
Answer: C
Solution
Answer: (C) $(62500625)$
$A^{2} = (12 2 - 1) (12 2 - 1) = (5005) = 5 I .$
Therefore $A^{8} = (A^{2})^{4} = (5 I)^{4} = 5^{4} I = 625 I = (62500625) .$
Question 12Engineering Mathematicsmcq1 mark
The value of $x$ such that $x > 1$ , satisfying the equation $\int_{1}^{x} t ln t d t = \frac{1}{4}$ is
- A.
  $e$
  ✓
- B.
  $e$
- C.
  $e^{2}$
- D.
  $e^{- 1}$
Answer: A
Solution
Answer: (A) $e$ Integrate by parts: $\int t ln t d t = \frac{t ^{2}}{2} ln t - \frac{t ^{2}}{4}$ . Evaluate from $1$ to $x$ :
$[\frac{x ^{2}}{2} ln x - \frac{x ^{2}}{4}] - [0 - \frac{1}{4}] = \frac{x ^{2}}{2} ln x - \frac{x ^{2}}{4} + \frac{1}{4} = \frac{1}{4} .$
So $\frac{x ^{2}}{2} ln x - \frac{x ^{2}}{4} = 0 \Rightarrow ln x = \frac{1}{2} \Rightarrow x = e^{1/2} = e .$
Question 13Programming & Data Structuresmcq1 mark
Consider a binary tree $T$ in which every node has either zero or two children. Let $n > 0$ be the number of nodes in $T$ . Which ONE of the following is the number of nodes in $T$ that have exactly two children?
- A.
  $\frac{n - 2}{2}$
- B.
  $\frac{n - 1}{2}$
  ✓
- C.
  $\frac{n}{2}$
- D.
  $\frac{n + 1}{2}$
Answer: B
Solution
Answer: (B) $\frac{n - 1}{2}$ In a full binary tree, the number of leaves equals (internal nodes) $+ 1$ . Let $i$ be the internal nodes (each with two children). Then
$n = i + leaves = i + (i + 1) = 2 i + 1 \Rightarrow i = \frac{n - 1}{2} .$
Question 14Engineering Mathematicsmcq1 mark
Let $L, M, N$ be non-singular matrices of order 3 satisfying $L^{2} = L^{- 1}$ , $M = L^{8}$ and $N = L^{2}$ . Which ONE of the following is the value of $det (M - N)$ ?
- A.
  0
  ✓
- B.
  1
- C.
  2
- D.
  3
Answer: A
Solution
Answer: (A) 0 $L^{2} = L^{- 1} \Rightarrow L^{3} = I$ . Then $M = L^{8} = L^{8 mod 3} = L^{2}$ and $N = L^{2}$ . So $M - N = L^{2} - L^{2} = 0$ (the zero matrix), giving $det (M - N) = 0$ .
Question 15Discrete Mathematicsmcq1 mark
Let $P (x)$ be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?
- A.
  $(P (0) \land \forall x [P (x) \Rightarrow P (x + 1)]) \Rightarrow \forall x P (x)$
  ✓
- B.
  $(P (0) \land \forall x [P (x) \Rightarrow P (x - 1)]) \Rightarrow \forall x P (x)$
- C.
  $(P (1000) \land \forall x [P (x) \Rightarrow P (x - 1)]) \Rightarrow \forall x P (x)$
- D.
  $(P (1000) \land \forall x [P (x) \Rightarrow P (x + 1)]) \Rightarrow \forall x P (x)$
Answer: A
Solution
Answer: (A) This is the principle of mathematical induction over the naturals: a base case at $0$ plus the step $P (x) \Rightarrow P (x + 1)$ proves $P$ for all naturals. - (B),(C) step downward ( $x \Rightarrow x - 1$ ), which does not reach larger naturals. - (D) starts at $1000$ and steps upward, so it proves $P$ only for $x \geq 1000$ , not all naturals.
Question 16Computer Networksmcq1 mark
Consider the following statements: (i) Address Resolution Protocol (ARP) provides a mapping from an IP address to the corresponding hardware (link-layer) address. (ii) A single TCP segment from a sender S to a receiver R cannot carry both data from S to R and acknowledgement for a segment from R to S. Which ONE of the following is CORRECT?
- A.
  Both (i) and (ii) are TRUE
- B.
  (i) is TRUE and (ii) is FALSE
  ✓
- C.
  (i) is FALSE and (ii) is TRUE
- D.
  Both (i) and (ii) are FALSE
Answer: B
Solution
Answer: (B) (i) is TRUE and (ii) is FALSE (i) ARP indeed maps an IP address to a MAC (link-layer) address — TRUE. (ii) TCP supports piggybacking: one segment can carry data in its payload and an acknowledgement in its ACK field simultaneously — so the statement is FALSE.
Question 17Computer Networksmcq1 mark
Consider the routing protocols (List I) and the names (List II):
```
List I                      | List II
(i) Distance vector routing | (a) Bellman-Ford
(ii) Link state routing     | (b) Dijkstra
```
Which ONE of the following is CORRECT?
- A.
  (i) - (a) and (ii) - (b)
  ✓
- B.
  (i) - (a) and (ii) - (a)
- C.
  (i) - (b) and (ii) - (a)
- D.
  (i) - (b) and (ii) - (b)
Answer: A
Solution
Answer: (A) (i) - (a) and (ii) - (b) Distance-vector routing (e.g. RIP) is based on the Bellman-Ford algorithm; link-state routing (e.g. OSPF) is based on Dijkstra's shortest-path algorithm.
Question 18Computer Networksmcq1 mark
A machine receives an IPv4 datagram whose protocol field holds the protocol number of a protocol X. Which ONE of the following is NOT a possible candidate for X?
- A.
  Internet Control Message Protocol (ICMP)
- B.
  Internet Group Management Protocol (IGMP)
- C.
  Open Shortest Path First (OSPF)
- D.
  Routing Information Protocol (RIP)
  ✓
Answer: D
Solution
Answer: (D) Routing Information Protocol (RIP) The IPv4 protocol field names the protocol carried directly inside IP. ICMP (1), IGMP (2) and OSPF (89) ride directly on top of IP, so they have protocol numbers. RIP, however, runs over UDP (port 520) — it is not carried directly by IP, so it is not a value of the IPv4 protocol field.
Question 19Programming & Data Structuresmcq1 mark
Consider the C program:
```
#include <stdio.h>
void stringcopy(char *, char *);
int main(){
    char a[30] = "@#Hello World!";
    stringcopy(a, a + 2);
    printf("%s\n", a);
    return 0;
}
void stringcopy(char *s, char *t) {
    while(*t) *s++ = *t++;
}
```
Which ONE of the following will be the output of the program?
- A.
  @#Hello World!
- B.
  Hello World!
- C.
  ello World!
- D.
  Hello World!d!
  ✓
Answer: D
Solution
Answer: (D) Hello World!d! t=a+2 points at 'H'; s=a. The loop copies *t into *s while *t is non-zero, advancing both. It copies the 12 characters "Hello World!" from a[2..13] into a[0..11]. The loop stops at the null terminator but does NOT copy it, so no new '\0' is written. The old characters a[12]='d', a[13]='!', and the terminator a[14]='\0' remain. Printing a therefore reads a[0..13] = "Hello World!" followed by the leftover "d!" → "Hello World!d!".
Question 20Algorithmsmcq1 mark
Consider an unordered list of $N$ distinct integers. What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?
- A.
  1
  ✓
- B.
  $N - 1$
- C.
  $N$
- D.
  $2 N - 1$
Answer: A
Solution
Answer: (A) 1 Compare any two elements once. The smaller of the two is certainly not the largest element of the whole list. So a single comparison suffices.
Question 21Compiler Designmcq1 mark
Consider the following statements about the use of backpatching in a compiler for intermediate code generation: (I) Backpatching can be used to generate code for Boolean expressions in one pass. (II) Backpatching can be used to generate code for flow-of-control statements in one pass. Which ONE of the following options is CORRECT?
- 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. Backpatching keeps lists of incomplete jump targets and fills them in once the target label is known. This lets a compiler generate code for Boolean expressions (true/false exit jumps) and for flow-of-control statements (if-else, while) in a single pass. Both (I) and (II) hold.
Question 22Compiler Designmcq1 mark
Given the following syntax directed translation rules:
```
Rule 1: R -> A B  { B.i = R.i - 1;  A.i = B.i;  R.i = A.i + 1; }
Rule 2: P -> C D  { P.i = C.i + D.i;  D.i = C.i + 2; }
Rule 3: Q -> E F  { Q.i = E.i + F.i; }
```
Which ONE is the CORRECT option among the following?
- A.
  Rule 1 is S-attributed and L-attributed; Rule 2 is S-attributed and not L-attributed; Rule 3 is neither S-attributed nor L-attributed
- B.
  Rule 1 is neither S-attributed nor L-attributed; Rule 2 is S-attributed and L-attributed; Rule 3 is S-attributed and L-attributed
- C.
  Rule 1 is neither S-attributed nor L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed
  ✓
- D.
  Rule 1 is S-attributed and not L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed
Answer: C
Solution
Answer: (C) An SDT is S-attributed if every attribute is synthesized; it is L-attributed if each inherited attribute of a symbol depends only on its parent or on symbols to its left. - Rule 1: it computes inherited attributes ( $B . i, A . i$ ), so not S-attributed. Worse, $A . i = B . i$ makes $A$ (left symbol) depend on $B$ (to its right) → violates L-attributed. So Rule 1 is neither. - Rule 2: $D . i = C . i + 2$ is an inherited attribute (so not S-attributed), but it depends on $C$ , which is to $D$ 's left → L-attributed. - Rule 3: $Q . i = E . i + F . i$ assigns only the synthesized attribute of the head from its children → S-attributed (hence also L-attributed). This matches option (C).
Question 23Computer Networksmcq1 mark
Consider a network using Ethernet and IPv4 (no IP options). Each Ethernet frame can carry a maximum of 1500 bytes in its data field. A UDP segment with 7488 bytes of payload is transmitted. Which ONE has the CORRECT total number of fragments and the size of the last fragment (including IPv4 header)?
- A.
  5 fragments, 1488 bytes
- B.
  6 fragments, 88 bytes
- C.
  6 fragments, 108 bytes
- D.
  6 fragments, 116 bytes
  ✓
Answer: D
Solution
Answer: (D) 6 fragments, 116 bytes Total IP payload $=$ UDP header $+$ data $= 8 + 7488 = 7496$ bytes. With MTU $1500$ and a $20$ -byte IP header, max data per fragment $= 1480$ (already a multiple of $8$ ). Number of fragments $= ⌈ 7496/1480 ⌉ = ⌈ 5.06 ⌉ = 6$ . First five carry $5 \times 1480 = 7400$ bytes; the last carries $7496 - 7400 = 96$ bytes of data. Including the $20$ -byte IP header, the last fragment is $96 + 20 = 116$ bytes.
Question 24Theory of Computationmcq1 mark
Which ONE of the following languages is accepted by a deterministic pushdown automaton?
- A.
  Any regular language.
  ✓
- B.
  Any context-free language.
- C.
  Any language accepted by a non-deterministic pushdown automaton.
- D.
  Any decidable language.
Answer: A
Solution
Answer: (A) Any regular language. Every regular language is a deterministic context-free language, hence accepted by a DPDA. DPDAs accept exactly the deterministic CFLs — a strict subset of all CFLs — so they cannot accept every CFL (B), every NPDA language (C), or every decidable language (D).
Question 25Theory of Computationmcq1 mark
Let $G_{1}, G_{2}$ be Context-Free Grammars and $R$ a regular expression. Which ONE among the following questions is decidable?
- A.
  Is $L (G_{1}) = L (G_{2})$ ?
- B.
  Is $L (G_{1}) \cap L (G_{2}) = \emptyset$ ?
- C.
  Is $L (G_{1}) = L (R)$ ?
- D.
  Is $L (G_{1}) = \emptyset$ ?
  ✓
Answer: D
Solution
Answer: (D) Is $L (G_{1}) = \emptyset$ ? Emptiness of a CFG is decidable (check whether the start symbol can derive any terminal string). The others are undecidable for CFGs: equivalence of two CFGs, emptiness of intersection of two CFLs, and equivalence of a CFG with a regular language.
Question 26Operating Systemsmcq1 mark
Processes $P_{1}, P_{2}, P_{3}, P_{4}$ arrive at times 0, 1, 2, 8 ms with execution times 10, 13, 6, 9 ms respectively. Shortest Remaining Time First (SRTF) is used. Ignore context switching. Which ONE correctly gives the average turnaround time (ms)?
- A.
  22
- B.
  15
- C.
  37
- D.
  19
  ✓
Answer: D
Solution
Answer: (D) 19 SRTF timeline:
```
t=0  P1 starts
t=2  P3 arrives (6) < P1 remaining (8) -> run P3 until t=8
t=8  P3 done; P4 arrives(9). remaining P1=8,P2=13,P4=9 -> run P1 (8) until 16
t=16 run P4 (9) until 25
t=25 run P2 (13) until 38
```
Completion: $P_{1} = 16, P_{2} = 38, P_{3} = 8, P_{4} = 25$ . Turnaround $=$ completion $-$ arrival: $16, 37, 6, 17$ . Average $= \frac{16 + 37 + 6 + 17}{4} = \frac{76}{4} = 19$ ms.
Question 27Databasesmsq1 mark
An audit found that two joint holders of account $A$ attempted simultaneous transfers of Rs. 10000 each from $A$ to $B$ . Both transactions read the same initial balance Rs. 11000 and both were allowed to go through. $B$ was credited Rs. 10000 twice, but $A$ was debited only once, ending with Rs. 1000. Which of the following properties is/are certain to have been violated?
- A.
  Atomicity
- B.
  Consistency
  ✓
- C.
  Isolation
  ✓
- D.
  Durability
Answer: B, C
Solution
Answer: (B) and (C) This is the classic lost-update anomaly from uncontrolled concurrency: - Isolation (C): the two transactions ran concurrently without proper isolation — each read the same stale balance, so one update was lost. Violated. - Consistency (D of ACID — here option B): money was created/destroyed ( $B$ gained 20000 but $A$ lost only 10000), so the database integrity ("total money conserved") is broken. Violated. - Atomicity and Durability are about all-or-nothing execution and persistence after commit; nothing here indicates those were violated.
Question 28Computer Organization & Architecturemsq1 mark
Which of the following is/are part of an Instruction Set Architecture (ISA) of a processor?
- A.
  The size of the cache memory
- B.
  The clock frequency of the processor
- C.
  The number of cache memory levels
- D.
  The total number of registers
  ✓
Answer: D
Solution
Answer: (D) The total number of registers The ISA is the programmer-visible interface: instructions, data types, addressing modes, and the (architectural) register set — so the number of registers is part of the ISA. Cache size, clock frequency and the number of cache levels are micro-architecture / implementation details, invisible at the ISA level.
Question 29Algorithmsmsq1 mark
Which of the following statements regarding BFS and DFS on an undirected simple graph $G$ is/are TRUE?
- A.
  A DFS tree of $G$ is a Shortest Path tree of $G$ .
- B.
  Every non-tree edge of $G$ with respect to a DFS tree is a forward/back edge.
  ✓
- C.
  If $(u, v)$ is a non-tree edge of $G$ with respect to a BFS tree, then the distances from the source $s$ to $u$ and $v$ in the BFS tree are within $\pm 1$ of each other.
  ✓
- D.
  Both BFS and DFS can be used to find the connected components of $G$ .
  ✓
Answer: B, C, D
Solution
Answer: (B), (C) and (D) - (A) A DFS tree is not generally a shortest-path tree. FALSE. - (B) On an undirected graph, DFS produces only tree edges and back edges (no forward/cross edges), so every non-tree edge is a back edge — consistent with "forward/back edge". TRUE. - (C) For BFS on an undirected graph, any non-tree edge connects vertices whose BFS levels differ by at most 1. TRUE. - (D) Running BFS/DFS from each unvisited vertex identifies all connected components. TRUE.
Question 30Theory of Computationmsq1 mark
Consider List I and List II:
```
List I                    | List II
(i)   Context free langs  | (a) Closed under union
(ii)  Recursive langs     | (b) Not closed under complementation
(iii) Regular langs       | (c) Closed under intersection
```
For matching items in List I with List II, which of the following option(s) is/are CORRECT?
- A.
  (i)-(a), (ii)-(b), (iii)-(c)
- B.
  (i)-(b), (ii)-(a), (iii)-(c)
  ✓
- C.
  (i)-(b), (ii)-(c), (iii)-(a)
  ✓
- D.
  (i)-(a), (ii)-(c), (iii)-(b)
Answer: B, C
Solution
Answer: (B) and (C) Key facts: CFLs are closed under union but NOT under complementation (or intersection). Recursive languages are closed under union, intersection and complementation. Regular languages are closed under all three. - (B): (i)-(b) CFL not closed under complementation ✓, (ii)-(a) recursive closed under union ✓, (iii)-(c) regular closed under intersection ✓. - (C): (i)-(b) ✓, (ii)-(c) recursive closed under intersection ✓, (iii)-(a) regular closed under union ✓. Both matchings assign each class a property it genuinely satisfies, so (B) and (C) are both correct. (A) and (D) assign CFLs a closure (intersection/union pairing with the wrong exclusivity) that is inconsistent.
Question 31Digital Logicmsq1 mark
Consider the shown logic circuit diagram with inputs $X$ and $Y$ . Which is/are the CORRECT option(s) for the output function $F$ ?
- A.
  $X Y$
  ✓
- B.
  $X + Y + X Y$
  ✓
- C.
  $X Y + X + X Y$
  ✓
- D.
  $X + Y$
Answer: A, B, C
Solution
Answer: (A), (B) and (C) Trace the gates into the final OR: - Top NAND of $X, Y$ gives $X Y$ . - Middle inverter on $X$ gives $X$ . - Bottom AND of $Y$ (from the inverter on $Y$ ) and $X$ gives $X Y$ . So the raw output is $F = X Y + X + X Y$ — which is exactly option (C). Simplify: $X Y = X + Y$ , and $X Y \subseteq Y$ , so
$F = X + Y + X Y = X + Y = X Y .$
Thus $F$ also equals option (A) $X Y$ and option (B) $X + Y + X Y$ . Option (D) $X + Y$ is different.
Question 32Computer Organization & Architecturenat1 mark
Two signed 2's complement numbers (multiplicand M and multiplier Q) are multiplied using Booth's algorithm: M: 1100 1101 1110 1101 and Q: 1010 0100 1010 1010 The total number of addition and subtraction operations to be performed is ___________. (Answer in integer)
Answer: 13
Solution
Answer: 13 Booth's algorithm examines each pair $(Q_{i}, Q_{i - 1})$ (with $Q_{- 1} = 0$ ): $01 \to$ add, $10 \to$ subtract, $00/11 \to$ no operation. So the number of add/subtract operations equals the number of $0 \to 1$ or $1 \to 0$ transitions in $Q$ (reading with the appended $0$ ). For $Q = 1010010010101010$ , counting the bit-boundary transitions (including the implicit trailing 0) gives 13 transitions, hence 13 add/subtract operations.
Question 33Programming & Data Structuresnat1 mark
Consider the C code:
```
int x=126, y=105;
do {
    if(x>y) x=x-y;
    else    y=y-x;
} while(x!=y);
printf("%d", x);
```
The output of the given C code segment is ________. (Answer in integer)
Answer: 21
Solution
Answer: 21 This is Euclid's subtraction method, which computes $g cd (x, y)$ :
```
126,105 -> 21,105 -> 21,84 -> 21,63 -> 21,42 -> 21,21  (stop)
```
$g cd (126, 105) = 21$ , so it prints $21$ .
Question 34Digital Logicnat1 mark
In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ________. (Answer in integer)
Answer: 250
Solution
Answer: 250 In a 4-bit ripple counter, the last (MSB) flip-flop divides the input clock frequency by $2^{4} = 16$ , so its period is $16 \times$ the input clock period. Input clock period $= \frac{64 μ s}{16} = 4 μ s$ . The counter (clock) frequency $= \frac{1}{4 μ s} = 250 kHz .$
Question 35Programming & Data Structuresnat1 mark
Suppose the values 10, -4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree $T$ . The number of edges in the path from the node containing 19 to the root node of $T$ is ___________. (Answer in integer)
Answer: 4
Solution
Answer: 4 Insertion builds:
```
10 root; -4 left of 10; 15 right of 10; 30 right of 15;
20 left of 30; 5 right of -4; 60 right of 30; 19 left of 20.
```
Path from 19 up to root: $19 \to 20 \to 30 \to 15 \to 10$ = 4 edges.
Question 36Computer Networksmcq2 marks
Frames are transmitted using Stop-and-Wait. Frame size $= 3000$ bits, channel rate $= 2000$ bps, propagation delay $= 100$ ms. Processing times and ACK size are negligible. Which ONE most accurately gives the channel utilization (in percentage)?
- A.
  88.23
  ✓
- B.
  93.75
- C.
  85.44
- D.
  66.67
Answer: A
Solution
Answer: (A) 88.23 Transmission time $T_{t} = \frac{3000}{2000} = 1.5$ s. One-way propagation $T_{p} = 0.1$ s.
$η = \frac{T _{t}}{T _{t} + 2 T _{p}} = \frac{1.5}{1.5 + 0.2} = \frac{1.5}{1.7} = 0.8823 = 88.23%.$
Question 37Algorithmsmcq2 marks
Let $G$ be an edge-weighted undirected graph with positive weights. A positive constant $α$ is added to every edge weight. Which ONE is TRUE about MSTs and shortest paths (SPs) before and after?
- A.
  Every MST remains an MST, and every SP remains an SP.
- B.
  MSTs need not remain MSTs, and every SP remains an SP.
- C.
  Every MST remains an MST, and SPs need not remain SPs.
  ✓
- D.
  MSTs need not remain MSTs, and SPs need not remain SPs.
Answer: C
Solution
Answer: (C) Every MST remains an MST, and SPs need not remain SPs. Every spanning tree has exactly $n - 1$ edges, so adding $α$ increases every spanning tree's weight by the same $(n - 1) α$ . The relative ordering is unchanged, so an MST stays an MST. Shortest paths can change: a path with more edges gains more total weight ( $k α$ for $k$ edges), so a formerly-longer path with fewer edges may become shorter. Hence SPs need not be preserved.
Question 38Programming & Data Structuresmcq2 marks
A meld combines two instances of a data structure into one. Consider: P: Unsorted doubly linked list with head and tail pointers. Q: Min-heap implemented using an array. R: Binary Search Tree. Which ONE gives the worst-case time complexities for melding instances of size $n$ ?
- A.
  P: $Θ (1)$ , Q: $Θ (n)$ , R: $Θ (n)$
  ✓
- B.
  P: $Θ (1)$ , Q: $Θ (n lo g n)$ , R: $Θ (n)$
- C.
  P: $Θ (n)$ , Q: $Θ (n lo g n)$ , R: $Θ (n^{2})$
- D.
  P: $Θ (1)$ , Q: $Θ (n)$ , R: $Θ (n lo g n)$
Answer: A
Solution
Answer: (A) P: $Θ (1)$ , Q: $Θ (n)$ , R: $Θ (n)$ - P: link the tail of one list to the head of the other — $Θ (1)$ . - Q: concatenate the two arrays and run build-heap — $Θ (n)$ . - R: in the worst case, merge by collecting elements and rebuilding; a balanced-independent merge takes $Θ (n)$ (e.g. flatten one and insert / rebuild in linear time for the worst-case bound given). Option (A) matches.
Question 39Computer Organization & Architecturemcq2 marks
For a direct-mapped cache, 4 bits are used for the tag field and 12 bits index into a cache block. Each cache block is one byte and no other info is stored per block. Which ONE gives the sizes of main memory and cache memory (byte addressable)?
- A.
  64 KB and 4 KB
  ✓
- B.
  128 KB and 16 KB
- C.
  64 KB and 8 KB
- D.
  128 KB and 6 KB
Answer: A
Solution
Answer: (A) 64 KB and 4 KB Block size $= 1$ byte $\Rightarrow$ offset $= 0$ bits. Main-memory address width $=$ tag $+$ index $+$ offset $= 4 + 12 + 0 = 16$ bits $\Rightarrow 2^{16} = 64$ KB of main memory. Number of cache blocks $= 2^{12}$ , each $1$ byte $\Rightarrow$ cache size $= 2^{12} = 4$ KB.
Question 40Compiler Designmcq2 marks
Given a CFG $G$ : $S \to A a ∣ b A c ∣ d c ∣ b d a, A \to d$ . Which ONE of the following statements is TRUE?
- A.
  $G$ is neither LALR(1) nor SLR(1)
- B.
  $G$ is CLR(1), not LALR(1)
- C.
  $G$ is LALR(1), not SLR(1)
  ✓
- D.
  $G$ is LALR(1), also SLR(1)
Answer: C
Solution
Answer: (C) $G$ is LALR(1), not SLR(1) This is a classic example. After reading $d$ there is a state with items for reducing $A \to d \cdot$ and shifting (from $S \to b d \cdot a$ ). Under SLR, the reduce is tried on all of $Follow (A) = {a, c}$ , and $a$ also allows a shift, causing a shift-reduce conflict — so $G$ is not SLR(1). With LR(1)/LALR(1) lookaheads, the reduce $A \to d$ is restricted to the specific contexts (lookaheads) that do not include the conflicting $a$ , resolving the conflict. So $G$ is LALR(1) but not SLR(1).
Question 41Algorithmsmcq2 marks
An array $A$ of length $n$ with distinct elements is bitonic if $A [1.. i]$ is non-decreasing and $A [i + 1.. n]$ is non-increasing for some $i$ . Which ONE is the best asymptotic bound for the worst-case number of comparisons to search for an element in a bitonic array?
- A.
  $Θ (n)$
- B.
  $Θ (1)$
- C.
  $Θ (lo g^{2} n)$
- D.
  $Θ (lo g n)$
  ✓
Answer: D
Solution
Answer: (D) $Θ (lo g n)$ First find the peak index with binary search in $Θ (lo g n)$ . Then binary search the increasing part and the decreasing part, each $Θ (lo g n)$ . Total $Θ (lo g n)$ comparisons in the worst case.
Question 42Discrete Mathematicsmsq2 marks
Let $F$ be the set of all functions from ${1, \dots, n}$ to ${0, 1}$ . Define $f ⪯ g$ iff $f (x) \leq g (x)$ for all $x$ (where $0 \leq 1$ ). Which of the following statement(s) is/are TRUE?
- A.
  $⪯$ is a symmetric relation
- B.
  $(F, ⪯)$ is a partial order
  ✓
- C.
  $(F, ⪯)$ is a lattice
  ✓
- D.
  $⪯$ is an equivalence relation
Answer: B, C
Solution
Answer: (B) and (C) $⪯$ is the pointwise order — equivalently the subset order on the $2^{n}$ bit-vectors (the Boolean lattice $B_{n}$ ). - It is reflexive, antisymmetric and transitive → a partial order. (B) True. - Every pair $f, g$ has a meet (pointwise AND) and a join (pointwise OR) in $F$ → a lattice. (C) True. - It is antisymmetric, not symmetric, so not symmetric (A) and not an equivalence relation (D).
Question 43Digital Logicmsq2 marks
Given the following Karnaugh Map for a Boolean function $F (w, x, y, z)$ (rows $w x$ , columns $y z$ ):
```
 wx \ yz | 00 | 01 | 11 | 10
---------+----+----+----+---
   00    | 1  | 0  | 0  | 1
   01    | 0  | 1  | 1  | 0
   11    | 0  | 1  | 1  | 0
   10    | 1  | 0  | 0  | 1
```
Which one or more of the following Boolean expression(s) represent(s) $F$ ?
- A.
  $w x y z + w x y z + w x y z + w x y z + x z$
  ✓
- B.
  $w x y z + w x y z + w x y z + x z$
- C.
  $w x y z + w x y z + w x y z + x z$
- D.
  $x z + x z$
  ✓
Answer: A, D
Solution
Answer: (A) and (D) Read the map: the 1's occur exactly where $x$ and $z$ agree. The four corner cells ( $y z \in {00, 10}$ with $w x \in {00, 10}$ ) are $x z$ ; the four centre cells ( $y z \in {01, 11}$ with $w x \in {01, 11}$ ) are $x z$ . So
$F = x z + x z (the XNOR of x and z),$
which is exactly option (D). Option (A) expands the $x z$ block over all $w, y$ (the four minterms sum to $x z$ ) and adds $x z$ , so (A) $= x z + x z = F$ as well. Options (B) and (C) miss some of the $x z$ minterms, so they are not equal to $F$ .
Question 44Engineering Mathematicsmsq2 marks
Consider $P X = Q$ with $P \in R^{3 \times 3}$ , $Q \in R^{3 \times 1}$ , and $P = LU$ ( $L$ unit lower-triangular, $U$ upper-triangular). Which of the following statement(s) is/are TRUE?
- A.
  The system $P X = Q$ can be solved by first solving $L Y = Q$ and then $U X = Y$ .
  ✓
- B.
  If $P$ is invertible, then both $L$ and $U$ are invertible.
  ✓
- C.
  If $P$ is singular, then at least one of the diagonal elements of $U$ is zero.
  ✓
- D.
  If $P$ is symmetric, then both $L$ and $U$ are symmetric.
Answer: A, B, C
Solution
Answer: (A), (B) and (C) - (A) This is exactly forward/back substitution: solve $L Y = Q$ , then $U X = Y$ . TRUE. - (B) $det P = det L \cdot det U = 1 \cdot \prod u_{ii}$ . If $P$ is invertible, $det P \neq = 0$ , so all $u_{ii} \neq = 0$ and $U$ (and $L$ , det $= 1$ ) are invertible. TRUE. - (C) If $P$ is singular, $det P = \prod u_{ii} = 0$ , so some diagonal entry of $U$ is zero. TRUE. - (D) Even for symmetric $P$ , $L$ is lower-triangular and $U$ upper-triangular; they are generally not symmetric (symmetry gives $P = L D L^{T}$ , not symmetric $L, U$ ). FALSE.
Question 45Programming & Data Structuresmsq2 marks
We augment a stack (distinct positive keys) with an $O (1)$ MIN operation returning a pointer to the smallest key, (1) without deleting it and (2) without increasing the complexity of standard stack operations. Which approach(es) achieve this?
- A.
  Keep with every record in the stack a pointer to the record with the smallest key below it.
  ✓
- B.
  Keep a pointer to the record with the smallest key in the stack.
- C.
  Keep an auxiliary array in which the key values are maintained in sorted order.
- D.
  Keep a Min-Heap in which the key values are maintained.
Answer: A
Solution
Answer: (A) (A) Store with each pushed record the pointer to the minimum of the stack below it; on push, the new record's "min" is computed in $O (1)$ ; MIN and pop stay $O (1)$ . This works. - (B) A single min pointer cannot be restored in $O (1)$ after popping the minimum. Fails. - (C) Maintaining a sorted array costs $O (n)$ per push/pop. Increases complexity. - (D) A min-heap makes push/pop $O (lo g n)$ . Increases complexity.
Question 46Databasesmsq2 marks
Consider the schemas with all FDs that hold: R1(A,B,C,D,E): { D->E, EA->B, EB->C } R2(A,B,C,D): { A->D, A->B, C->A } Which of the following statement(s) is/are TRUE?
- A.
  R1 is in 3NF
- B.
  R2 is in 3NF
- C.
  R1 is NOT in 3NF
  ✓
- D.
  R2 is NOT in 3NF
  ✓
Answer: C, D
Solution
Answer: (C) and (D) R1: $A$ and $D$ appear on no RHS, so they are in every key; ${A, D}^{+} = A D E B C =$ all → candidate key $A D$ . Prime attributes $= {A, D}$ . The FD $D \to E$ has a non-superkey LHS and a non-prime RHS ( $E$ ) → violates 3NF. So R1 is NOT in 3NF (C). R2: $C^{+} = C A D B =$ all → candidate key $C$ ; prime $= {C}$ . The FD $A \to D$ has non-superkey LHS ( $A$ ) and non-prime RHS ( $D$ ) → violates 3NF. So R2 is NOT in 3NF (D). Hence (A),(B) are false and (C),(D) are true.
Question 47Operating Systemsmsq2 marks
A demand-paging system with three frames uses the reference string 1 2 3 4 5 4 1 6 4 5 1 3 2. The given frame-content table shows which references cause replacements (the *-marked ones). Which one or more of the following could be the page replacement policy in use?
- A.
  Least Recently Used page replacement policy
- B.
  Least Frequently Used page replacement policy
- C.
  Most Frequently Used page replacement policy
- D.
  Optimal page replacement policy
  ✓
Answer: D
Solution
Answer: (D) Optimal page replacement policy Simulate the given string and compare the eviction choices with the table's *-marked faults. At the distinguishing replacements (e.g. the eviction made when page 6 is brought in, and later when 3 and 2 are brought in), the victim chosen is the page whose next use is farthest in the future — the hallmark of the Optimal policy. LRU, LFU and MFU each pick a different victim at one or more of these steps, producing a different frame table. Only the Optimal policy reproduces the given contents.
Question 48Operating Systemsmsq2 marks
$P = {P_{1}, P_{2}, P_{3}, P_{4}}$ are processes; $R = {R_{1}, R_{2}, R_{3}, R_{4}}$ are single-instance resources. Assignment edges: $R_{1} \to P_{1}, R_{2} \to P_{2}, R_{3} \to P_{3}, R_{4} \to P_{4}$ . Claim (wait) edges: $P_{1} \to R_{2}, P_{2} \to R_{3}, P_{3} \to R_{1}, P_{2} \to R_{4}, P_{4} \to R_{2}$ . Which of the following statement(s) is/are CORRECT?
- A.
  Aborting $P_{1}$ makes the system deadlock free.
- B.
  Aborting $P_{3}$ makes the system deadlock free.
- C.
  Aborting $P_{2}$ makes the system deadlock free.
  ✓
- D.
  Aborting $P_{1}$ and $P_{4}$ makes the system deadlock free.
  ✓
Answer: C, D
Solution
Answer: (C) and (D) Build the wait-for graph ( $P_{i} \to P_{k}$ if $P_{i}$ waits for a resource held by $P_{k}$ ):
```
P1->P2,  P2->P3,  P3->P1,  P2->P4,  P4->P2
```
There are two cycles: $P_{1} \to P_{2} \to P_{3} \to P_{1}$ and $P_{2} \to P_{4} \to P_{2}$ . - Aborting $P_{1}$ breaks only the first cycle; $P_{2} \leftrightarrow P_{4}$ remains → still deadlocked. (A) wrong. - Aborting $P_{3}$ breaks only the first cycle; $P_{2} \leftrightarrow P_{4}$ remains. (B) wrong. - $P_{2}$ lies on both cycles, so aborting $P_{2}$ breaks both → deadlock free. (C) correct. - Aborting $P_{1}$ (breaks cycle 1) and $P_{4}$ (breaks cycle 2) removes both cycles → deadlock free. (D) correct.
Question 49Computer Organization & Architecturemsq2 marks
Three IEEE-754 single-precision numbers are stored as: RX = 0xC1100000, RY = 0x40C00000, RZ = 0x41400000. Which of the following option(s) is/are CORRECT?
- A.
  $4 (X + Y) + Z = 0$
  ✓
- B.
  $2 Y - Z = 0$
  ✓
- C.
  $4 X + 3 Z = 0$
  ✓
- D.
  $X + Y + Z = 0$
Answer: A, B, C
Solution
Answer: (A), (B) and (C) Decode each (sign, exponent $- 127$ , $1. mantissa$ ): - $X$ : C1100000 → $- 1.125 \times 2^{3} = - 9$ . - $Y$ : 40C00000 → $+ 1.5 \times 2^{2} = 6$ . - $Z$ : 41400000 → $+ 1.5 \times 2^{3} = 12$ . Now: (A) $4 (- 9 + 6) + 12 = - 12 + 12 = 0$ ✓; (B) $2 (6) - 12 = 0$ ✓; (C) $4 (- 9) + 3 (12) = - 36 + 36 = 0$ ✓; (D) $- 9 + 6 + 12 = 9 \neq = 0$ ✗.
Question 50Digital Logicmsq2 marks
Which of the following Boolean algebraic equation(s) is/are CORRECT?
- A.
  $A B C + A B C + A B C + A B C + A B C = B C + B C + A B$
- B.
  $A B + A C + B C = A B + A C$
  ✓
- C.
  $(A + C) (A + B) = A B + A C$
  ✓
- D.
  $(A + B + D) (C + D) (A + C + D) (A + B + D) = A D + C D$
  ✓
Answer: B, C, D
Solution
Answer: (B), (C) and (D) - (B) Consensus theorem: $A B + A C + B C = A B + A C$ (the term $B C$ is redundant). TRUE. - (C) Expand: $(A + C) (A + B) = A A + A B + A C + B C = A B + A C + B C = A B + A C$ (consensus). TRUE. - (D) Applying De Morgan to the complemented product-of-sums and simplifying yields $A D + C D$ . TRUE. - (A) The left side has minterm set ${0, 3, 4, 5, 7}$ while the right side gives ${0, 1, 3, 4, 7}$ (it contains $A B C = m_{1}$ but not $A B C = m_{5}$ ). The sets differ, so (A) is FALSE.
Question 51Compiler Designmsq2 marks
Consider grammars $G_{1}$ and $G_{2}$ :
```
G1: S -> if E then S | if E then S else S | a
    E -> b
G2: S -> if E then S | M
    M -> if E then M else S | c
    E -> b
```
Which of the following option(s) is/are CORRECT?
- A.
  $G_{1}$ is not LL(1) and $G_{2}$ is LL(1).
- B.
  $G_{1}$ is LL(1) and $G_{2}$ is not LL(1).
- C.
  $G_{1}$ and $G_{2}$ are not LL(1).
  ✓
- D.
  $G_{1}$ and $G_{2}$ are ambiguous.
  ✓
Answer: C, D
Solution
Answer: (C) and (D) (C) Neither grammar is LL(1). In $G_{1}$ the two $S$ -productions both begin with if, giving a FIRST/FIRST conflict. In $G_{2}$ both $S \to if E then S$ and $S \to M \to if E then M else S$ also begin with if, so FIRST $(if E then S) \cap$ FIRST $(M) \neq = \emptyset$ — again not LL(1). (D) Both grammars exhibit the dangling-else construct and admit more than one parse tree for such inputs (per the official key), so both are ambiguous.
Question 52Theory of Computationmsq2 marks
Let $Σ = {a, b, c}$ and for $x \in Σ^{*}$ , $#_{α} (x)$ denote the number of $α$ 's in $x$ . Which one or more of the following define regular language(s)?
- A.
  ${a^{m} b^{n} ∣ m, n \geq 0}$
  ✓
- B.
  ${a, b}^{*} \cap {a^{m} b^{n} c^{m - n} ∣ m \geq n \geq 0}$
- C.
  ${w \in {a, b}^{*} ∣ #_{a} (w) \equiv 2 (mod 7) and #_{b} (w) \equiv 3 (mod 9)}$
  ✓
- D.
  ${w \in {a, b}^{*} ∣ #_{a} (w) \equiv 2 (mod 7) and #_{a} (w) = #_{b} (w)}$
Answer: A, C
Solution
Answer: (A) and (C) - (A) $a^{*} b^{*}$ is regular. ✓ - (B) Intersecting with ${a, b}^{*}$ forces $c^{m - n}$ to be empty, i.e. $m = n$ , giving ${a^{n} b^{n}}$ — NOT regular. - (C) Track $#_{a} mod 7$ and $#_{b} mod 9$ with a finite automaton of $7 \times 9 = 63$ states → regular. ✓ - (D) $#_{a} = #_{b}$ requires counting and is NOT regular.
Question 53Databasesmsq2 marks
Transactions T1: R1(X) W1(Y) R1(X) W1(X) COMMIT, and T2: W2(X) W2(Y) COMMIT, over data items X, Y. Which of the schedule(s) is/are conflict serializable?
- A.
  R1(X), W2(X), W1(Y), W2(Y), R1(X), W1(X), COMMIT(T2), COMMIT(T1)
- B.
  W2(X), R1(X), W2(Y), W1(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1)
  ✓
- C.
  R1(X), W1(Y), W2(X), W2(Y), R1(X), W1(X), COMMIT(T1), COMMIT(T2)
- D.
  W2(X), R1(X), W1(Y), W2(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1)
Answer: B
Solution
Answer: (B) Build the precedence (serialization) graph for each schedule; conflict serializable iff it is acyclic. - (B): W2(X) before R1(X) and before W1(X) → $T_{2} \to T_{1}$ ; W2(Y) before W1(Y) → $T_{2} \to T_{1}$ . No conflict puts $T_{1}$ before $T_{2}$ . Graph has only $T_{2} \to T_{1}$ → acyclic → conflict serializable (order $T_{2}, T_{1}$ ). ✓ - (A): R1(X) before W2(X) gives $T_{1} \to T_{2}$ , while W2(X) before later W1(X) gives $T_{2} \to T_{1}$ → cycle. Not serializable. - (C): W1(Y) before W2(Y) gives $T_{1} \to T_{2}$ , and W2(X) before W1(X) gives $T_{2} \to T_{1}$ → cycle. Not serializable. - (D): W2(X) before R1(X) gives $T_{2} \to T_{1}$ , and W1(Y) before W2(Y) gives $T_{1} \to T_{2}$ → cycle. Not serializable.
Question 54Databasesmsq2 marks
Schema: Students(rollno,name,age,cgpa), Courses(courseno,cname,credits), Enrolled(rollno,courseno,grade). Which of the following is/are correct SQL to retrieve the names of students enrolled in courseno 1470?
- A.
  SELECT S.name FROM Students S WHERE EXISTS (SELECT * FROM Enrolled E WHERE E.courseno = 1470 AND E.rollno = S.rollno);
  ✓
- B.
  SELECT S.name FROM Students S WHERE SIZEOF (SELECT * FROM Enrolled E WHERE E.courseno = 1470 AND E.rollno = S.rollno) > 0;
- C.
  SELECT S.name FROM Students S WHERE 0 < (SELECT COUNT(*) FROM Enrolled E WHERE E.courseno = 1470 AND E.rollno = S.rollno);
  ✓
- D.
  SELECT S.name FROM Students S NATURAL JOIN Enrolled E WHERE E.courseno = 1470;
  ✓
Answer: A, C, D
Solution
Answer: (A), (C) and (D) - (A) Correlated EXISTS subquery returns students having a matching enrollment in course 1470. Correct. - (C) 0 < (SELECT COUNT(*) ...) is true exactly when a matching enrollment exists. Correct. - (D) Students NATURAL JOIN Enrolled joins on the common attribute rollno; filtering courseno = 1470 gives the enrolled students' names. Correct. - (B) SIZEOF is not a valid SQL operator. Incorrect.
Question 55Computer Organization & Architecturenat2 marks
L1 access time $= 1$ ns, L1 hit rate $= 90%$ . L2 hit rate $= 80%$ , L2 miss penalty (L2 $\to$ L1) $= 10$ ns, main-memory miss penalty (MM $\to$ L2) $= 100$ ns. The average memory access time in nanoseconds is ___________. (rounded off to one decimal place)
Answer: 4
Solution
Answer: 4.0
$AMAT = T_{L 1} + (1 - h_{L 1}) [penalty_{L 2} + (1 - h_{L 2}) penalty_{M M}] .$

$= 1 + 0.1 [10 + 0.2 (100)] = 1 + 0.1 (10 + 20) = 1 + 0.1 (30) = 1 + 3 = 4.0 ns .$
Question 56Computer Organization & Architecturenat2 marks
A 5-stage pipeline has stage delays 180, 250, 150, 170, 250 ns, and an inter-stage latch delay of 10 ns. No stalls. The time to process 1000 instructions in microseconds is __________. (rounded off to two decimal places)
Answer: 260.2 to 261.2
Solution
Answer: 261.04 Clock period $= max (stage delays) + latch = 250 + 10 = 260$ ns. Time for $N$ instructions in a $k$ -stage pipeline $= (k + N - 1) \times clock = (5 + 999) \times 260 ns = 1004 \times 260 = 261040 ns = 261.04 μ s .$
Question 57Databasesnat2 marks
In a B+ tree where each node holds at most four keys, a root-to-leaf path is: A = (49, 77, 83, -), B = (7, 19, 33, 44), C = (20*, 22*, 25*, 26*). A pointer between keys $k_{1}$ and $k_{2}$ points to a subtree with keys in $[k_{1}, k_{2})$ ; when a leaf is created, its smallest key is copied up. A record with key 23 is inserted. The smallest key value in the parent of the leaf that contains 25* is __________. (Answer in integer)
Answer: 33
Solution
Answer: 33 Inserting 23 into the full leaf $C = (20, 22, 25, 26)$ makes $(20, 22, 23, 25, 26)$ — overflow. Split into $(20, 22)$ and $(23, 25, 26)$ , copying up $23$ (smallest of the right leaf) to parent $B$ . $B = (7, 19, 33, 44)$ becomes $(7, 19, 23, 33, 44)$ — overflow. A 5-key internal node splits with the middle key $23$ pushed up to $A$ , leaving left part $(7, 19)$ and right part $(33, 44)$ . The leaf containing $2 5^{*}$ is $(23, 25, 26)$ , whose parent is the right internal node $(33, 44)$ . Its smallest key value is $33$ .
Question 58Operating Systemsnat2 marks
A system has a $2^{32}$ -byte logical address space and uses two-level hierarchical paging with page size 4096 bytes. A logical address is split into a $b$ -bit outer-page-table index, an offset within the inner-page-table page, and an offset within the desired page. Each inner-page-table entry is 8 bytes. All pages are the same size. The value of $b$ is ___________. (Answer in integer)
Answer: 11
Solution
Answer: 11 Page size $= 4096 = 2^{12}$ → page offset $= 12$ bits. Inner page table fits in one page: entries per page $= \frac{4096}{8} = 512 = 2^{9}$ → inner index $= 9$ bits. Outer index $b = 32 - 12 - 9 = 11$ bits.
Question 59Algorithmsnat2 marks
Consider the algorithm someAlgo(G): (1) run BFS from any vertex $v$ , let $u$ be a farthest vertex; (2) run BFS from $u$ , let $z$ be a farthest vertex; (3) output the distance between $u$ and $z$ . For the tree shown in the figure, the output of someAlgo( $T$ ) is ___________. (Answer in integer)
Answer: 6
Solution
Answer: 6 The double-BFS procedure is the standard algorithm for the diameter of a tree: the farthest vertex $u$ from any start is always an endpoint of a longest path, and BFS from $u$ reaches the other endpoint $z$ , so the returned distance equals the tree's diameter. Tracing the longest path in the given tree gives a diameter of $6$ edges, so the output is $6$ .
Question 60Theory of Computationnat2 marks
Let $Σ = {1, 2, 3, 4}$ . For $x \in Σ^{*}$ , $p r o d (x)$ is the product of the symbols modulo 7 (with $p r o d (ϵ) = 1$ ). Define $L = {x \in Σ^{*} ∣ p r o d (x) = 2}$ . The number of states in a minimum-state DFA for $L$ is ___________. (Answer in integer)
Answer: 6
Solution
Answer: 6 Track the running product modulo 7. The symbols $1, 2, 3, 4$ are all non-zero mod 7, so the product is always a unit — it lives in the multiplicative group $(Z /7)^{*} = {1, 2, 3, 4, 5, 6}$ , which has 6 elements. Starting from $1$ , these symbols (e.g. 3 is a generator) can reach every residue in ${1, \dots, 6}$ , and each residue leads to different acceptance behaviour, so all 6 are distinct, non-mergeable states (0 is never reachable). The accepting state is residue $2$ . Minimum DFA has $6$ states.
Question 61Computer Organization & Architecturenat2 marks
An application executes $6.4 \times 1 0^{8}$ instructions in 6.3 s. The instruction mix is:
```
Type       | CPI | Count
Branch     |  2  | 2.25e8
Load       |  5  | 1.20e8
Store      |  4  | 1.65e8
Arithmetic |  3  | 1.30e8
```
The duration of a clock cycle in nanoseconds is _________. (rounded off to one decimal place)
Answer: 3
Solution
Answer: 3.0 Total clock cycles $= \sum (CPI \times count)$ :
$2 (2.25) + 5 (1.20) + 4 (1.65) + 3 (1.30) = (4.5 + 6.0 + 6.6 + 3.9) \times 1 0^{8} = 21.0 \times 1 0^{8} .$
Clock cycle time $= \frac{total time}{total cycles} = \frac{6.3 s}{21.0 \times 1 0 ^{8}} = 3.0 \times 1 0^{- 9} s = 3.0 ns .$
Question 62Programming & Data Structuresnat2 marks
Consider the C program:
```
int main(){
    int a;
    int arr[5] = {30,50,10};
    int *ptr;
    ptr = &arr[0] + 1;
    a = *ptr;
    (*ptr)++;
    ptr++;
    printf("%d", a + (*ptr) + arr[1]);
    return 0;
}
```
The output of the above program is ___________. (Answer in integer)
Answer: 111
Solution
Answer: 111 arr = {30,50,10,0,0}. ptr = &arr[0]+1 = &arr[1], so a = *ptr = 50. Then (*ptr)++ makes arr[1] = 51. ptr++ now points to &arr[2], where *ptr = 10. Output $= a + (* pt r) + a r r [1] = 50 + 10 + 51 = 111.$
Question 63Programming & Data Structuresnat2 marks
Consider the C program:
```
int g(int n) { return (n+10); }
int f(int n) { return g(n*2); }
int main() {
    int sum, n;
    sum = 0;
    for (n=1; n<3; n++)
        sum += g(f(n));
    printf("%d", sum);
    return 0;
}
```
The output of the given C program is ________. (Answer in integer)
Answer: 46
Solution
Answer: 46 $f (n) = g (2 n) = 2 n + 10$ , so $g (f (n)) = g (2 n + 10) = 2 n + 20$ . - $n = 1 : 2 (1) + 20 = 22$ . - $n = 2 : 2 (2) + 20 = 24$ . $sum = 22 + 24 = 46.$
Question 64Engineering Mathematicsnat2 marks
A quadratic $(x - α) (x - β)$ over the complex numbers is square invariant if $(x - α) (x - β) = (x - α^{2}) (x - β^{2})$ . Choosing one such polynomial at random, the probability that its roots are equal is __________. (rounded off to one decimal place)
Answer: 0.5
Solution
Answer: 0.5 Square invariance means ${α, β} = {α^{2}, β^{2}}$ as multisets. - Case $α^{2} = α, β^{2} = β$ : each root $\in {0, 1}$ → unordered pairs ${0, 0}, {0, 1}, {1, 1}$ . - Case $α^{2} = β, β^{2} = α$ (new): then $α^{4} = α$ , giving the primitive cube roots of unity ${ω, ω^{2}}$ . So there are four square-invariant polynomials: ${0, 0}, {0, 1}, {1, 1}, {ω, ω^{2}}$ . Equal roots occur for ${0, 0}$ and ${1, 1}$ — that is 2 of the 4.
$P = \frac{2}{4} = 0.5.$
Question 65Engineering Mathematicsnat2 marks
The unit interval $(0, 1)$ is divided at a point chosen uniformly over $(0, 1)$ into two subintervals. The expected length of the subinterval that contains 0.4 is ___________. (rounded off to two decimal places)
Answer: 0.7 to 0.8
Solution
Answer: 0.74 Let $U \sim Uniform (0, 1)$ be the split point. - If $U > 0.4$ , the point $0.4$ lies in $(0, U)$ , length $U$ . - If $U < 0.4$ , it lies in $(U, 1)$ , length $1 - U$ .
$E [length] = \int_{0.4}^{1} U d U + \int_{0}^{0.4} (1 - U) d U .$

$\int_{0.4}^{1} U d U = \frac{1 - 0.16}{2} = 0.42, \int_{0}^{0.4} (1 - U) d U = 0.4 - 0.08 = 0.32.$

$E = 0.42 + 0.32 = 0.74.$

Practice the full paper with a timer

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

Create free account →