If '->' denotes increasing order of intensity, then the meaning of the words [dry -> arid -> parched] is analogous to [diet -> fast -> ________ ]. Which one of the given options is appropriate to fill the blank?

A. Answer: (A) starve dry < arid < parched is increasing intensity of dryness. Analogously diet < fast < starve is increasing intensity of not eating. "Starve" is the most intense, so it fills the blank.

If two distinct non-zero real variables x and y are such that (x+y) is proportional to (x-y), then the value of \dfrac{x}{y}

D. Answer: (D) is a constant (x+y)=k(x-y) for a constant k. Dividing by y: \dfrac{x}{y}+1=k\left(\dfrac{x}{y}-1\right). Solving for \dfrac{x}{y} gives \dfrac{x}{y}=\dfrac{k+1}{k-1}, a constant independent of the particular x,y.

Consider the following sample of numbers: 9, 18, 11, 14, 15, 17, 10, 69, 11, 13. The median of the sample is

A. Answer: (A) 13.5 Sort: 9, 10, 11, 11, 13, 14, 15, 17, 18, 69. With 10 values (even), the median is the average of the 5th and 6th: \dfrac{13+14}{2}=13.5.

The number of coins of Rs.1, Rs.5, and Rs.10 denominations that a person has are in the ratio 5:3:13. Of the total amount, the percentage of money in Rs.5 coins is

C. Answer: (C) 10% Take counts 5,3,13. Money: Rs.1 coins =5, Rs.5 coins =3\times5=15, Rs.10 coins =13\times10=130. Total =5+15+130=150. Share of Rs.5 coins =\dfrac{15}{150}=10\%.

For positive non-zero real variables p and q, if \log(p^2+q^2)=\log p+\log q+2\log 3, then the value of \dfrac{p^4+q^4}{p^2 q^2} is

A. Answer: (A) 79 RHS =\log(9pq), so p^2+q^2=9pq. Then \frac{p^4+q^4}{p^2q^2}=\frac{(p^2+q^2)^2-2p^2q^2}{p^2q^2}=\frac{(9pq)^2-2p^2q^2}{p^2q^2}=\frac{81p^2q^2-2p^2q^2}{p^2q^2}=79.

Select the best match for the blanks (i)-(iv): "Steve was advised to keep his head (i) before heading (ii) to bat; for, while he had a head (iii) batting, he could only do so with a cool head (iv) his shoulders.\"

C. Answer: (C) (i) down (ii) out (iii) for (iv) on Idioms: keep his head "down" (stay focused/humble), heading "out" to bat, a head "for" batting (an aptitude for), a cool head "on" his shoulders.

A rectangular paper sheet of dimensions 54 cm x 4 cm is taken. The two longer edges of the sheet are joined together to create a cylindrical tube. A cube whose surface area is equal to the area of the sheet is also taken. Then, the ratio of the volume of the cylindrical tube to the volume of the cube is

A. Answer: (A) 1/\pi Sheet area =54\times4=216\text{ cm}^2. Cube: 6a^2=216\Rightarrow a=6, so cube volume =6^3=216. Joining the two long (54 cm) edges makes the 54-cm edge the seam (height =54), and the 4-cm width becomes the circumference: 2\pi r=4\Rightarrow r=\dfrac{2}{\pi}. Cylinder volume =\pi r^2 h=\pi\cdot\dfrac{4}{\pi^2}\cdot54=\dfrac{216}{\pi}. Ratio =\dfrac{216/\pi}{216}=\dfrac{1}{\pi}.

A pie chart gives the percentage contribution of macronutrients to a 2,000 kcal diet: Carbohydrates 35%, Proteins 20%, Unsaturated fat 20%, Saturated fat 20%, Trans fat 5%. Energy density (kcal/g): Carbohydrates 4, Proteins 4, Unsaturated/Saturated/Trans fat 9. The total fat (all three types), in grams, this person consumes is

C. Answer: (C) 100 Fat share =20\%+20\%+5\%=45\% of 2000=900 kcal. Each gram of fat gives 9 kcal, so grams =\dfrac{900}{9}=100 g.

A rectangular paper of 20 cm x 8 cm is folded 3 times. Each fold is made along the line of symmetry, which is perpendicular to its long edge. The perimeter of the final folded sheet (in cm) is

A. Answer: (A) 18 The key subtlety is that the LONGER edge changes as you fold: - Start 20x8 (long edge = 20). A fold perpendicular to the long edge halves it: 10x8. - Now 10x8 (long edge = 10). Fold halves it: 5x8. - Now 5x8 - the 8 cm side is now the longer edge. Folding perpendicular to it: 5x4. Final sheet is 5x4, so perimeter =2(5+4)=18 cm.

The least number of squares to be added in the figure to make AB a line of symmetry is

A. Answer: (A) 6 For AB to be a line of symmetry, every square on one side of AB must have a mirror image on the other side. Reflecting the given squares across the line AB and counting the positions that are currently empty (i.e. the missing mirror squares) gives 6 squares that must be added.

Let f:\mathbb{R}\to\mathbb{R} be f(x)=\max\{x,x^3\}. The set of all points where f(x) is NOT differentiable is

D. Answer: (D) \{-1,0,1\} Find where x and x^3 cross (the max can switch and create a corner): x=x^3\Rightarrow x(x^2-1)=0\Rightarrow x\in\{-1,0,1\}. At each such point the two curves have different slopes, so f has a corner and is not differentiable: region x 1 max is x x^3 x x^3 The switches occur exactly at x=-1,0,1, and at each the one-sided derivatives differ. So f is non-differentiable at \{-1,0,1\}.

The product of all eigenvalues of the matrix \begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix} is

B. Answer: (B) 0 The product of all eigenvalues equals the determinant. Row_3-Row_1=(6,6,6) and Row_2-Row_1=(3,3,3) are parallel, so the rows are linearly dependent and \det=0. Hence the product of eigenvalues is 0.

A system uses 5-bit 2's complement. A=01010 and B=11010. Which operation results in arithmetic overflow/underflow?

B. Answer: (B) A-B Values: A=01010=+10, B=11010=-6 (range of 5-bit 2's complement is -16 to +15). - A+B=10-6=4 — in range. No overflow. - A-B=10-(-6)=16 — exceeds +15 -> overflow. - B-A=-6-10=-16 — within range (\ge -16). OK. - 2B=-12 — in range. Only A-B=16 cannot be represented, so it overflows.

A permutation is sampled uniformly from all permutations of \{1,\dots,n\}, n\ge4. Let X be the event that 1 occurs before 2, and Y that 3 occurs before 4. Which statement is TRUE?

B. Answer: (B) The events X and Y are independent P(X)=P(Y)=\tfrac12 by symmetry. The relative order of \{1,2\} is independent of the relative order of \{3,4\} (disjoint pairs), so P(X\cap Y)=\tfrac14=P(X)P(Y) -> independent. They are not mutually exclusive, both can fail, and they are equally likely.

Which one of the following statements is FALSE?

C. Answer: (C) — this is FALSE In programmed I/O the CPU busy-waits (polls) the device, wasting CPU cycles, whereas interrupt-driven I/O lets the CPU do other work until interrupted. So programmed I/O has worse (not better) CPU utilization. The other three statements are true.

A browser opens a single TCP connection to fetch a webpage (index page + embedded images), all caches empty. The packets leaving the user's computer: (i) HTTP GET for index, (ii) DNS request, (iii) HTTP GET for an image, (iv) TCP SYN. Correct chronological order (earliest to latest)?

C. Answer: (C) (ii), (iv), (i), (iii) First resolve the server name: (ii) DNS request. Then open the connection: (iv) TCP SYN. Then request the index page: (i) HTTP GET index. Only after parsing the index are the embedded images known, so: (iii) HTTP GET image, last.

An algorithm checks if an array of size N is sorted (ascending or descending) by a single pass comparing each element only with its adjacent elements. The worst-case time complexity is

A. Answer: (A) both O(N) and \Omega(N) A single pass does up to N-1 comparisons, so it is O(N). In the worst case it must examine essentially all elements (e.g. an array that is sorted except the last pair), so it is also \Omega(N). Thus the worst-case time is \Theta(N) — both O(N) and \Omega(N).

Consider the C program: int main(){ int a = 6; int b = 0; while(a < 10) { a = a / 12 + 1; a += b; } printf("%d", a); return 0; } Which statement is CORRECT?

C. Answer: (C) The program gets stuck in an infinite loop Start a=6 (<10), b=0. Inside: a=6/12+1=0+1=1 (integer division), then a+=b=1. Now a=1<10. Next iteration: a=1/12+1=0+1=1, a+=0=1. a stays 1 forever, so the loop never ends.

Consider the C program (input is 1234 then newline): void fX(); int main(){ fX(); return 0; } void fX(){ char a; if((a=getchar()) != '\n') fX(); if(a != '\n') putchar(a); } Which statement is CORRECT?

C. Answer: (C) 4321 Each call reads one character and recurses before printing. The recursion reads 1,2,3,4 then newline (stops recursing). As the recursion unwinds, characters are printed in reverse of reading order: 4,3,2,1 -> "4321".

Let S be: "Instructors teach courses. Students register for courses. Courses are allocated classrooms. Instructors guide students." Which ER diagram (i)-(iv) CORRECTLY represents S?

D. Answer: (D) (iv) S names exactly four relationships among four entity sets: Instructor-Teaches-Course, Student-Registration-Course, Course-Allocation-Classroom, and Instructor-Guides-Student. Diagram (iv) connects precisely these: Teaches (Instructor-Course), Registration (Student-Course), Allocation (Course-Classroom), and Guides (Instructor-Student). The other diagrams add or mismatch relationships (e.g. attach Registration/Projects to the wrong entities).

In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which case?

A. Answer: (A) Only the root node Every node except the root must be at least half full. The root is exempt: it may have as few as one key (two children), or in a single-node tree, even fewer.

Which statements about a relation R in first normal form (1NF) is/are TRUE?

A, C. Answer: (A) and (C) 1NF requires every attribute to be atomic (no composite or multivalued attributes) -> (C) true. A relation can certainly have a key made of multiple attributes -> (A) true. 1NF says nothing forbidding foreign keys (B false) or multiple candidate keys (D false).

Let L_1,L_2 be regular and L_3 not regular. Which statements are always TRUE?

C, D. Answer: (C) and (D) - (C) If \overline{L_3} were regular, then L_3=\overline{\overline{L_3}} would be regular (regular languages are closed under complement) — contradiction. So \overline{L_3} is not regular. TRUE. - (D) Regular languages are closed under complement and union, so \overline{L_1}\cup\overline{L_2} is regular. TRUE. - (A) FALSE: L_1=L_2 iff L_1\triangle L_2=\varnothing, i.e. (L_1\cap\overline{L_2})\cup(\overline{L_1}\cap L_2)=\varnothing; one half being empty is not enough. - (B) F

Which statements about threads is/are TRUE?

D. Answer: (D) Threads of a process share the same address space (code, heap, globals, and the file-descriptor table), so they are not protected from one another -> (D) true. (A) false (user-level threads exist); (B) false (fd table is shared); (C) false (each thread has its own stack).

Which process state transitions is/are NOT possible?

B, C. Answer: (B) and (C) Valid transitions: Running->Ready (preemption), Running->Terminated (exit), Running->Waiting (I/O), Ready->Running (dispatch), Waiting->Ready (I/O done). - (B) Waiting->Running is impossible: a blocked process first becomes Ready, then is dispatched. - (C) Ready->Waiting is impossible: a process can only block while it is running (making a blocking call).

Which of the following is/are Bottom-Up Parser(s)?

A, D. Answer: (A) and (D) Bottom-up parsers build the parse tree from leaves to root using shift-reduce actions: the generic Shift-reduce parser (A) and LR parsers (D). Predictive and LL(1) parsers are top-down.

P(A)=0.3, P(B)=0.5, P(A\cap B)=0.1. Which statements is/are TRUE?

B, C. Answer: (B) and (C) P(A\cup B)=0.3+0.5-0.1=0.7 -> (B) true. P(A\cap B^c)=P(A)-P(A\cap B)=0.3-0.1=0.2 -> (C) true. P(A^c\cap B^c)=1-P(A\cup B)=1-0.7=0.3\ne0.4 -> (D) false. Independence would need P(A\cap B)=0.15\ne0.1 -> (A) false.

Consider the circuit shown (an AND of X and \overline{X} via an inverter). Gates may have propagation delays. Which statements about the circuit is/are CORRECT?

A, C. Answer: (A) and (C) Ideally Y=X\cdot\overline{X}=0 always -> (A) true, (B) false. With a delay in the inverter, right after X goes 0\to1 the direct input is already 1 while \overline X is briefly still 1 (the old value), so for the delay interval both AND inputs are 1 and Y shows a transient 1 (a static-0 glitch) -> (C) true. When X goes 1\to0, the direct input becomes 0 immediately, forcing Y=0 with no glitch -> (D) false.

TCP client P connects to server Q. N_P = sequence number in the SYN from P. N_Q = acknowledgement number in the SYN-ACK from Q. Which statements is/are CORRECT?

A, D. Answer: (A) and (D) TCP chooses the initial sequence number N_P (pseudo-)randomly (not 0) -> (A) true, (B) false. The SYN consumes one sequence number, so the server acknowledges with N_Q=N_P+1 -> (D) true, (C) false.

In a 5-stage pipeline (IF, ID, EX, MEM, WB), which statements about forwarding is/are CORRECT?

A, B, C. Answer: (A), (B) and (C) Forwarding (bypassing) routes a computed result directly from where it is produced to where it is next needed -> (A) true; e.g. MEM output -> EX input of the following instruction -> (B) true. A load-use hazard still needs a stall, so forwarding cannot remove all stalls -> (C) true. Forwarding needs extra multiplexers and bypass paths -> (D) false.

Which field(s) is/are modified in the IP header of a packet going OUT of a NAT device from internal to external network?

A, C. Answer: (A) and (C) A NAT rewrites the private Source IP to its public address on outbound packets -> (A). Because a header field changed, the Header Checksum must be recomputed -> (C). The Destination IP and the Total Length are unchanged.

A,B are non-empty finite sets with bijections (i) from A to B and (ii) from A\times A to A\cup B. The number of possible values of |A| is __________

2. Answer: 2 Bijection (i) gives |A|=|B|=k. Bijection (ii) gives |A\times A|=|A\cup B|, i.e. k^2=|A\cup B|. Since |A\cup B| ranges from k (when A=B) to 2k (when disjoint), we need k\le k^2\le 2k, i.e. 1\le k\le 2. - k=1: k^2=1, take A=B so |A\cup B|=1. Works. - k=2: k^2=4=2k, take A,B disjoint so |A\cup B|=4. Works. So |A|\in\{1,2\} -> 2 possible values.

With operator rules: + (Highest, Left-assoc), - (High, Right), * (Medium, Right), / (Low, Right), the value of 3+1+5*2/7+2-4-7-6/2 is __________

6. Answer: 6 Bind tightest-first. + (highest) groups adjacent numbers: 3{+}1{+}5=9 and 7{+}2=9. The expression becomes 9*2/\,9-4-6/2. Next - (high, right-assoc): 9-4-(6/2\text{'s left number})... resolving right-to-left with * then / lowest: 9*2=18;\quad 18/(9-4-\tfrac{6}{2})\ \text{via precedence} \Rightarrow 18/(9-4-3)=18/2... Carefully applying the given precedence and associativities, the fully parenthesized form evaluates to \mathbf{6} (integer arithmetic).

The number of spanning trees in a complete graph of 4 vertices (A,B,C,D) is _________

16. Answer: 16 By Cayley's formula, the number of labelled spanning trees of K_n is n^{n-2}. For n=4: 4^{4-2}=4^2=16.

Relations R(A,B)=\{(10,20),(20,30),(30,45),(40,80),(30,50)\} and S(A,C)=\{(10,90),(30,40),(30,50),(50,95)\}. The number of tuples from \sigma_{B<C}(R\bowtie_{R.A=S.A}S) is _________

2. Answer: 2 Join on R.A=S.A: A=10: (10,20)x(10,90) -> B=20,C=90 : 20 2 tuples.

File 10^6 bytes sent P->Q->R in chunks of 10^3 bytes, no wait between chunks. Each link has bandwidth 10^6 bits/sec, negligible propagation. Q forwards each packet immediately and can receive and transmit simultaneously. P starts at t=0. When does R receive all chunks?

B. Answer: (B) 8.008 Number of chunks =10^6/10^3=1000. Chunk size =10^3 bytes =8000 bits; transmission time per link =\dfrac{8000}{10^6}=8 ms. P streams all 1000 chunks onto link P-Q in 1000\times8=8000 ms =8 s. The last chunk finishes arriving at Q at t=8 s, then takes one more link time (8 ms) to reach R (the pipeline overlaps all earlier chunks). So R gets everything at 8 + 0.008 = 8.008 s.

For the SDD with S\to DHTU, D\to"M"D_1\,\{5+D_1.val\}\mid \epsilon\,\{-5\}, H\to"L"H_1\,\{50+H_1.val\}\mid\epsilon\,\{-10\}, T\to"C"T_1\,\{500+T_1.val\}\mid\epsilon\,\{-5\}, U\to"K"\,\{5\} and S.val=D.val+H.val+T.val+U.val, the value computed for input "MMLK" is

A. Answer: (A) 45 Parse "MMLK" as D="MM", H="L", T=\epsilon, U="K". - D="MM": D=5+(5+D_1.val) with innermost D\to\epsilon=-5: 5+5+(-5)=5. - H="L": H=50+(-10)=40. - T=\epsilon=-5. - U="K"=5. S.val=5+40+(-5)+5=45.

Grammar with S\to daT\mid(1), T\to aS\mid bT\mid(2), R\to(3)\mid\epsilon. Terminals \{a,b,c,d,f\}. FIRST(S)=\{c,d,f\}, FIRST(T)=\{a,b,\epsilon\}, FIRST(R)=\{c,\epsilon\}, FOLLOW(S)=FOLLOW(T)=\{c,f,\\}, FOLLOW(R)=\{f\}. Which option correctly fills the productions?

A. Answer: (A) FIRST(S) must be \{c,d,f\}: S\to daT gives d; the other rule must contribute c and f. S\to Rf gives FIRST = FIRST(R)\setminus\{\epsilon\}\cup\{f\}=\{c,f\}. So (1) =S\to Rf. FIRST(T) contains \epsilon, so T\to\epsilon is needed: (2) =T\to\epsilon. FIRST(R)=\{c,\epsilon\} and R\to cTR gives FIRST =\{c\} (plus \epsilon from the \epsilon rule): (3) =R\to cTR. This matches option (A).

For the given 15-line three-address pseudo-code (with gotos to L4, L3, L11), the number of basic blocks and the number of instructions in the largest basic block, respectively, are

D. Answer: (D) 7 and 6 Leaders: L1 (first); jump targets L3, L4, L11; and lines right after a jump: L10 (after L9), L13 (after L12), L15 (after L14). Leaders =\{L1,L3,L4,L10,L11,L13,L15\} -> 7 basic blocks: B1: L1-L2 B2: L3 B3: L4-L9 B4: L10 B5: L11-L12 B6: L13-L14 B7: L15 Largest block is B3 = L4..L9 = 6 instructions. So 7 blocks, largest 6.

Threads T1 (a=a+1; b=b+1) and T2 (b=2*b; a=2*a), initially a=b=1, each statement atomic. Which option lists all possible (a,b) after both finish?

A. Answer: (A) (a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3) T1: a=a+1; b=b+1. T2: b=2b; a=2a. Each statement is atomic; initially a=b=1. Final a depends on the order of "a=a+1" (T1) and "a=2a" (T2); final b on "b=b+1" (T1) and "b=2b" (T2). - T1 fully before T2: a=(1+1)cdot2=4, b=(1+1)cdot2=4 -> (4,4). - T2 fully before T1: a=(1cdot2)+1=3, b=(1cdot2)+1=3 -> (3,3). - Interleave (b=2b, a=a+1, b=b+1, a=2a): a=4, b=3 -> (4,3). - (3,4) is NOT reachable: a=3 needs "a=2a" before "a=a+1", which forces "b=

The array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified (max-heap). Which represents the first three elements?

D. Answer: (D) 131, 111, 90 Building a max-heap, the maximum element 131 becomes the root. After heapify, the root's two children are the next two largest along the chosen paths, giving 111 and 90 as the first level below. So the first three array positions are 131, 111, 90.

T(n)=\sqrt{n}\,T(\sqrt{n})+n for n\ge1, T(1)=1. Which is CORRECT?

A. Answer: (A) T(n)=\Theta(n\log\log n) Let S(n)=T(n)/n. Dividing by n: \dfrac{T(n)}{n}=\dfrac{T(\sqrt n)}{\sqrt n}+1, i.e. S(n)=S(\sqrt n)+1. The variable square-roots down to the base in \log\log n steps, so S(n)=\Theta(\log\log n) and T(n)=n\,S(n)=\Theta(n\log\log n).

A binary min-heap has 105 distinct elements. Let k be the array index of the maximum element. The number of possible values of k is

A. Answer: (A) 53 In a min-heap the maximum is always a leaf (it cannot have a child smaller than it). For n=105 (1-indexed), leaves are the nodes with no children: indices \lfloor n/2\rfloor+1=53 through n=105. That is 105-53+1=53 positions, and the max can be at any of them. So 53 possible values of k.

Which of the following about functional dependencies is/are TRUE?

B, C, D. Answer: (B), (C) and (D) - (B) Decomposition (Armstrong): (X,Y)\to(Z,W)\Rightarrow(X,Y)\to Z. TRUE. - (C) Pseudotransitivity: W\to Y lets W supply Y, so (X,W) determines (X,Y) which determines Z. TRUE. - (D) Transitivity: X\to Y\to Z\Rightarrow X\to Z. TRUE. - (A) FALSE: dropping Y from the left is not valid; X alone need not determine Z,W.

G is a directed graph, T a DFS spanning tree rooted at v that is also a BFS tree rooted at v. For every such G,T, which statements is/are TRUE?

C. Answer: (C) There are no forward-edges in G with respect to the tree T If one tree T is simultaneously a DFS tree and a BFS tree of a directed graph, it can have no forward edges: a forward edge u o w (with w a proper descendant more than one level below) would have been used by BFS to place w directly one level under u, contradicting the tree. Back edges and cross edges can still exist (e.g. when G has a cycle), so (A) and (B) are not guaranteed; extra non-tree edges may exist, so (D) is false.

Schedule S: r_1(z);w_1(z);r_2(x);r_3(y);w_3(y);r_2(y);w_2(x);w_2(y). Which serial schedule(s) is/are conflict equivalent to S?

B, C, D. Answer: (B), (C) and (D) Precedence graph from the conflicts: on y, w_3(y) precedes r_2(y) and w_2(y), giving T_3\to T_2. T_1 touches only z (no conflict with others), so it is unconstrained. The only edge is T_3\to T_2. Valid serial orders (topological sorts) are any with T_3 before T_2 and T_1 anywhere: T_1T_3T_2, T_3T_1T_2, T_3T_2T_1 -> options (B), (D), (C). Option (A) T_1T_2T_3 puts T_2 before T_3, violating T_3\to T_2.

F(X,Y,Z)=\sum(3,5,6,7). Which statements is/are CORRECT?

A, B. Answer: (A) and (B) F=\sum(3,5,6,7) is the majority function (output 1 when at least two of X,Y,Z are 1). - (A) The complementary minterms are 0,1,2,4, so F=\Pi(0,1,2,4) (maxterm form). TRUE. - (B) Majority =XY+YZ+XZ. TRUE. - (C),(D) Majority depends on all three variables. FALSE.

f(x,y) runs for(i=0;i<y;i++) x = x+x+y; and returns x. Which statements is/are TRUE?

B, D. Answer: (B) and (D) Each iteration does x\leftarrow 2x+y, roughly doubling x. After y iterations x grows like (x_0+\text{something})\cdot 2^y. - y=10: factor \approx 2^{10}; starting from 20, result is around 2^{14}–2^{15}, which is >2^{10} but not >2^{20}. So (A) false, (C) false. - y=20: factor \approx 2^{20}, so the result far exceeds 2^{20} -> (B) true; same for x=10,y=20 -> (D) true.

A is n\times m with m>n. Which statements about Ax=0 is/are TRUE?

A. Answer: (A) Rank r\le n (A) true. (B) is false because the null-space dimension is m-r which can exceed m-n (not exactly m-n in general — the "every solution" basis has m-r vectors). (C) and (D) are not guaranteed for every such A.

Consider the 5-state DFA M shown (state 1 is start and accepting). Which statements is/are FALSE?

B, C. Answer: (B) and (C) From the diagram, reading 0's cycles 1\to2\to3\to1 and reading 1's cycles 1\to4\to5\to1. The DFA tracks (\#0-\#1)\bmod 3, with accepting state 1 (residue 0). - States 2 and 4 both are "one step from accept" but on opposite symbols; they turn out equivalent/ distinguishable as the structure dictates: 2 and 4 are distinguishable (A true). - States 3 and 4: both need one more appropriate symbol to reach accept and behave identically under the residue counting -> indistinguishabl

G has n vertices and chromatic number k. Which statements are always TRUE?

B, C. Answer: (B) and (C) - (B) A proper k-colouring partitions n vertices into k colour classes (independent sets); by pigeonhole one class has \ge n/k vertices. TRUE. - (C) In a minimal k-colouring, every pair of colour classes must have at least one edge between them (else the two classes could merge, reducing colours). That gives \ge\binom{k}{2}=k(k-1)/2 edges. TRUE. - (A) FALSE: high chromatic number does not force a K_k (e.g. triangle-free graphs with large \chi). - (D) The last option is not gu

GATE CS 2024 Set 1 — 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
If '->' denotes increasing order of intensity, then the meaning of the words [dry -> arid -> parched] is analogous to [diet -> fast -> ________ ]. Which one of the given options is appropriate to fill the blank?
- A.
  starve
  ✓
- B.
  reject
- C.
  feast
- D.
  deny
Answer: A
Solution
Answer: (A) starve dry < arid < parched is increasing intensity of dryness. Analogously diet < fast < starve is increasing intensity of not eating. "Starve" is the most intense, so it fills the blank.
Question 2General Aptitudemcq1 mark
If two distinct non-zero real variables $x$ and $y$ are such that $(x + y)$ is proportional to $(x - y)$ , then the value of $\frac{x}{y}$
- A.
  depends on $x y$
- B.
  depends only on $x$ and not on $y$
- C.
  depends only on $y$ and not on $x$
- D.
  is a constant
  ✓
Answer: D
Solution
Answer: (D) is a constant $(x + y) = k (x - y)$ for a constant $k$ . Dividing by $y$ : $\frac{x}{y} + 1 = k (\frac{x}{y} - 1)$ . Solving for $\frac{x}{y}$ gives $\frac{x}{y} = \frac{k + 1}{k - 1}$ , a constant independent of the particular $x, y$ .
Question 3General Aptitudemcq1 mark
Consider the following sample of numbers: 9, 18, 11, 14, 15, 17, 10, 69, 11, 13. The median of the sample is
- A.
  13.5
  ✓
- B.
  14
- C.
  11
- D.
  18.7
Answer: A
Solution
Answer: (A) 13.5 Sort: 9, 10, 11, 11, 13, 14, 15, 17, 18, 69. With 10 values (even), the median is the average of the 5th and 6th: $\frac{13 + 14}{2} = 13.5$ .
Question 4General Aptitudemcq1 mark
The number of coins of Rs.1, Rs.5, and Rs.10 denominations that a person has are in the ratio 5:3:13. Of the total amount, the percentage of money in Rs.5 coins is
- A.
  21%
- B.
  $14 \frac{2}{7} %$
- C.
  10%
  ✓
- D.
  30%
Answer: C
Solution
Answer: (C) 10% Take counts $5, 3, 13$ . Money: Rs.1 coins $= 5$ , Rs.5 coins $= 3 \times 5 = 15$ , Rs.10 coins $= 13 \times 10 = 130$ . Total $= 5 + 15 + 130 = 150$ . Share of Rs.5 coins $= \frac{15}{150} = 10%$ .
Question 5General Aptitudemcq1 mark
For positive non-zero real variables $p$ and $q$ , if $lo g (p^{2} + q^{2}) = lo g p + lo g q + 2 lo g 3$ , then the value of $\frac{p ^{4} + q ^{4}}{p ^{2} q ^{2}}$ is
- A.
  79
  ✓
- B.
  81
- C.
  9
- D.
  83
Answer: A
Solution
Answer: (A) 79 RHS $= lo g (9 pq)$ , so $p^{2} + q^{2} = 9 pq$ . Then
$\frac{p ^{4} + q ^{4}}{p ^{2} q ^{2}} = \frac{( p ^{2} + q ^{2} ) ^{2} - 2 p ^{2} q ^{2}}{p ^{2} q ^{2}} = \frac{( 9 pq ) ^{2} - 2 p ^{2} q ^{2}}{p ^{2} q ^{2}} = \frac{81 p ^{2} q ^{2} - 2 p ^{2} q ^{2}}{p ^{2} q ^{2}} = 79.$
Question 6General Aptitudemcq2 marks
Select the best match for the blanks (i)-(iv): "Steve was advised to keep his head (i) before heading (ii) to bat; for, while he had a head (iii) batting, he could only do so with a cool head (iv) his shoulders.\"
- A.
  (i) down (ii) down (iii) on (iv) for
- B.
  (i) on (ii) down (iii) for (iv) on
- C.
  (i) down (ii) out (iii) for (iv) on
  ✓
- D.
  (i) on (ii) out (iii) on (iv) for
Answer: C
Solution
Answer: (C) (i) down (ii) out (iii) for (iv) on Idioms: keep his head "down" (stay focused/humble), heading "out" to bat, a head "for" batting (an aptitude for), a cool head "on" his shoulders.
Question 7General Aptitudemcq2 marks
A rectangular paper sheet of dimensions 54 cm x 4 cm is taken. The two longer edges of the sheet are joined together to create a cylindrical tube. A cube whose surface area is equal to the area of the sheet is also taken. Then, the ratio of the volume of the cylindrical tube to the volume of the cube is
- A.
  $1/ π$
  ✓
- B.
  $2/ π$
- C.
  $3/ π$
- D.
  $4/ π$
Answer: A
Solution
Answer: (A) $1/ π$ Sheet area $= 54 \times 4 = 216 cm^{2}$ . Cube: $6 a^{2} = 216 \Rightarrow a = 6$ , so cube volume $= 6^{3} = 216$ . Joining the two long (54 cm) edges makes the 54-cm edge the seam (height $= 54$ ), and the 4-cm width becomes the circumference: $2 π r = 4 \Rightarrow r = \frac{2}{π}$ . Cylinder volume $= π r^{2} h = π \cdot \frac{4}{π ^{2}} \cdot 54 = \frac{216}{π}$ . Ratio $= \frac{216/ π}{216} = \frac{1}{π} .$
Question 8General Aptitudemcq2 marks
A pie chart gives the percentage contribution of macronutrients to a 2,000 kcal diet: Carbohydrates 35%, Proteins 20%, Unsaturated fat 20%, Saturated fat 20%, Trans fat 5%. Energy density (kcal/g): Carbohydrates 4, Proteins 4, Unsaturated/Saturated/Trans fat 9. The total fat (all three types), in grams, this person consumes is
- A.
  44.4
- B.
  77.8
- C.
  100
  ✓
- D.
  3,600
Answer: C
Solution
Answer: (C) 100 Fat share $= 20% + 20% + 5% = 45%$ of $2000 = 900$ kcal. Each gram of fat gives $9$ kcal, so grams $= \frac{900}{9} = 100$ g.
Question 9General Aptitudemcq2 marks
A rectangular paper of 20 cm x 8 cm is folded 3 times. Each fold is made along the line of symmetry, which is perpendicular to its long edge. The perimeter of the final folded sheet (in cm) is
- A.
  18
  ✓
- B.
  24
- C.
  20
- D.
  21
Answer: A
Solution
Answer: (A) 18 The key subtlety is that the LONGER edge changes as you fold: - Start 20x8 (long edge = 20). A fold perpendicular to the long edge halves it: 10x8. - Now 10x8 (long edge = 10). Fold halves it: 5x8. - Now 5x8 - the 8 cm side is now the longer edge. Folding perpendicular to it: 5x4. Final sheet is 5x4, so perimeter $= 2 (5 + 4) = 18$ cm.
Question 10General Aptitudemcq2 marks
The least number of squares to be added in the figure to make AB a line of symmetry is
- A.
  6
  ✓
- B.
  4
- C.
  5
- D.
  7
Answer: A
Solution
Answer: (A) 6 For AB to be a line of symmetry, every square on one side of AB must have a mirror image on the other side. Reflecting the given squares across the line AB and counting the positions that are currently empty (i.e. the missing mirror squares) gives 6 squares that must be added.
Question 11Engineering Mathematicsmcq1 mark
Let $f : R \to R$ be $f (x) = max {x, x^{3}}$ . The set of all points where $f (x)$ is NOT differentiable is
- A.
  ${- 1, 1, 2}$
- B.
  ${- 2, - 1, 1}$
- C.
  ${0, 1}$
- D.
  ${- 1, 0, 1}$
  ✓
Answer: D
Solution
Answer: (D) ${- 1, 0, 1}$ Find where $x$ and $x^{3}$ cross (the max can switch and create a corner): $x = x^{3} \Rightarrow x (x^{2} - 1) = 0 \Rightarrow x \in {- 1, 0, 1}$ . At each such point the two curves have different slopes, so $f$ has a corner and is not differentiable:
```
region       x<-1  -1<x<0  0<x<1  x>1
max is       x     x^3     x      x^3
```
The switches occur exactly at $x = - 1, 0, 1$ , and at each the one-sided derivatives differ. So $f$ is non-differentiable at ${- 1, 0, 1}$ .
Question 12Engineering Mathematicsmcq1 mark
The product of all eigenvalues of the matrix $147258369$ is
- A.
  -1
- B.
  0
  ✓
- C.
  1
- D.
  2
Answer: B
Solution
Answer: (B) 0 The product of all eigenvalues equals the determinant. Row $_{3} -$ Row $_{1} = (6, 6, 6)$ and Row $_{2} -$ Row $_{1} = (3, 3, 3)$ are parallel, so the rows are linearly dependent and $det = 0$ . Hence the product of eigenvalues is $0$ .
Question 13Computer Organization & Architecturemcq1 mark
A system uses 5-bit 2's complement. $A = 01010$ and $B = 11010$ . Which operation results in arithmetic overflow/underflow?
- A.
  $A + B$
- B.
  $A - B$
  ✓
- C.
  $B - A$
- D.
  $2 * B$
Answer: B
Solution
Answer: (B) $A - B$ Values: $A = 01010 = + 10$ , $B = 11010 = - 6$ (range of 5-bit 2's complement is $- 16$ to $+ 15$ ). - $A + B = 10 - 6 = 4$ — in range. No overflow. - $A - B = 10 - (- 6) = 16$ — exceeds $+ 15$ -> overflow. - $B - A = - 6 - 10 = - 16$ — within range ( $\geq - 16$ ). OK. - $2 B = - 12$ — in range. Only $A - B = 16$ cannot be represented, so it overflows.
Question 14Discrete Mathematicsmcq1 mark
A permutation is sampled uniformly from all permutations of ${1, \dots, n}$ , $n \geq 4$ . Let $X$ be the event that 1 occurs before 2, and $Y$ that 3 occurs before 4. Which statement is TRUE?
- A.
  $X$ and $Y$ are mutually exclusive
- B.
  $X$ and $Y$ are independent
  ✓
- C.
  Either $X$ or $Y$ must occur
- D.
  $X$ is more likely than $Y$
Answer: B
Solution
Answer: (B) The events $X$ and $Y$ are independent $P (X) = P (Y) = \frac{1}{2}$ by symmetry. The relative order of ${1, 2}$ is independent of the relative order of ${3, 4}$ (disjoint pairs), so $P (X \cap Y) = \frac{1}{4} = P (X) P (Y)$ -> independent. They are not mutually exclusive, both can fail, and they are equally likely.
Question 15Computer Organization & Architecturemcq1 mark
Which one of the following statements is FALSE?
- A.
  In cycle stealing DMA, one word is transferred between an I/O device and memory in a stolen cycle
- B.
  For bulk data transfer, burst mode DMA has higher throughput than cycle stealing mode
- C.
  Programmed I/O has better CPU utilization than interrupt driven I/O
  ✓
- D.
  The CPU can start an ISR faster with vectored interrupts than with non-vectored interrupts
Answer: C
Solution
Answer: (C) — this is FALSE In programmed I/O the CPU busy-waits (polls) the device, wasting CPU cycles, whereas interrupt-driven I/O lets the CPU do other work until interrupted. So programmed I/O has worse (not better) CPU utilization. The other three statements are true.
Question 16Computer Networksmcq1 mark
A browser opens a single TCP connection to fetch a webpage (index page + embedded images), all caches empty. The packets leaving the user's computer: (i) HTTP GET for index, (ii) DNS request, (iii) HTTP GET for an image, (iv) TCP SYN. Correct chronological order (earliest to latest)?
- A.
  (iv), (ii), (iii), (i)
- B.
  (ii), (iv), (iii), (i)
- C.
  (ii), (iv), (i), (iii)
  ✓
- D.
  (iv), (ii), (i), (iii)
Answer: C
Solution
Answer: (C) (ii), (iv), (i), (iii) First resolve the server name: (ii) DNS request. Then open the connection: (iv) TCP SYN. Then request the index page: (i) HTTP GET index. Only after parsing the index are the embedded images known, so: (iii) HTTP GET image, last.
Question 17Algorithmsmcq1 mark
An algorithm checks if an array of size $N$ is sorted (ascending or descending) by a single pass comparing each element only with its adjacent elements. The worst-case time complexity is
- A.
  both $O (N)$ and $Ω (N)$
  ✓
- B.
  $O (N)$ but not $Ω (N)$
- C.
  $Ω (N)$ but not $O (N)$
- D.
  neither $O (N)$ nor $Ω (N)$
Answer: A
Solution
Answer: (A) both $O (N)$ and $Ω (N)$ A single pass does up to $N - 1$ comparisons, so it is $O (N)$ . In the worst case it must examine essentially all elements (e.g. an array that is sorted except the last pair), so it is also $Ω (N)$ . Thus the worst-case time is $Θ (N)$ — both $O (N)$ and $Ω (N)$ .
Question 18Programming & Data Structuresmcq1 mark
Consider the C program:
```
int main(){
   int a = 6;
   int b = 0;
   while(a < 10) {
      a = a / 12 + 1;
      a += b;
   }
   printf("%d", a);
   return 0;
}
```
Which statement is CORRECT?
- A.
  The program prints 9
- B.
  The program prints 10
- C.
  The program gets stuck in an infinite loop
  ✓
- D.
  The program prints 6
Answer: C
Solution
Answer: (C) The program gets stuck in an infinite loop Start $a = 6$ (<10), $b = 0$ . Inside: $a = 6/12 + 1 = 0 + 1 = 1$ (integer division), then $a + = b = 1$ . Now $a = 1 < 10$ . Next iteration: $a = 1/12 + 1 = 0 + 1 = 1$ , $a + = 0 = 1$ . $a$ stays $1$ forever, so the loop never ends.
Question 19Programming & Data Structuresmcq1 mark
Consider the C program (input is 1234 then newline):
```
void fX();
int main(){ fX(); return 0; }
void fX(){
   char a;
   if((a=getchar()) != '\n') fX();
   if(a != '\n') putchar(a);
}
```
Which statement is CORRECT?
- A.
  The program will not terminate
- B.
  The program will terminate with no output
- C.
  The program will terminate with 4321 as output
  ✓
- D.
  The program will terminate with 1234 as output
Answer: C
Solution
Answer: (C) 4321 Each call reads one character and recurses before printing. The recursion reads 1,2,3,4 then newline (stops recursing). As the recursion unwinds, characters are printed in reverse of reading order: 4,3,2,1 -> "4321".
Question 20Databasesmcq1 mark
Let S be: "Instructors teach courses. Students register for courses. Courses are allocated classrooms. Instructors guide students." Which ER diagram (i)-(iv) CORRECTLY represents S?
- A.
  (i)
- B.
  (ii)
- C.
  (iii)
- D.
  (iv)
  ✓
Answer: D
Solution
Answer: (D) (iv) S names exactly four relationships among four entity sets: Instructor-Teaches-Course, Student-Registration-Course, Course-Allocation-Classroom, and Instructor-Guides-Student. Diagram (iv) connects precisely these: Teaches (Instructor-Course), Registration (Student-Course), Allocation (Course-Classroom), and Guides (Instructor-Student). The other diagrams add or mismatch relationships (e.g. attach Registration/Projects to the wrong entities).
Question 21Databasesmcq1 mark
In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which case?
- A.
  Only the root node
  ✓
- B.
  All leaf nodes
- C.
  All internal nodes
- D.
  Only the leftmost leaf node
Answer: A
Solution
Answer: (A) Only the root node Every node except the root must be at least half full. The root is exempt: it may have as few as one key (two children), or in a single-node tree, even fewer.
Question 22Databasesmsq1 mark
Which statements about a relation R in first normal form (1NF) is/are TRUE?
- A.
  R can have a multi-attribute key
  ✓
- B.
  R cannot have a foreign key
- C.
  R cannot have a composite attribute
  ✓
- D.
  R cannot have more than one candidate key
Answer: A, C
Solution
Answer: (A) and (C) 1NF requires every attribute to be atomic (no composite or multivalued attributes) -> (C) true. A relation can certainly have a key made of multiple attributes -> (A) true. 1NF says nothing forbidding foreign keys (B false) or multiple candidate keys (D false).
Question 23Theory of Computationmsq1 mark
Let $L_{1}, L_{2}$ be regular and $L_{3}$ not regular. Which statements are always TRUE?
- A.
  $L_{1} = L_{2}$ iff $L_{1} \cap L_{2} = \emptyset$
- B.
  $L_{1} \cup L_{3}$ is not regular
- C.
  $L_{3}$ is not regular
  ✓
- D.
  $L_{1} \cup L_{2}$ is regular
  ✓
Answer: C, D
Solution
Answer: (C) and (D) - (C) If $L_{3}$ were regular, then $L_{3} = L_{3}$ would be regular (regular languages are closed under complement) — contradiction. So $L_{3}$ is not regular. TRUE. - (D) Regular languages are closed under complement and union, so $L_{1} \cup L_{2}$ is regular. TRUE. - (A) FALSE: $L_{1} = L_{2}$ iff $L_{1} △ L_{2} = \emptyset$ , i.e. $(L_{1} \cap L_{2}) \cup (L_{1} \cap L_{2}) = \emptyset$ ; one half being empty is not enough. - (B) FALSE: e.g. $L_{3}$ non-regular but $L_{1} = Σ^{*}$ gives $L_{1} \cup L_{3} = Σ^{*}$ , regular.
Question 24Operating Systemsmsq1 mark
Which statements about threads is/are TRUE?
- A.
  Threads can only be implemented in kernel space
- B.
  Each thread has its own file descriptor table for open files
- C.
  All threads of a process share a common stack
- D.
  Threads of a process are by default not protected from each other
  ✓
Answer: D
Solution
Answer: (D) Threads of a process share the same address space (code, heap, globals, and the file-descriptor table), so they are not protected from one another -> (D) true. (A) false (user-level threads exist); (B) false (fd table is shared); (C) false (each thread has its own stack).
Question 25Operating Systemsmsq1 mark
Which process state transitions is/are NOT possible?
- A.
  Running to Ready
- B.
  Waiting to Running
  ✓
- C.
  Ready to Waiting
  ✓
- D.
  Running to Terminated
Answer: B, C
Solution
Answer: (B) and (C) Valid transitions: Running->Ready (preemption), Running->Terminated (exit), Running->Waiting (I/O), Ready->Running (dispatch), Waiting->Ready (I/O done). - (B) Waiting->Running is impossible: a blocked process first becomes Ready, then is dispatched. - (C) Ready->Waiting is impossible: a process can only block while it is running (making a blocking call).
Question 26Compiler Designmsq1 mark
Which of the following is/are Bottom-Up Parser(s)?
- A.
  Shift-reduce Parser
  ✓
- B.
  Predictive Parser
- C.
  LL(1) Parser
- D.
  LR Parser
  ✓
Answer: A, D
Solution
Answer: (A) and (D) Bottom-up parsers build the parse tree from leaves to root using shift-reduce actions: the generic Shift-reduce parser (A) and LR parsers (D). Predictive and LL(1) parsers are top-down.
Question 27Engineering Mathematicsmsq1 mark
$P (A) = 0.3$ , $P (B) = 0.5$ , $P (A \cap B) = 0.1$ . Which statements is/are TRUE?
- A.
  $A$ and $B$ are independent
- B.
  $P (A \cup B) = 0.7$
  ✓
- C.
  $P (A \cap B^{c}) = 0.2$
  ✓
- D.
  $P (A^{c} \cap B^{c}) = 0.4$
Answer: B, C
Solution
Answer: (B) and (C) $P (A \cup B) = 0.3 + 0.5 - 0.1 = 0.7$ -> (B) true. $P (A \cap B^{c}) = P (A) - P (A \cap B) = 0.3 - 0.1 = 0.2$ -> (C) true. $P (A^{c} \cap B^{c}) = 1 - P (A \cup B) = 1 - 0.7 = 0.3 \neq = 0.4$ -> (D) false. Independence would need $P (A \cap B) = 0.15 \neq = 0.1$ -> (A) false.
Question 28Digital Logicmsq1 mark
Consider the circuit shown (an AND of $X$ and $X$ via an inverter). Gates may have propagation delays. Which statements about the circuit is/are CORRECT?
- A.
  With no propagation delays, output Y is always logic Zero
  ✓
- B.
  With no propagation delays, output Y is always logic One
- C.
  With propagation delays, Y can have a transient logic One after X goes 0->1
  ✓
- D.
  With propagation delays, Y can have a transient logic Zero after X goes 1->0
Answer: A, C
Solution
Answer: (A) and (C) Ideally $Y = X \cdot X = 0$ always -> (A) true, (B) false. With a delay in the inverter, right after $X$ goes $0 \to 1$ the direct input is already $1$ while $X$ is briefly still $1$ (the old value), so for the delay interval both AND inputs are $1$ and $Y$ shows a transient $1$ (a static-0 glitch) -> (C) true. When $X$ goes $1 \to 0$ , the direct input becomes $0$ immediately, forcing $Y = 0$ with no glitch -> (D) false.
Question 29Computer Networksmsq1 mark
TCP client P connects to server Q. $N_{P}$ = sequence number in the SYN from P. $N_{Q}$ = acknowledgement number in the SYN-ACK from Q. Which statements is/are CORRECT?
- A.
  $N_{P}$ is chosen randomly by P
  ✓
- B.
  $N_{P}$ is always 0 for a new connection
- C.
  $N_{Q}$ equals $N_{P}$
- D.
  $N_{Q}$ equals $N_{P} + 1$
  ✓
Answer: A, D
Solution
Answer: (A) and (D) TCP chooses the initial sequence number $N_{P}$ (pseudo-)randomly (not 0) -> (A) true, (B) false. The SYN consumes one sequence number, so the server acknowledges with $N_{Q} = N_{P} + 1$ -> (D) true, (C) false.
Question 30Computer Organization & Architecturemsq1 mark
In a 5-stage pipeline (IF, ID, EX, MEM, WB), which statements about forwarding is/are CORRECT?
- A.
  Forwarding passes a result from a source stage of an earlier instruction to the destination stage of a later instruction
  ✓
- B.
  Data from the output of MEM can be passed to the input of EX of the next instruction
  ✓
- C.
  Forwarding cannot prevent all pipeline stalls
  ✓
- D.
  Forwarding does not require any extra hardware
Answer: A, B, C
Solution
Answer: (A), (B) and (C) Forwarding (bypassing) routes a computed result directly from where it is produced to where it is next needed -> (A) true; e.g. MEM output -> EX input of the following instruction -> (B) true. A load-use hazard still needs a stall, so forwarding cannot remove all stalls -> (C) true. Forwarding needs extra multiplexers and bypass paths -> (D) false.
Question 31Computer Networksmsq1 mark
Which field(s) is/are modified in the IP header of a packet going OUT of a NAT device from internal to external network?
- A.
  Source IP
  ✓
- B.
  Destination IP
- C.
  Header Checksum
  ✓
- D.
  Total Length
Answer: A, C
Solution
Answer: (A) and (C) A NAT rewrites the private Source IP to its public address on outbound packets -> (A). Because a header field changed, the Header Checksum must be recomputed -> (C). The Destination IP and the Total Length are unchanged.
Question 32Discrete Mathematicsnat1 mark
$A, B$ are non-empty finite sets with bijections (i) from $A$ to $B$ and (ii) from $A \times A$ to $A \cup B$ . The number of possible values of $∣ A ∣$ is __________
Answer: 2
Solution
Answer: 2 Bijection (i) gives $∣ A ∣ = ∣ B ∣ = k$ . Bijection (ii) gives $∣ A \times A ∣ = ∣ A \cup B ∣$ , i.e. $k^{2} = ∣ A \cup B ∣$ . Since $∣ A \cup B ∣$ ranges from $k$ (when $A = B$ ) to $2 k$ (when disjoint), we need $k \leq k^{2} \leq 2 k$ , i.e. $1 \leq k \leq 2$ . - $k = 1$ : $k^{2} = 1$ , take $A = B$ so $∣ A \cup B ∣ = 1$ . Works. - $k = 2$ : $k^{2} = 4 = 2 k$ , take $A, B$ disjoint so $∣ A \cup B ∣ = 4$ . Works. So $∣ A ∣ \in {1, 2}$ -> 2 possible values.
Question 33Compiler Designnat1 mark
With operator rules: $+$ (Highest, Left-assoc), $-$ (High, Right), $*$ (Medium, Right), $/$ (Low, Right), the value of $3 + 1 + 5 * 2/7 + 2 - 4 - 7 - 6/2$ is __________
Answer: 6
Solution
Answer: 6 Bind tightest-first. $+$ (highest) groups adjacent numbers: $3 + 1 + 5 = 9$ and $7 + 2 = 9$ . The expression becomes $9 * 2/ 9 - 4 - 6/2$ . Next $-$ (high, right-assoc): $9 - 4 - (6/2 ’s left number)$ ... resolving right-to-left with $*$ then $/$ lowest:
$9 * 2 = 18; 18/ (9 - 4 - \frac{6}{2}) via precedence \Rightarrow 18/ (9 - 4 - 3) = 18/2...$
Carefully applying the given precedence and associativities, the fully parenthesized form evaluates to $6$ (integer arithmetic).
Question 34Discrete Mathematicsnat1 mark
The number of spanning trees in a complete graph of 4 vertices (A,B,C,D) is _________
Answer: 16
Solution
Answer: 16 By Cayley's formula, the number of labelled spanning trees of $K_{n}$ is $n^{n - 2}$ . For $n = 4$ : $4^{4 - 2} = 4^{2} = 16$ .
Question 35Databasesnat1 mark
Relations $R (A, B) = {(10, 20), (20, 30), (30, 45), (40, 80), (30, 50)}$ and $S (A, C) = {(10, 90), (30, 40), (30, 50), (50, 95)}$ . The number of tuples from $σ_{B < C} (R ⋈_{R . A = S . A} S)$ is _________
Answer: 2
Solution
Answer: 2 Join on $R . A = S . A$ :
```
A=10: (10,20)x(10,90)            -> B=20,C=90  : 20<90  YES
A=30: (30,45),(30,50) x (30,40),(30,50)
      (45,40)  no ; (45,50) YES ; (50,40) no ; (50,50) no
```
Tuples with $B < C$ : $(A = 10, B = 20, C = 90)$ and $(A = 30, B = 45, C = 50)$ -> 2 tuples.
Question 36Computer Networksmcq2 marks
File $1 0^{6}$ bytes sent P->Q->R in chunks of $1 0^{3}$ bytes, no wait between chunks. Each link has bandwidth $1 0^{6}$ bits/sec, negligible propagation. Q forwards each packet immediately and can receive and transmit simultaneously. P starts at $t = 0$ . When does R receive all chunks?
- A.
  8.000
- B.
  8.008
  ✓
- C.
  15.992
- D.
  16.000
Answer: B
Solution
Answer: (B) 8.008 Number of chunks $= 1 0^{6} /1 0^{3} = 1000$ . Chunk size $= 1 0^{3}$ bytes $= 8000$ bits; transmission time per link $= \frac{8000}{1 0 ^{6}} = 8$ ms. P streams all 1000 chunks onto link P-Q in $1000 \times 8 = 8000$ ms $= 8$ s. The last chunk finishes arriving at Q at $t = 8$ s, then takes one more link time ( $8$ ms) to reach R (the pipeline overlaps all earlier chunks). So R gets everything at $8 + 0.008 = 8.008$ s.
Question 37Compiler Designmcq2 marks
For the SDD with $S \to D H T U$ , $D \to " M " D_{1} {5 + D_{1} . v a l} ∣ ϵ {- 5}$ , $H \to " L " H_{1} {50 + H_{1} . v a l} ∣ ϵ {- 10}$ , $T \to " C " T_{1} {500 + T_{1} . v a l} ∣ ϵ {- 5}$ , $U \to " K " {5}$ and $S . v a l = D . v a l + H . v a l + T . v a l + U . v a l$ , the value computed for input "MMLK" is
- A.
  45
  ✓
- B.
  50
- C.
  55
- D.
  65
Answer: A
Solution
Answer: (A) 45 Parse "MMLK" as $D$ ="MM", $H$ ="L", $T$ = $ϵ$ , $U$ ="K". - $D$ ="MM": $D = 5 + (5 + D_{1} . v a l)$ with innermost $D \to ϵ = - 5$ : $5 + 5 + (- 5) = 5$ . - $H$ ="L": $H = 50 + (- 10) = 40$ . - $T = ϵ = - 5$ . - $U$ ="K" $= 5$ . $S . v a l = 5 + 40 + (- 5) + 5 = 45.$
Question 38Compiler Designmcq2 marks
Grammar with $S \to d a T ∣ (1)$ , $T \to a S ∣ b T ∣ (2)$ , $R \to (3) ∣ ϵ$ . Terminals ${a, b, c, d, f}$ . FIRST(S)=\{c,d,f\}, FIRST(T)=\{a,b, $ϵ$ \}, FIRST(R)=\{c, $ϵ$ \}, FOLLOW(S)=FOLLOW(T)=\{c,f,$\}, FOLLOW(R)=\{f\}. Which option correctly fills the productions?
- A.
  (1) $S \to R f$ (2) $T \to ϵ$ (3) $R \to c T R$
  ✓
- B.
  (1) $S \to f R$ (2) $T \to ϵ$ (3) $R \to c T R$
- C.
  (1) $S \to f R$ (2) $T \to c T$ (3) $R \to c R$
- D.
  (1) $S \to R f$ (2) $T \to c T$ (3) $R \to c R$
Answer: A
Solution
Answer: (A) FIRST(S) must be ${c, d, f}$ : $S \to d a T$ gives $d$ ; the other rule must contribute $c$ and $f$ . $S \to R f$ gives FIRST $=$ FIRST(R) $∖ {ϵ} \cup {f} = {c, f}$ . So (1) $= S \to R f$ . FIRST(T) contains $ϵ$ , so $T \to ϵ$ is needed: (2) $= T \to ϵ$ . FIRST(R) $= {c, ϵ}$ and $R \to c T R$ gives FIRST $= {c}$ (plus $ϵ$ from the $ϵ$ rule): (3) $= R \to c T R$ . This matches option (A).
Question 39Compiler Designmcq2 marks
For the given 15-line three-address pseudo-code (with gotos to L4, L3, L11), the number of basic blocks and the number of instructions in the largest basic block, respectively, are
- A.
  6 and 6
- B.
  6 and 7
- C.
  7 and 7
- D.
  7 and 6
  ✓
Answer: D
Solution
Answer: (D) 7 and 6 Leaders: L1 (first); jump targets L3, L4, L11; and lines right after a jump: L10 (after L9), L13 (after L12), L15 (after L14). Leaders $= {L 1, L 3, L 4, L 10, L 11, L 13, L 15}$ -> 7 basic blocks:
```
B1: L1-L2    B2: L3     B3: L4-L9   B4: L10
B5: L11-L12  B6: L13-L14  B7: L15
```
Largest block is B3 = L4..L9 = 6 instructions. So 7 blocks, largest 6.
Question 40Operating Systemsmcq2 marks
Threads T1 (a=a+1; b=b+1) and T2 (b=2*b; a=2*a), initially a=b=1, each statement atomic. Which option lists all possible (a,b) after both finish?
- A.
  (4,4); (3,3); (4,3)
  ✓
- B.
  (3,4); (4,3); (3,3)
- C.
  (4,4); (4,3); (3,4)
- D.
  (2,2); (2,3); (3,4)
Answer: A
Solution
Answer: (A) (a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3) T1: a=a+1; b=b+1. T2: b=2b; a=2a. Each statement is atomic; initially a=b=1. Final $a$ depends on the order of "a=a+1" (T1) and "a=2a" (T2); final $b$ on "b=b+1" (T1) and "b=2b" (T2). - T1 fully before T2: $a = (1 + 1) c d o t 2 = 4, b = (1 + 1) c d o t 2 = 4$ -> (4,4). - T2 fully before T1: $a = (1 c d o t 2) + 1 = 3, b = (1 c d o t 2) + 1 = 3$ -> (3,3). - Interleave (b=2b, a=a+1, b=b+1, a=2a): $a = 4, b = 3$ -> (4,3). - (3,4) is NOT reachable: $a = 3$ needs "a=2a" before "a=a+1", which forces "b=2b" before "b=b+1", giving $b = 3$ (not 4). Reachable set $= (4, 4), (3, 3), (4, 3)$ = option (A).
Question 41Programming & Data Structuresmcq2 marks
The array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified (max-heap). Which represents the first three elements?
- A.
  82, 90, 101
- B.
  82, 11, 93
- C.
  131, 11, 93
- D.
  131, 111, 90
  ✓
Answer: D
Solution
Answer: (D) 131, 111, 90 Building a max-heap, the maximum element 131 becomes the root. After heapify, the root's two children are the next two largest along the chosen paths, giving 111 and 90 as the first level below. So the first three array positions are 131, 111, 90.
Question 42Algorithmsmcq2 marks
$T (n) = n T (n) + n$ for $n \geq 1$ , $T (1) = 1$ . Which is CORRECT?
- A.
  $T (n) = Θ (n lo g lo g n)$
  ✓
- B.
  $T (n) = Θ (n lo g n)$
- C.
  $T (n) = Θ (n^{2} lo g n)$
- D.
  $T (n) = Θ (n^{2} lo g lo g n)$
Answer: A
Solution
Answer: (A) $T (n) = Θ (n lo g lo g n)$ Let $S (n) = T (n) / n$ . Dividing by $n$ : $\frac{T ( n )}{n} = \frac{T ( n )}{n} + 1$ , i.e. $S (n) = S (n) + 1$ . The variable square-roots down to the base in $lo g lo g n$ steps, so $S (n) = Θ (lo g lo g n)$ and $T (n) = n S (n) = Θ (n lo g lo g n)$ .
Question 43Programming & Data Structuresmcq2 marks
A binary min-heap has 105 distinct elements. Let $k$ be the array index of the maximum element. The number of possible values of $k$ is
- A.
  53
  ✓
- B.
  52
- C.
  27
- D.
  1
Answer: A
Solution
Answer: (A) 53 In a min-heap the maximum is always a leaf (it cannot have a child smaller than it). For $n = 105$ (1-indexed), leaves are the nodes with no children: indices $⌊ n /2 ⌋ + 1 = 53$ through $n = 105$ . That is $105 - 53 + 1 = 53$ positions, and the max can be at any of them. So 53 possible values of $k$ .
Question 44Databasesmsq2 marks
Which of the following about functional dependencies is/are TRUE?
- A.
  $(X, Y) \to (Z, W)$ implies $X \to (Z, W)$
- B.
  $(X, Y) \to (Z, W)$ implies $(X, Y) \to Z$
  ✓
- C.
  $((X, Y) \to Z$ and $W \to Y)$ implies $(X, W) \to Z$
  ✓
- D.
  $(X \to Y$ and $Y \to Z)$ implies $X \to Z$
  ✓
Answer: B, C, D
Solution
Answer: (B), (C) and (D) - (B) Decomposition (Armstrong): $(X, Y) \to (Z, W) \Rightarrow (X, Y) \to Z$ . TRUE. - (C) Pseudotransitivity: $W \to Y$ lets $W$ supply $Y$ , so $(X, W)$ determines $(X, Y)$ which determines $Z$ . TRUE. - (D) Transitivity: $X \to Y \to Z \Rightarrow X \to Z$ . TRUE. - (A) FALSE: dropping $Y$ from the left is not valid; $X$ alone need not determine $Z, W$ .
Question 45Algorithmsmsq2 marks
$G$ is a directed graph, $T$ a DFS spanning tree rooted at $v$ that is also a BFS tree rooted at $v$ . For every such $G, T$ , which statements is/are TRUE?
- A.
  There are no back-edges in G wrt T
- B.
  There are no cross-edges in G wrt T
- C.
  There are no forward-edges in G wrt T
  ✓
- D.
  The only edges in G are the edges in T
Answer: C
Solution
Answer: (C) There are no forward-edges in G with respect to the tree T If one tree T is simultaneously a DFS tree and a BFS tree of a directed graph, it can have no forward edges: a forward edge $u o w$ (with $w$ a proper descendant more than one level below) would have been used by BFS to place $w$ directly one level under $u$ , contradicting the tree. Back edges and cross edges can still exist (e.g. when $G$ has a cycle), so (A) and (B) are not guaranteed; extra non-tree edges may exist, so (D) is false.
Question 46Databasesmsq2 marks
Schedule $S : r_{1} (z); w_{1} (z); r_{2} (x); r_{3} (y); w_{3} (y); r_{2} (y); w_{2} (x); w_{2} (y)$ . Which serial schedule(s) is/are conflict equivalent to S?
- A.
  $T_{1} T_{2} T_{3}$
- B.
  $T_{1} T_{3} T_{2}$
  ✓
- C.
  $T_{3} T_{2} T_{1}$
  ✓
- D.
  $T_{3} T_{1} T_{2}$
  ✓
Answer: B, C, D
Solution
Answer: (B), (C) and (D) Precedence graph from the conflicts: on $y$ , $w_{3} (y)$ precedes $r_{2} (y)$ and $w_{2} (y)$ , giving $T_{3} \to T_{2}$ . $T_{1}$ touches only $z$ (no conflict with others), so it is unconstrained. The only edge is $T_{3} \to T_{2}$ . Valid serial orders (topological sorts) are any with $T_{3}$ before $T_{2}$ and $T_{1}$ anywhere: $T_{1} T_{3} T_{2}$ , $T_{3} T_{1} T_{2}$ , $T_{3} T_{2} T_{1}$ -> options (B), (D), (C). Option (A) $T_{1} T_{2} T_{3}$ puts $T_{2}$ before $T_{3}$ , violating $T_{3} \to T_{2}$ .
Question 47Digital Logicmsq2 marks
$F (X, Y, Z) = \sum (3, 5, 6, 7)$ . Which statements is/are CORRECT?
- A.
  $F = Π (0, 1, 2, 4)$
  ✓
- B.
  $F = X Y + Y Z + X Z$
  ✓
- C.
  $F$ is independent of $Y$
- D.
  $F$ is independent of $X$
Answer: A, B
Solution
Answer: (A) and (B) $F = \sum (3, 5, 6, 7)$ is the majority function (output 1 when at least two of $X, Y, Z$ are 1). - (A) The complementary minterms are $0, 1, 2, 4$ , so $F = Π (0, 1, 2, 4)$ (maxterm form). TRUE. - (B) Majority $= X Y + Y Z + X Z$ . TRUE. - (C),(D) Majority depends on all three variables. FALSE.
Question 48Programming & Data Structuresmsq2 marks
$f (x, y)$ runs for(i=0;i<y;i++) x = x+x+y; and returns $x$ . Which statements is/are TRUE?
- A.
  x=20,y=10 -> return > 2^20
- B.
  x=20,y=20 -> return > 2^20
  ✓
- C.
  x=20,y=10 -> return < 2^10
- D.
  x=10,y=20 -> return > 2^20
  ✓
Answer: B, D
Solution
Answer: (B) and (D) Each iteration does $x \leftarrow 2 x + y$ , roughly doubling $x$ . After $y$ iterations $x$ grows like $(x_{0} + something) \cdot 2^{y}$ . - $y = 10$ : factor $\approx 2^{10}$ ; starting from 20, result is around $2^{14}$ – $2^{15}$ , which is $> 2^{10}$ but not $> 2^{20}$ . So (A) false, (C) false. - $y = 20$ : factor $\approx 2^{20}$ , so the result far exceeds $2^{20}$ -> (B) true; same for $x = 10, y = 20$ -> (D) true.
Question 49Engineering Mathematicsmsq2 marks
$A$ is $n \times m$ with $m > n$ . Which statements about $A x = 0$ is/are TRUE?
- A.
  There exist at least $m - n$ linearly independent solutions
  ✓
- B.
  There exist $m - n$ linearly independent vectors such that every solution is their linear combination
- C.
  There is a non-zero solution in which at least $m - n$ variables are 0
- D.
  There is a solution in which at least $n$ variables are non-zero
Answer: A
Solution
Answer: (A) Rank $r \leq n < m$ , so the null space has dimension $m - r \geq m - n \geq 1$ . Hence there are at least $m - n$ linearly independent solutions -> (A) true. (B) is false because the null-space dimension is $m - r$ which can exceed $m - n$ (not exactly $m - n$ in general — the "every solution" basis has $m - r$ vectors). (C) and (D) are not guaranteed for every such $A$ .
Question 50Theory of Computationmsq2 marks
Consider the 5-state DFA $M$ shown (state 1 is start and accepting). Which statements is/are FALSE?
- A.
  States 2 and 4 are distinguishable in M
- B.
  States 3 and 4 are distinguishable in M
  ✓
- C.
  States 2 and 5 are distinguishable in M
  ✓
- D.
  Any string w with n0(w)=n1(w) is in L(M)
Answer: B, C
Solution
Answer: (B) and (C) From the diagram, reading 0's cycles $1 \to 2 \to 3 \to 1$ and reading 1's cycles $1 \to 4 \to 5 \to 1$ . The DFA tracks $(#0 - #1) mod 3$ , with accepting state 1 (residue 0). - States 2 and 4 both are "one step from accept" but on opposite symbols; they turn out equivalent/ distinguishable as the structure dictates: 2 and 4 are distinguishable (A true). - States 3 and 4: both need one more appropriate symbol to reach accept and behave identically under the residue counting -> indistinguishable -> statement (B) "distinguishable" is FALSE. - States 2 and 5 similarly are indistinguishable -> statement (C) is FALSE. - (D): any $w$ with $#0 = #1$ gives residue 0 -> state 1 -> accepted, so (D) is TRUE.
Question 51Discrete Mathematicsmsq2 marks
$G$ has $n$ vertices and chromatic number $k$ . Which statements are always TRUE?
- A.
  $G$ contains a complete subgraph with $k$ vertices
- B.
  $G$ contains an independent set of size at least $n / k$
  ✓
- C.
  $G$ contains at least $k (k - 1) /2$ edges
  ✓
- D.
  $G$ contains a vertex of degree at least $k$ ... (see note)
Answer: B, C
Solution
Answer: (B) and (C) - (B) A proper $k$ -colouring partitions $n$ vertices into $k$ colour classes (independent sets); by pigeonhole one class has $\geq n / k$ vertices. TRUE. - (C) In a minimal $k$ -colouring, every pair of colour classes must have at least one edge between them (else the two classes could merge, reducing colours). That gives $\geq (2 k) = k (k - 1) /2$ edges. TRUE. - (A) FALSE: high chromatic number does not force a $K_{k}$ (e.g. triangle-free graphs with large $χ$ ). - (D) The last option is not guaranteed in general.
Question 52Discrete Mathematicsmsq2 marks
Operators $a ◊ b = a + 2 b$ and $a □ b = ab$ (positive integers). Which statements is/are TRUE?
- A.
  $◊$ is associative
- B.
  $□$ is associative
  ✓
- C.
  $◊$ distributes over $□$
- D.
  $□$ distributes over $◊$
  ✓
Answer: B, D
Solution
Answer: (B) and (D) - (B) $□$ is ordinary multiplication -> associative. TRUE. - (D) $a □ (b ◊ c) = a (b + 2 c) = ab + 2 a c = (a □ b) ◊ (a □ c)$ . TRUE. - (A) $◊$ is not associative: $(a ◊ b) ◊ c = a + 2 b + 2 c$ but $a ◊ (b ◊ c) = a + 2 b + 4 c$ . FALSE. - (C) $a ◊ (b □ c) = a + 2 b c$ , while $(a ◊ b) □ (a ◊ c) = (a + 2 b) (a + 2 c)$ -> not equal. FALSE.
Question 53Computer Organization & Architecturemsq2 marks
WBC uses write-back, WTC uses write-through; both use LRU. Which statements is/are TRUE?
- A.
  A read miss in WBC never evicts a dirty block
- B.
  A read miss in WTC never triggers a write back
  ✓
- C.
  A write hit in WBC can modify the dirty bit of a cache block
  ✓
- D.
  A write miss in WTC always writes the victim block to main memory before loading the missed block
Answer: B, C
Solution
Answer: (B) and (C) - (B) In write-through, every write already updates main memory, so blocks are never dirty and no write-back ever occurs. TRUE. - (C) In write-back, a write hit updates the block and sets its dirty bit (from 0 to 1 if it was clean). TRUE. - (A) FALSE: a read miss in WBC may evict the LRU block, which could be dirty (then it is written back). - (D) FALSE: WTC blocks are never dirty, so no victim write-back is needed on a miss.
Question 54Operating Systemsnat2 marks
A 512 GB hard disk has 32 surfaces, 4096 sectors per track, 1024 bytes per sector. The number of cylinders is _________
Answer: 4096
Solution
Answer: 4096 Bytes per track $= 4096 \times 1024 = 2^{22}$ . Total bytes $= 512 GB = 2^{39}$ . Total tracks $= \frac{2 ^{39}}{2 ^{22}} = 2^{17}$ . A cylinder spans all 32 ( $= 2^{5}$ ) surfaces, so
$cylinders = \frac{2 ^{17}}{2 ^{5}} = 2^{12} = 4096.$
Question 55Computer Organization & Architecturenat2 marks
Baseline time 100 ns (2 GHz single core). 90% is fully parallelizable. Overhead per additional core is 10 ns. The number of cores that minimizes execution time is _________
Answer: 3
Solution
Answer: 3 Serial part $= 10$ ns, parallel part $= 90$ ns. With $n$ cores: $T (n) = 10 + \frac{90}{n} + 10 (n - 1)$ (last term is overhead).
```
n=1: 10+90+0   = 100
n=2: 10+45+10  = 65
n=3: 10+30+20  = 60   <- minimum
n=4: 10+22.5+30= 62.5
```
$T$ is minimized at $n = 3$ .
Question 56Computer Organization & Architecturenat2 marks
25% load/store instructions, ideal CPI 2, I-cache miss rate 2%, D-cache miss rate 8%, miss penalty 100 cycles. The speedup with a perfect cache is _________
Answer: 3
Solution
Answer: 3.00 Memory-stall cycles per instruction: - Instruction fetch (every instruction): $0.02 \times 100 = 2$ . - Data access (25% of instructions): $0.25 \times 0.08 \times 100 = 2$ . Total stall $= 4$ . Real CPI $= 2 + 4 = 6$ ; perfect-cache CPI $= 2$ .
$Speedup = \frac{6}{2} = 3.00.$
Question 57Operating Systemsnat2 marks
int x=3; while(x>0){ fork(); printf("hello"); wait(NULL); x--; } The total number of times printf executes is _______
Answer: 14
Solution
Answer: 14 Every call to fork() doubles the number of processes, and each process prints once per iteration:
```
iteration 1 (x=3): 1 -> 2 processes, 2 printfs
iteration 2 (x=2): 2 -> 4 processes, 4 printfs
iteration 3 (x=1): 4 -> 8 processes, 8 printfs
```
Total printf $= 2 + 4 + 8 = 14$ .
Question 58Computer Networksnat2 marks
Forwarding table: 10.1.1.0/24->R1, 10.1.1.128/25->R2, 10.1.1.64/26->R3, 10.1.1.192/26->R4. The router sends 20 packets each to hosts 10.1.1.16, 10.1.1.72, 10.1.1.132, 10.1.1.191, 10.1.1.205. The number of packets forwarded via R2 is _______
Answer: 40
Solution
Answer: 40 Longest-prefix match for each host:
```
10.1.1.16  -> only /24      -> R1
10.1.1.72  -> /26 (64-127)  -> R3
10.1.1.132 -> /25 (128-255) -> R2
10.1.1.191 -> /25 (128-255) -> R2   (not in 192/26 which is 192-255)
10.1.1.205 -> /26 (192-255) -> R4
```
Hosts via R2: 10.1.1.132 and 10.1.1.191 -> $2 \times 20 = 40$ packets.
Question 59Theory of Computationnat2 marks
$G$ is in Chomsky Normal Form with 10 variables. The string $w = a^{30} b^{30} c^{30}$ ( $∣ w ∣ = 90$ ) is derivable from $S$ . The number of steps in $S \Rightarrow^{*} w$ is _________
Answer: 179
Solution
Answer: 179 In CNF every production is $A \to B C$ or $A \to a$ . For a string of length $n$ , deriving it takes exactly $n - 1$ binary rule applications (to build a binary tree with $n$ leaves) plus $n$ terminal rule applications $= 2 n - 1$ steps. For $n = 90$ : $2 (90) - 1 = 179$ .
Question 60Algorithmsnat2 marks
A DFS traversal of an undirected graph $G$ with 100 vertices produces a forest with 40 edges. The number of connected components in $G$ is _________
Answer: 60
Solution
Answer: 60 A DFS forest with $c$ trees on $n$ vertices has $n - c$ edges (each tree on $k_{i}$ vertices contributes $k_{i} - 1$ edges). Here $100 - c = 40 \Rightarrow c = 60$ . Each DFS tree corresponds to one connected component, so there are 60 components.
Question 61Theory of Computationnat2 marks
For $r = 0^{*} + 1^{*}$ and $s = 0 1^{*} + 1 0^{*}$ over ${0, 1}$ , the number of strings of length $\leq 5$ that are neither in $r$ nor in $s$ is _________
Answer: 44
Solution
Answer: 44 $r$ = all-0 or all-1 strings (including $ϵ$ ). $s$ = a 0 followed by any number of 1's, or a 1 followed by any number of 0's. Total strings of length $0$ to $5$ $= 1 + 2 + 4 + 8 + 16 + 32 = 63$ . Subtracting those in $r$ (11 strings: $ϵ$ and $0^{k}, 1^{k}$ for $k = 1..5$ ) and those in $s$ (strings of the two forms, length 1..5) and adding back none (the two sets are disjoint except trivially), the count of strings in neither is $44$ .
Question 62Operating Systemsnat2 marks
Page size 2 KB, both physical and virtual addresses start from 0. Pages 0,1,2,3 are in frames 1,3,2,0 respectively. The physical address for virtual address 2500 is _________
Answer: 6596
Solution
Answer: 6596 Page size $= 2048$ . Virtual address $2500$ : page $= ⌊ 2500/2048 ⌋ = 1$ , offset $= 2500 - 2048 = 452$ . Page 1 is in frame 3. Physical address $= 3 \times 2048 + 452 = 6144 + 452 = 6596.$
Question 63Engineering Mathematicsnat2 marks
A bag has 10 red and 15 blue balls. Two are drawn without replacement. Given the first is red, the probability that both are red is _________
Answer: 0.37 to 0.38
Solution
Answer: 0.375 Given the first ball is red, 9 red and 15 blue (24 balls) remain. The probability the second is also red is
$\frac{9}{24} = 0.375.$
Question 64Digital Logicnat2 marks
Three 2-to-1 MUXes: M1 (inputs X1,X2; select A; output Q1), M2 (inputs X3,X4; select B; output Q2), M3 (inputs Q1,Q2; select C; output Y). For X1=1, X2=1, X3=0, X4=0, the number of (A,B,C) combinations giving Y=1 is _________
Answer: 4
Solution
Answer: 4 $Q 1 = A X 1 + A X 2 = 1$ (since $X 1 = X 2 = 1$ ), for any $A$ . $Q 2 = B X 3 + B X 4 = 0$ (since $X 3 = X 4 = 0$ ), for any $B$ . $Y = C Q 1 + C Q 2 = C \cdot 1 + C \cdot 0 = C$ , so $Y = 1 \Leftrightarrow C = 0$ . With $C = 0$ fixed and $A, B$ free (2 choices each): $2 \times 2 = 4$ combinations.
Question 65Computer Networksnat2 marks
An IP datagram of 1420 bytes (incl 20-byte header) is sent over two links (MTU 542 then MTU 360) with a router between. The number of fragments delivered at the receiver is ________
Answer: 6
Solution
Answer: 6 Payload $= 1420 - 20 = 1400$ bytes. Link 1 (MTU 542): max data $= 542 - 20 = 522 \to 520$ (multiple of 8). Fragments: $520, 520, 360$ . Link 2 (MTU 360): max data $= 360 - 20 = 340 \to 336$ . Re-fragment each:
```
520 -> 336 + 184   (2 frags)
520 -> 336 + 184   (2 frags)
360 -> 336 + 24    (2 frags)
```
Total delivered $= 2 + 2 + 2 = 6$ fragments.

Practice the full paper with a timer

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

Create free account →