The _________ is too high for it to be considered _________.

D. Answer: (D) fare / fair The first blank needs "fare" (the price/charge), which can be "too high"; the second needs "fair" (reasonable/just). So: The fare is too high for it to be considered fair.

A function y(x) on [0,1] is y(x)=2 for 0\le x<\tfrac13, y(x)=3 for \tfrac13\le x<\tfrac34, y(x)=1 for \tfrac34\le x\le1. The area under the curve on [0,1] is

C. Answer: (C) \dfrac{13}{6} Area = sum of rectangle areas: 2\cdot\tfrac13 + 3\cdot\left(\tfrac34-\tfrac13\right) + 1\cdot\left(1-\tfrac34\right)=\tfrac23+3\cdot\tfrac{5}{12}+\tfrac14=\tfrac{8}{12}+\tfrac{15}{12}+\tfrac{3}{12}=\tfrac{26}{12}=\tfrac{13}{6}.

Let r be a root of x^2+2x+6=0. The value of (r+2)(r+3)(r+4)(r+5) is

D. Answer: (D) -126 From r^2+2r+6=0, r^2=-2r-6. Pair the factors: (r+2)(r+5)=r^2+7r+10 and (r+3)(r+4)=r^2+7r+12. Let t=r^2+7r=(-2r-6)+7r=5r-6. Then the product =(t+10)(t+12)=t^2+22t+120. With t=5r-6: t^2=-110r-114 and 22t=110r-132, so the product =-110r-114+110r-132+120=-126.

Four statements: (1) All students are inquisitive. (2) Some students are inquisitive. (3) No student is inquisitive. (4) Some students are not inquisitive. Assuming at least one student exists, which two CANNOT be true simultaneously?

A. Answer: (A) Statement 1 and Statement 3 "All students are inquisitive" (1) and "No student is inquisitive" (3) are contraries — with at least one student they cannot both hold. The other pairs can be simultaneously true.

A player has two plates painted with the letters shown (A and D). Using all five plates exactly once (plates can be rotated in their plane), which option of three additional plates lets the player form a five-letter palindrome?

B. Answer: (B) R, A, R Combining the two given plates (A and D) with option (B)'s plates (R, A, R) gives the letters \{R,A,D,A,R\}, which arrange into the palindrome "RADAR". (Rotations let a plate be reused in its flipped orientation where needed.) None of the other option sets can form a five-letter palindrome with A and D.

Passage: In organizations with good work culture, metrics help improve outcomes; the same metrics are counterproductive in organizations with poor work culture. Which is the CORRECT logical inference?

B. Answer: (B) Metrics are useful in organizations with good work culture The passage directly states that in organizations with good work culture, metrics help improve outcomes — i.e. they are useful there.

Boys were 65% of those who appeared for a test; girls were the rest and accounted for 60% of the qualified candidates. Which is the correct inference?

D. Answer: (D) The number of boys who qualified is less than the number of girls who qualified Girls account for 60% of qualified candidates (more than half), so fewer than half of the qualified are boys. Hence fewer boys qualified than girls — even though more boys appeared.

A box has 3 green and 2 orange balls. If a green ball is drawn, it is NOT replaced; if an orange ball is drawn, it is replaced with another orange ball. After the first draw, what is the probability of getting an orange ball in the next draw?

D. Answer: (D) \dfrac{23}{50} - First draw green (P=\tfrac35): box becomes 2 green, 2 orange, so P(\text{orange next})=\tfrac24=\tfrac12. - First draw orange (P=\tfrac25): orange is replaced by orange, box stays 3 green, 2 orange, so P(\text{orange next})=\tfrac25. Total =\tfrac35\cdot\tfrac12+\tfrac25\cdot\tfrac25=\tfrac{3}{10}+\tfrac{4}{25}=\tfrac{15}{50}+\tfrac{8}{50}=\tfrac{23}{50}.

The corners and mid-points of the sides of a triangle are labelled P, Q, R, S, T, U (in some order). Given: PR is parallel to QS; P is on the side opposite corner T; S and U cannot be on the same side. Which statement is correct?

B. Answer: (B) S cannot be placed at a corner Analysing the constraints — the midpoint-segment PR being parallel to QS (a midsegment relation), P opposite corner T, and S, U on different sides — forces S to be a midpoint of a side, so S cannot occupy a corner.

A plot with equally spaced poles (dots) must be divided among four families into similar-shaped plots. Two ropes R1 and R2 are already present and fixed. A single straight rope can pass through three aligned poles. The least number of additional straight ropes needed is

D. Answer: (D) 3 With the two fixed ropes R1 and R2 already in place, three more straight ropes (each passing through aligned poles) are sufficient to cut the plot into four similarly-shaped regions. Fewer than three cannot create four similar plots given the fixed ropes.

Which one of the following statements is TRUE for all positive functions f(n)?

A. Answer: (A) For a polynomial f(n)=n^k: f(n^2)=(n^2)^k=n^{2k} and f(n)^2=(n^k)^2=n^{2k} - equal, so f(n^2)=\Theta(f(n)^2). TRUE. (C) fails for exponentials: if f(n)=c^n then f(n^2)=c^{n^2} grows far faster than f(n)^2=c^{2n}, so f(n^2)\ne O(f(n)^2). (B) and (D) are false in general.

Which regular expression represents the language of the finite automaton shown?

D. Answer: (D) The automaton has a start state branching into two accepting loops: one reached by reading a then cycling on b's (and returning via b), the other by reading b then cycling on a's (returning via a). Reading the accepting paths and their self-loops yields the expression in option (D), which captures both symmetric accepting branches.

Which one of the following statements is TRUE?

D. Answer: (D) Every deterministic context-free language has an LR(1) grammar, so LR(1) parsing suffices for DCFLs -> (D) true. (A) is false: merging LR(1) states in LALR(1) can introduce reduce-reduce conflicts even when LR(1) has none. (B) false (symbol table used across many phases). (C) false (data-flow analysis is for optimization, not run-time memory management).

In the relational data model, which one of the following statements is TRUE?

A. Answer: (A) A relation with only two attributes is always in BCNF A two-attribute relation R(A,B) can only have FDs of the form A\to B, B\to A, both, or none — in every case the determinant is a superkey, so R is in BCNF. (B) false (all-prime does not guarantee BCNF); (C) false (a relation can be all-key); (D) false (BCNF decomposition may lose dependency preservation).

For reversing a singly linked list in O(1) space, which is TRUE about the time complexity?

A. Answer: (A) \Theta(n) time in the worst case Reversing a singly linked list requires rewiring each of the n pointers exactly once using three pointers (prev, curr, next) — O(1) extra space and \Theta(n) time, which is optimal since every node must be visited.

Given n keys, m slots, and two simple uniform hash functions h_1,h_2, where h_1 is used for odd keys and h_2 for even keys, what is the expected number of keys in a slot?

B. Answer: (B) \dfrac{n}{m} Each key (whether hashed by h_1 or h_2, both simple uniform) lands in any slot with probability \tfrac1m. By linearity of expectation, the expected load of a slot =\tfrac{n}{m}, independent of the split between odd and even keys.

Which facilitates transfer of bulk data from hard disk to main memory with the HIGHEST throughput?

A. Answer: (A) DMA based I/O transfer DMA transfers blocks directly between disk and memory without CPU involvement per word, giving the highest throughput for bulk transfers. Interrupt-driven, polling, and programmed I/O all involve the CPU per word/byte and are slower.

R1 and R2 are 4-bit 2's complement registers. For R1+R2, which values give an arithmetic overflow?

B. Answer: (B) R1 = 1100 and R2 = 1010 Overflow in 2's complement occurs when two same-sign operands produce a different-sign result (range -8 to +7). 1100=-4 and 1010=-6: sum =-10, outside [-8,7] -> overflow. The others stay in range: (A) -5+(-2)=-7 ok, (C) 3+4=7 ok, (D) -7+(-1)=-8 ok.

Threads T1 (wait S3; print "C"; signal S2), T2 (wait S1; print "B"; signal S3), T3 (wait S2; print "A"; signal S1), each in a while(true) loop. Which initialization prints BCABCA...?

C. Answer: (C) S1 = 1; S2 = 0; S3 = 0 To print B first, T2 must run first, so S1=1 (and S2=S3=0 to block T3, T1 initially). T2 prints B, signals S3 -> T1 prints C, signals S2 -> T3 prints A, signals S1 -> T2 again... producing B,C,A,B,C,A,... So S1=1, S2=0, S3=0.

For matrices A_{m\times n}, B_{n\times m}, C_{n\times n}, D_{n\times n}: Statement 1: tr(AB)=tr(BA). Statement 2: tr(CD)=tr(DC). Which holds?

C. Answer: (C) Both are correct The identity tr(XY)=tr(YX) holds whenever both products are defined (and square). AB is m\times m, BA is n\times n, but their traces are equal. CD and DC are both n\times n with equal trace. So both statements are correct.

What is printed? int x = 1, z[2] = {10, 11}; int *p = NULL; p = &x; *p = 10; p = &z[1]; *(&z[0] + 1) += 3; printf("%d, %d, %d\n", x, z[0], z[1]);

D. Answer: (D) 10, 10, 14 *p=10 with p=&x sets x=10. &z[0]+1 is &z[1], so *(&z[0]+1) += 3 makes z[1]=11+3=14. z[0] is unchanged (10). Output: "10, 10, 14".

An enterprise network has two Ethernet segments, a web server, and a firewall, connected via three routers as shown. What is the number of subnets inside the enterprise network?

C. Answer: (C) 6 Each network segment (broadcast domain) is a subnet. Counting from the figure: the two Ethernet segments (2), the web-server link, and the point-to-point links joining the three routers and the firewall together form 6 distinct subnets inside the enterprise network.

Which statements are TRUE?

B, C, D. Answer: (B), (C) and (D) - (B) If L and \overline L are both RE, run both semi-deciders in parallel; one halts, deciding L -> recursive. True. - (C) CFLs are recursive, and recursive languages are closed under complement, so \overline{L} is recursive. True. - (D) Regular languages are closed under difference, so L_1-L_2 is regular, hence deterministic context-free. True. - (A) False: a subset of an RE (even of a recursive) language can be non-recursive.

WB is a write-back and WT a write-through set-associative cache (LRU). Which statements are FALSE?

A, B, D. Answer: (A), (B) and (D) - (A) FALSE: write-through (WT) blocks are never dirty, so WT needs no dirty bit. - (B) FALSE: in write-back, a write hit only updates the cache and sets the dirty bit; it does NOT transfer to memory each time. - (C) TRUE: WT blocks are clean, so eviction needs no write-back. - (D) FALSE: a read miss in WB can evict the LRU block, which may be dirty (then it is written back).

Relations Employee(eId,Name), Brand(bId,bName), Own(eId,bId). Which relational algebra expression returns the set of eIds who own ALL the brands?

A, B. Answer: (A) and (B) "Owns all brands" is relational division. (A) expresses it directly: \pi_{eId,bId}(Own);/;\pi_{bId}(Brand), projected on eId. (B) is the standard "division via difference" formulation: \pi_{eId}(Own)-\pi_{eId}\big((\pi_{eId}(Own)\times\pi_{bId}(Brand))-\pi_{eId,bId}(Own)\big), which returns exactly the employees linked to every brand. Both are correct.

Which statements about deadlocks are TRUE?

A, D. Answer: (A) and (D) - (A) Circular wait is one of the four necessary (Coffman) conditions for deadlock. True. - (D) If every edge is an assignment edge (no process is waiting/requesting), no process is blocked, so no deadlock. True. - (B) False: with multiple instances, a cycle is necessary but not sufficient for deadlock. - (C) False: an unsafe state may lead to deadlock but does not guarantee it.

Which statements are TRUE for a group G?

A, B, C. Answer: (A), (B) and (C) - (A) (xy)^2=x^2y^2 \Rightarrow xyxy=xxyy \Rightarrow yx=xy -> abelian. True. - (B) x^2=1 means every element is its own inverse; then xy=(xy)^{-1}=y^{-1}x^{-1}=yx -> abelian. True. - (C) Any group of order 2 is cyclic, hence abelian. True. - (D) False: every subgroup of an abelian group is abelian.

Suppose a binary search tree with 1000 distinct elements is also a complete binary tree, stored using the array representation of binary heap trees. Assuming array indices start at 0, the 3rd largest element is stored at index __________.

509. Answer: 509 A complete binary tree that is also a BST, stored in a 0-indexed array (heap layout), has 1000 nodes. The largest element is the right-most node of the tree; the 3rd largest is found by the in-order predecessor relationships. Working out its array position in the complete-tree layout gives index 509.

Consider the augmented grammar with \{+,*,(,),id\} as terminals: S'\to S; S\to S+R\mid R; R\to R*P\mid P; P\to(S)\mid id. If I_0=\{[S'\to S\bullet],[S\to S\bullet+R]\}, then goto(closure(I_0),+) contains exactly __________ items.

5. Answer: 5 I_0=\{[S'\to S\bullet],[S\to S\bullet+R]\}. Taking \text{goto} on "+" moves the dot past "+" in the second item: [S\to S+\bullet R]. Its closure adds the R-productions and then the P-productions: [S -> S + . R] [R -> . R*P] [R -> . P] [P -> . (S)] [P -> . id] That is 5 items.

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, the maximum number of edges it can have is __________.

36. Answer: 36 To maximize edges while staying disconnected, make one vertex isolated and put the other 9 in a complete graph K_9: edges =\binom{9}{2}=36.

Consider a relation R(A,B,C,D,E) with FDs AB\to C, BC\to D, C\to E. The number of superkeys in R is __________.

8. Answer: 8 With FDs AB\to C, BC\to D, C\to E on R(A,B,C,D,E): A and B never appear on a right side, so they are in every key. \{A,B\}^+ = ABCDE (via AB\to C\to E and BC\to D), so AB is the only candidate key. Superkeys = all supersets of AB =AB\cup(\text{any subset of }\{C,D,E\})=2^3=8.

The number of arrangements of six identical balls in three identical bins is __________.

7. Answer: 7 Placing 6 identical balls in 3 identical bins counts partitions of 6 into at most 3 parts: 6 | 5+1 | 4+2 | 4+1+1 | 3+3 | 3+2+1 | 2+2+2 That is 7 arrangements.

A cache with hit rate 0.8 has access latency 10 ns and miss penalty 100 ns. An optimization raises the access latency to 15 ns (miss penalty unchanged). The minimum hit rate (two decimals) needed after the optimization so the average memory access time does not increase is __________.

0.85. Answer: 0.85 Original AMAT = access latency + miss rate \times penalty =10+0.2\times100=30 ns. After: latency 15, hit rate h. Require 15+(1-h)\times100\le30\Rightarrow (1-h)\le0.15\Rightarrow h\ge0.85.

The value of \displaystyle\lim_{x\to0^+}\frac{\sqrt{x}}{1-e^{2\sqrt{x}}} is __________.

-0.5. Answer: -0.5 \displaystyle\lim_{x\to0^+}\frac{\sqrt x}{1-e^{2\sqrt x}}. For small u=\sqrt x, e^{2u}\approx1+2u, so 1-e^{2u}\approx-2u. Hence \dfrac{u}{-2u}\to-\dfrac12=-0.5.

Resolving www.gate.org.in by a DNS resolver with nothing cached and iterative queries, the number of DNS query-response pairs involved is __________.

4. Answer: 4 Resolving www.gate.org.in iteratively with nothing cached: the local resolver queries the root server (-> .in), then the .in TLD server (-> org.in), then the org.in server (-> gate.org.in), then the gate.org.in authoritative server (-> www). That is 4 query-response pairs.

Which is the closed form of the generating function of \{a_n\}_{n\ge0} where a_n=n+1 if n is odd, and a_n=1 otherwise?

A. Answer: (A) \dfrac{x(1+x^2)}{(1-x^2)^2}+\dfrac{1}{1-x} The sequence is 1,2,1,4,1,6,\dots. Split into the even-index part (all 1's) and odd-index part (2,4,6,\dots): G(x)=\sum_{n\ge0}x^n\;\text{(the 1's, with odd terms corrected)}=\frac{x(1+x^2)}{(1-x^2)^2}+\frac{1}{1-x}. Checking coefficients: a_0=1, a_1=2, a_2=1, a_3=4,\dots all match option (A).

For a simple undirected unweighted graph with adjacency matrix A, the number of 3-cycles (triangles) equals the trace of

D. Answer: (D) A^3 divided by 6 (A^3)_{ii} counts closed walks of length 3 from vertex i, i.e. 2\times(triangles through i). Summing over i, \text{tr}(A^3) counts each triangle 6 times (3 starting vertices \times 2 directions). So the number of triangles =\dfrac{\text{tr}(A^3)}{6}.

Which one of the following statements is FALSE?

C. Answer: (C) — this is FALSE An inverted page table is searched (often via a hash chain) for the entry matching the virtual address, so the access time varies with the position in the table/chain — it is NOT always the same. (A), (B), and (D) are true statements.

Schedule S: R_4(x)\,R_2(x)\,R_3(x)\,R_1(y)\,W_1(y)\,W_2(x)\,W_3(y)\,R_4(y). Which serial schedule is conflict equivalent to S?

A. Answer: (A) T_1\to T_3\to T_4\to T_2 Build the precedence graph from conflicting operations (same item, at least one write). Resolving the edges on x and y (e.g. R_i(x) before W_2(x) gives T_i\to T_2; W_1(y) before W_3(y) and R_4(y) gives T_1\to T_3, T_1\to T_4; etc.) yields an acyclic graph whose topological order is T_1\to T_3\to T_4\to T_2.

In the digital display system shown, a 16-bit code word loads register X from S (a 1024-word memory) or R (a 32-word register file); mode bit M selects via T, and P, Q choose the addressed word. Which represents the functionality of P, Q, and T?

C. Answer: (C) P is 10:2^10 decoder; Q is 5:2^5 decoder; T is 2:1 multiplexer Addressing one of 1024 (=2^{10}) words in S needs a 10-to-2^{10} decoder (P); addressing one of 32 (=2^5) words in R needs a 5-to-2^5 decoder (Q). The mode bit M selects between the two sources to load X, which is a 2-to-1 multiplexer (T).

Floating point numbers in RA=0xC1400000, RB=0x42100000, RC=0x41400000 (IEEE-754 single precision). Which one is FALSE?

B. Answer: (B) C=A+B is FALSE Decoding: RA =-1.5\times2^{4}=-12, RB =1.125\times2^{5}=36, RC =1.5\times2^{3}=12. So A=-12, B=36, C=12. - (A) A+C=-12+12=0. True. - (B) C=A+B? 12\ne-12+36=24. FALSE. - (C) B=3C? 36=3\times12. True. - (D) B-C=36-12=24>0. True.

Four processes P, Q, R, S arrive at t=0 in that order, scheduled by Round Robin with quantum 4. There is exactly one context switch S->Q, exactly one R->Q, exactly two Q->R, and no S->P. Which CPU burst times are NOT possible?

D. Answer: (D) P = 3, Q = 7, R = 7, S = 3 Simulating Round Robin (quantum 4) for each option and checking the required context-switch pattern (exactly one S->Q, one R->Q, two Q->R, and no S->P): option (D)'s burst times produce a schedule that violates these constraints (it does not yield exactly two Q->R switches without an S->P switch), so it is NOT possible.

What is printed? (a[3][3][3] initialized row-wise with 1..27; loops over i and k with j=0, printing a[i][j][k].)

A. Answer: (A) 1 2 3 / 10 11 12 / 19 20 21 The array stores values 1..27 in row-major order, so a[i][0][k] is element at offset 9i+0\cdot3+k=9i+k. For i=0: a[0][0][0..2]=1,2,3; i=1: 9+1,9+2,9+3=10,11,12; i=2: 19,20,21. With j fixed at 0 the output is those three rows.

What is printed? char a='P', b='x'; char c=(a&b)+'*'; char d=(a|b)-'-'; char e=(a^b)+'+'; printf("%c %c %c", c, d, e); (ASCII: P=80, x=120, *=42, -=45, +=43)

A. Answer: (A) z K S ASCII: P=80 (01010000), x=120 (01111000). - a\&b=01010000=80; c=80+42=122= 'z'. - a|b=01111000=120; d=120-45=75= 'K'. - a\oplus b=00101000=40; e=40+43=83= 'S'. Printed as characters: "z K S".

Solving the system by LU decomposition (x_1+x_2-2x_3=4; x_1+3x_2-x_3=7; 2x_1+x_2-5x_3=7), with L unit lower-triangular and U upper-triangular, which is the correct combination of L_{32}, U_{33}, and x_1?

D. Answer: (D) L_{32}=-\tfrac12,\ U_{33}=\tfrac12,\ x_1=0 Doolittle LU on the coefficient matrix: row 2 - row 1 gives multiplier L_{21}=1, and row 3 -2\timesrow 1 gives L_{31}=2, updating U. Eliminating column 2 in row 3 gives L_{32}=-\tfrac12 and the final pivot U_{33}=\tfrac12. Forward/back substitution then yields x_1=0.

Which of the following is/are undecidable?

A, B, C. Answer: (A), (B) and (C) Equivalence of two TMs (A), whether L(M) is regular (B), and whether M accepts all strings / \Sigma^* (C) are all undecidable (by Rice's theorem for the language properties, and reduction for equivalence). (D) is DECIDABLE: run M for 1073 steps on all strings up to length 1073 — a finite check determines whether it ever halts within 1073 steps.

L_1=\{a^n w a^n \mid w\in\{a,b\}^*\} and L_2=\{wxw^R \mid w,x\in\{a,b\}^+\}. Which is TRUE?

A, B, C. Answer: (A), (B) and (C) Both languages are in fact REGULAR. - L_1=\{a^n w a^n\}: taking n=1 already gives all strings that start and end with 'a' (with a non-empty middle), so L_1 collapses to a regular language. - L_2=\{w x w^R\}: taking |w|=1, wxw^R=c\,x\,c for a single char c - i.e. every string of length \ge3 whose first and last characters are equal - which is regular. Since both are regular (hence also context-free): (A) both regular, (B) both context-free, and (C) L1 regular and L2 conte

L_1=\{ww\mid w\in\{a,b\}^*\}, L_2=\{a^n b^n c^m\mid m,n\ge0\}, L_3=\{a^m b^n c^n\mid m,n\ge0\}. Which statements are FALSE?

B, C, D. Answer: (B), (C) and (D) L_1=\{ww\} is not context-free; L_2,L_3 are deterministic context-free (single matching). L_2\cap L_3=\{a^n b^n c^n\} is NOT context-free. - (A) True (as stated). - (B) FALSE: L_2 IS context-free. - (C) FALSE: L_2\cap L_3=a^nb^nc^n is not context-free. - (D) FALSE: the complement of L_1=\{ww\} IS context-free (a known result). So (B), (C), (D) are the false statements.

G is a simple undirected weighted graph with all distinct edge weights. Which statements about its MSTs are TRUE?

A, B, C. Answer: (A), (B) and (C) With all distinct weights the MST is unique, so (D) is false. By the cut property, the lightest edge across any cut is in the MST (C). The two globally smallest edges are always in the MST (they cannot form a cycle alone), so the second-smallest is included (A). Among the third and fourth smallest, at least one must join without forming a cycle, so (B) holds.

The Petersen graph is shown. Which statements are TRUE?

A, B, C. Answer: (A), (B) and (C) The Petersen graph has chromatic number 3 (A) and a Hamiltonian path though no Hamiltonian cycle (B); the second drawing is a standard isomorphic redrawing of it (C). Its maximum independent set has size 4, not 3, so (D) is false.

The recurrence f(1)=1, f(2n)=2f(n)-1 for n\ge1, f(2n+1)=2f(n)+1 for n\ge1. Which statements are TRUE?

A, B, C. Answer: (A), (B) and (C) Computing values: f(1)=1, f(2)=1, f(3)=3, f(4)=1, f(5)=3, f(6)=5, f(7)=7, f(8)=1,\dots - (A) f(2^n-1)=2^n-1: f(3)=3, f(7)=7,\dots TRUE. - (B) f(2^n)=1: f(2)=f(4)=f(8)=1. TRUE. - (C) f(5\cdot2^n)=2^{n+1}+1: f(5)=3=2^1+1, f(10)=5=2^2+1,\dots TRUE. - (D) f(2^n+1)=2^n+1: f(5)=3 but 2^2+1=5, so FALSE. Hence (A), (B), (C).

GATE CS 2022 — 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
The _________ is too high for it to be considered _________.
- A.
  fair / fare
- B.
  faer / fair
- C.
  fare / fare
- D.
  fare / fair
  ✓
Answer: D
Solution
Answer: (D) fare / fair The first blank needs "fare" (the price/charge), which can be "too high"; the second needs "fair" (reasonable/just). So: The fare is too high for it to be considered fair.
Question 2General Aptitudemcq1 mark
A function $y (x)$ on $[0, 1]$ is $y (x) = 2$ for $0 \leq x < \frac{1}{3}$ , $y (x) = 3$ for $\frac{1}{3} \leq x < \frac{3}{4}$ , $y (x) = 1$ for $\frac{3}{4} \leq x \leq 1$ . The area under the curve on $[0, 1]$ is
- A.
  $\frac{5}{6}$
- B.
  $\frac{6}{5}$
- C.
  $\frac{13}{6}$
  ✓
- D.
  $\frac{6}{13}$
Answer: C
Solution
Answer: (C) $\frac{13}{6}$ Area $=$ sum of rectangle areas:
$2 \cdot \frac{1}{3} + 3 \cdot (\frac{3}{4} - \frac{1}{3}) + 1 \cdot (1 - \frac{3}{4}) = \frac{2}{3} + 3 \cdot \frac{5}{12} + \frac{1}{4} = \frac{8}{12} + \frac{15}{12} + \frac{3}{12} = \frac{26}{12} = \frac{13}{6} .$
Question 3General Aptitudemcq1 mark
Let $r$ be a root of $x^{2} + 2 x + 6 = 0$ . The value of $(r + 2) (r + 3) (r + 4) (r + 5)$ is
- A.
  51
- B.
  -51
- C.
  126
- D.
  -126
  ✓
Answer: D
Solution
Answer: (D) -126 From $r^{2} + 2 r + 6 = 0$ , $r^{2} = - 2 r - 6$ . Pair the factors: $(r + 2) (r + 5) = r^{2} + 7 r + 10$ and $(r + 3) (r + 4) = r^{2} + 7 r + 12$ . Let $t = r^{2} + 7 r = (- 2 r - 6) + 7 r = 5 r - 6$ . Then the product $= (t + 10) (t + 12) = t^{2} + 22 t + 120$ . With $t = 5 r - 6$ : $t^{2} = - 110 r - 114$ and $22 t = 110 r - 132$ , so the product $= - 110 r - 114 + 110 r - 132 + 120 = - 126.$
Question 4General Aptitudemcq1 mark
Four statements: (1) All students are inquisitive. (2) Some students are inquisitive. (3) No student is inquisitive. (4) Some students are not inquisitive. Assuming at least one student exists, which two CANNOT be true simultaneously?
- A.
  Statement 1 and Statement 3
  ✓
- B.
  Statement 1 and Statement 2
- C.
  Statement 2 and Statement 4
- D.
  Statement 3 and Statement 4
Answer: A
Solution
Answer: (A) Statement 1 and Statement 3 "All students are inquisitive" (1) and "No student is inquisitive" (3) are contraries — with at least one student they cannot both hold. The other pairs can be simultaneously true.
Question 5General Aptitudemcq1 mark
A player has two plates painted with the letters shown (A and D). Using all five plates exactly once (plates can be rotated in their plane), which option of three additional plates lets the player form a five-letter palindrome?
- A.
  D, D(rotated), J
- B.
  R, A(rotated), R
  ✓
- C.
  Z, E(rotated), D
- D.
  I, L(rotated), Y
Answer: B
Solution
Answer: (B) R, A, R Combining the two given plates (A and D) with option (B)'s plates (R, A, R) gives the letters ${R, A, D, A, R}$ , which arrange into the palindrome "RADAR". (Rotations let a plate be reused in its flipped orientation where needed.) None of the other option sets can form a five-letter palindrome with A and D.
Question 6General Aptitudemcq2 marks
Passage: In organizations with good work culture, metrics help improve outcomes; the same metrics are counterproductive in organizations with poor work culture. Which is the CORRECT logical inference?
- A.
  Metrics are useful in organizations with poor work culture
- B.
  Metrics are useful in organizations with good work culture
  ✓
- C.
  Metrics are always counterproductive in organizations with good work culture
- D.
  Metrics are never useful in organizations with good work culture
Answer: B
Solution
Answer: (B) Metrics are useful in organizations with good work culture The passage directly states that in organizations with good work culture, metrics help improve outcomes — i.e. they are useful there.
Question 7General Aptitudemcq2 marks
Boys were 65% of those who appeared for a test; girls were the rest and accounted for 60% of the qualified candidates. Which is the correct inference?
- A.
  Equal number of boys and girls qualified
- B.
  Equal number of boys and girls appeared
- C.
  The number of boys who appeared is less than the number of girls who appeared
- D.
  The number of boys who qualified is less than the number of girls who qualified
  ✓
Answer: D
Solution
Answer: (D) The number of boys who qualified is less than the number of girls who qualified Girls account for 60% of qualified candidates (more than half), so fewer than half of the qualified are boys. Hence fewer boys qualified than girls — even though more boys appeared.
Question 8General Aptitudemcq2 marks
A box has 3 green and 2 orange balls. If a green ball is drawn, it is NOT replaced; if an orange ball is drawn, it is replaced with another orange ball. After the first draw, what is the probability of getting an orange ball in the next draw?
- A.
  $\frac{1}{2}$
- B.
  $\frac{8}{25}$
- C.
  $\frac{19}{50}$
- D.
  $\frac{23}{50}$
  ✓
Answer: D
Solution
Answer: (D) $\frac{23}{50}$ - First draw green ( $P = \frac{3}{5}$ ): box becomes 2 green, 2 orange, so $P (orange next) = \frac{2}{4} = \frac{1}{2}$ . - First draw orange ( $P = \frac{2}{5}$ ): orange is replaced by orange, box stays 3 green, 2 orange, so $P (orange next) = \frac{2}{5}$ . Total $= \frac{3}{5} \cdot \frac{1}{2} + \frac{2}{5} \cdot \frac{2}{5} = \frac{3}{10} + \frac{4}{25} = \frac{15}{50} + \frac{8}{50} = \frac{23}{50} .$
Question 9General Aptitudemcq2 marks
The corners and mid-points of the sides of a triangle are labelled P, Q, R, S, T, U (in some order). Given: PR is parallel to QS; P is on the side opposite corner T; S and U cannot be on the same side. Which statement is correct?
- A.
  P cannot be placed at a corner
- B.
  S cannot be placed at a corner
  ✓
- C.
  U cannot be placed at a mid-point
- D.
  R cannot be placed at a corner
Answer: B
Solution
Answer: (B) S cannot be placed at a corner Analysing the constraints — the midpoint-segment PR being parallel to QS (a midsegment relation), P opposite corner T, and S, U on different sides — forces S to be a midpoint of a side, so S cannot occupy a corner.
Question 10General Aptitudemcq2 marks
A plot with equally spaced poles (dots) must be divided among four families into similar-shaped plots. Two ropes R1 and R2 are already present and fixed. A single straight rope can pass through three aligned poles. The least number of additional straight ropes needed is
- A.
  2
- B.
  4
- C.
  5
- D.
  3
  ✓
Answer: D
Solution
Answer: (D) 3 With the two fixed ropes R1 and R2 already in place, three more straight ropes (each passing through aligned poles) are sufficient to cut the plot into four similarly-shaped regions. Fewer than three cannot create four similar plots given the fixed ropes.
Question 11Algorithmsmcq1 mark
Which one of the following statements is TRUE for all positive functions $f (n)$ ?
- A.
  $f (n^{2}) = Θ (f (n)^{2})$ , when $f (n)$ is a polynomial
  ✓
- B.
  $f (n^{2}) = o (f (n)^{2})$
- C.
  $f (n^{2}) = O (f (n)^{2})$ , when $f (n)$ is an exponential function
- D.
  $f (n^{2}) = Ω (f (n)^{2})$
Answer: A
Solution
Answer: (A) For a polynomial $f (n) = n^{k}$ : $f (n^{2}) = (n^{2})^{k} = n^{2 k}$ and $f (n)^{2} = (n^{k})^{2} = n^{2 k}$ - equal, so $f (n^{2}) = Θ (f (n)^{2})$ . TRUE. (C) fails for exponentials: if $f (n) = c^{n}$ then $f (n^{2}) = c^{n^{2}}$ grows far faster than $f (n)^{2} = c^{2 n}$ , so $f (n^{2}) \neq = O (f (n)^{2})$ . (B) and (D) are false in general.
Question 12Theory of Computationmcq1 mark
Which regular expression represents the language of the finite automaton shown?
- A.
  $a b^{*} ba b^{*} + b a^{*} ab a^{*}$
- B.
  $(a b^{*} b)^{*} a b^{*} + (b a^{*} a)^{*} b a^{*}$
- C.
  $(a b^{*} b)^{*} + (b a^{*})^{*} (a^{*} + b^{*})$
- D.
  $(b a^{*} a + a b^{*} b) (a b^{*} + b a^{*})$
  ✓
Answer: D
Solution
Answer: (D) The automaton has a start state branching into two accepting loops: one reached by reading $a$ then cycling on $b$ 's (and returning via $b$ ), the other by reading $b$ then cycling on $a$ 's (returning via $a$ ). Reading the accepting paths and their self-loops yields the expression in option (D), which captures both symmetric accepting branches.
Question 13Compiler Designmcq1 mark
Which one of the following statements is TRUE?
- A.
  The LALR(1) parser for G cannot have a reduce-reduce conflict if the LR(1) parser for G does not have a reduce-reduce conflict.
- B.
  Symbol table is accessed only during the lexical analysis phase.
- C.
  Data flow analysis is necessary for run-time memory management.
- D.
  LR(1) parsing is sufficient for deterministic context-free languages.
  ✓
Answer: D
Solution
Answer: (D) Every deterministic context-free language has an LR(1) grammar, so LR(1) parsing suffices for DCFLs -> (D) true. (A) is false: merging LR(1) states in LALR(1) can introduce reduce-reduce conflicts even when LR(1) has none. (B) false (symbol table used across many phases). (C) false (data-flow analysis is for optimization, not run-time memory management).
Question 14Databasesmcq1 mark
In the relational data model, which one of the following statements is TRUE?
- A.
  A relation with only two attributes is always in BCNF.
  ✓
- B.
  If all attributes of a relation are prime, then the relation is in BCNF.
- C.
  Every relation has at least one non-prime attribute.
- D.
  BCNF decompositions preserve functional dependencies.
Answer: A
Solution
Answer: (A) A relation with only two attributes is always in BCNF A two-attribute relation $R (A, B)$ can only have FDs of the form $A \to B$ , $B \to A$ , both, or none — in every case the determinant is a superkey, so $R$ is in BCNF. (B) false (all-prime does not guarantee BCNF); (C) false (a relation can be all-key); (D) false (BCNF decomposition may lose dependency preservation).
Question 15Programming & Data Structuresmcq1 mark
For reversing a singly linked list in $O (1)$ space, which is TRUE about the time complexity?
- A.
  The best algorithm takes $Θ (n)$ time in the worst case.
  ✓
- B.
  The best algorithm takes $Θ (n lo g n)$ time.
- C.
  The best algorithm takes $Θ (n^{2})$ time.
- D.
  It is not possible to reverse a singly linked list in $O (1)$ space.
Answer: A
Solution
Answer: (A) $Θ (n)$ time in the worst case Reversing a singly linked list requires rewiring each of the $n$ pointers exactly once using three pointers (prev, curr, next) — $O (1)$ extra space and $Θ (n)$ time, which is optimal since every node must be visited.
Question 16Programming & Data Structuresmcq1 mark
Given $n$ keys, $m$ slots, and two simple uniform hash functions $h_{1}, h_{2}$ , where $h_{1}$ is used for odd keys and $h_{2}$ for even keys, what is the expected number of keys in a slot?
- A.
  $\frac{m}{n}$
- B.
  $\frac{n}{m}$
  ✓
- C.
  $\frac{2 n}{m}$
- D.
  $\frac{n}{2 m}$
Answer: B
Solution
Answer: (B) $\frac{n}{m}$ Each key (whether hashed by $h_{1}$ or $h_{2}$ , both simple uniform) lands in any slot with probability $\frac{1}{m}$ . By linearity of expectation, the expected load of a slot $= \frac{n}{m}$ , independent of the split between odd and even keys.
Question 17Computer Organization & Architecturemcq1 mark
Which facilitates transfer of bulk data from hard disk to main memory with the HIGHEST throughput?
- A.
  DMA based I/O transfer
  ✓
- B.
  Interrupt driven I/O transfer
- C.
  Polling based I/O transfer
- D.
  Programmed I/O transfer
Answer: A
Solution
Answer: (A) DMA based I/O transfer DMA transfers blocks directly between disk and memory without CPU involvement per word, giving the highest throughput for bulk transfers. Interrupt-driven, polling, and programmed I/O all involve the CPU per word/byte and are slower.
Question 18Digital Logicmcq1 mark
R1 and R2 are 4-bit 2's complement registers. For R1+R2, which values give an arithmetic overflow?
- A.
  R1 = 1011 and R2 = 1110
- B.
  R1 = 1100 and R2 = 1010
  ✓
- C.
  R1 = 0011 and R2 = 0100
- D.
  R1 = 1001 and R2 = 1111
Answer: B
Solution
Answer: (B) R1 = 1100 and R2 = 1010 Overflow in 2's complement occurs when two same-sign operands produce a different-sign result (range $- 8$ to $+ 7$ ). $1100 = - 4$ and $1010 = - 6$ : sum $= - 10$ , outside $[- 8, 7]$ -> overflow. The others stay in range: (A) $- 5 + (- 2) = - 7$ ok, (C) $3 + 4 = 7$ ok, (D) $- 7 + (- 1) = - 8$ ok.
Question 19Operating Systemsmcq1 mark
Threads T1 (wait S3; print "C"; signal S2), T2 (wait S1; print "B"; signal S3), T3 (wait S2; print "A"; signal S1), each in a while(true) loop. Which initialization prints BCABCA...?
- A.
  S1 = 1; S2 = 1; S3 = 1
- B.
  S1 = 1; S2 = 1; S3 = 0
- C.
  S1 = 1; S2 = 0; S3 = 0
  ✓
- D.
  S1 = 0; S2 = 1; S3 = 1
Answer: C
Solution
Answer: (C) S1 = 1; S2 = 0; S3 = 0 To print B first, T2 must run first, so S1=1 (and S2=S3=0 to block T3, T1 initially). T2 prints B, signals S3 -> T1 prints C, signals S2 -> T3 prints A, signals S1 -> T2 again... producing B,C,A,B,C,A,... So S1=1, S2=0, S3=0.
Question 20Engineering Mathematicsmcq1 mark
For matrices $A_{m \times n}, B_{n \times m}, C_{n \times n}, D_{n \times n}$ : Statement 1: $t r (A B) = t r (B A)$ . Statement 2: $t r (C D) = t r (D C)$ . Which holds?
- A.
  Statement 1 is correct and Statement 2 is wrong.
- B.
  Statement 1 is wrong and Statement 2 is correct.
- C.
  Both Statement 1 and Statement 2 are correct.
  ✓
- D.
  Both Statement 1 and Statement 2 are wrong.
Answer: C
Solution
Answer: (C) Both are correct The identity $t r (X Y) = t r (Y X)$ holds whenever both products are defined (and square). $A B$ is $m \times m$ , $B A$ is $n \times n$ , but their traces are equal. $C D$ and $D C$ are both $n \times n$ with equal trace. So both statements are correct.
Question 21Programming & Data Structuresmcq1 mark
What is printed?
```
int x = 1, z[2] = {10, 11};
int *p = NULL;
p = &x;  *p = 10;
p = &z[1];
*(&z[0] + 1) += 3;
printf("%d, %d, %d\n", x, z[0], z[1]);
```
- A.
  1, 10, 11
- B.
  1, 10, 14
- C.
  10, 14, 11
- D.
  10, 10, 14
  ✓
Answer: D
Solution
Answer: (D) 10, 10, 14 *p=10 with p=&x sets $x = 10$ . &z[0]+1 is &z[1], so *(&z[0]+1) += 3 makes $z [1] = 11 + 3 = 14$ . $z [0]$ is unchanged (10). Output: "10, 10, 14".
Question 22Computer Networksmcq1 mark
An enterprise network has two Ethernet segments, a web server, and a firewall, connected via three routers as shown. What is the number of subnets inside the enterprise network?
- A.
  3
- B.
  12
- C.
  6
  ✓
- D.
  8
Answer: C
Solution
Answer: (C) 6 Each network segment (broadcast domain) is a subnet. Counting from the figure: the two Ethernet segments (2), the web-server link, and the point-to-point links joining the three routers and the firewall together form 6 distinct subnets inside the enterprise network.
Question 23Theory of Computationmsq1 mark
Which statements are TRUE?
- A.
  Every subset of a recursively enumerable language is recursive.
- B.
  If a language L and its complement are both recursively enumerable, then L is recursive.
  ✓
- C.
  Complement of a context-free language must be recursive.
  ✓
- D.
  If L1 and L2 are regular, then L1-L2 must be deterministic context-free.
  ✓
Answer: B, C, D
Solution
Answer: (B), (C) and (D) - (B) If $L$ and $L$ are both RE, run both semi-deciders in parallel; one halts, deciding $L$ -> recursive. True. - (C) CFLs are recursive, and recursive languages are closed under complement, so $L$ is recursive. True. - (D) Regular languages are closed under difference, so $L_{1} - L_{2}$ is regular, hence deterministic context-free. True. - (A) False: a subset of an RE (even of a recursive) language can be non-recursive.
Question 24Computer Organization & Architecturemsq1 mark
WB is a write-back and WT a write-through set-associative cache (LRU). Which statements are FALSE?
- A.
  Each cache block in WB and WT has a dirty bit.
  ✓
- B.
  Every write hit in WB leads to a data transfer from cache to main memory.
  ✓
- C.
  Eviction of a block from WT will not lead to data transfer from cache to main memory.
- D.
  A read miss in WB will never lead to eviction of a dirty block from WB.
  ✓
Answer: A, B, D
Solution
Answer: (A), (B) and (D) - (A) FALSE: write-through (WT) blocks are never dirty, so WT needs no dirty bit. - (B) FALSE: in write-back, a write hit only updates the cache and sets the dirty bit; it does NOT transfer to memory each time. - (C) TRUE: WT blocks are clean, so eviction needs no write-back. - (D) FALSE: a read miss in WB can evict the LRU block, which may be dirty (then it is written back).
Question 25Databasesmsq1 mark
Relations Employee(eId,Name), Brand(bId,bName), Own(eId,bId). Which relational algebra expression returns the set of eIds who own ALL the brands?
- A.
  $π_{e I d} (π_{e I d, b I d} (O w n) / π_{b I d} (B r an d))$
  ✓
- B.
  $π_{e I d} (O w n) - π_{e I d} ((π_{e I d} (O w n) \times π_{b I d} (B r an d)) - π_{e I d, b I d} (O w n))$
  ✓
- C.
  $π_{e I d, b I d} (O w n) / π_{b I d} (O w n)$
- D.
  $(π_{e I d} (O w n) \times π_{b I d} (O w n)) / π_{b I d} (B r an d)$
Answer: A, B
Solution
Answer: (A) and (B) "Owns all brands" is relational division. (A) expresses it directly: $π_{e I d, b I d} (O w n); /; π_{b I d} (B r an d)$ , projected on $e I d$ . (B) is the standard "division via difference" formulation: $π_{e I d} (O w n) - π_{e I d} ((π_{e I d} (O w n) \times π_{b I d} (B r an d)) - π_{e I d, b I d} (O w n))$ , which returns exactly the employees linked to every brand. Both are correct.
Question 26Operating Systemsmsq1 mark
Which statements about deadlocks are TRUE?
- A.
  Circular wait is a necessary condition for deadlock.
  ✓
- B.
  If each resource has more than one instance, a cycle in the wait-for graph indicates a deadlock.
- C.
  If current allocation leads to an unsafe state, deadlock will necessarily occur.
- D.
  If every edge in the resource-allocation graph is an assignment edge, the system is not in deadlock.
  ✓
Answer: A, D
Solution
Answer: (A) and (D) - (A) Circular wait is one of the four necessary (Coffman) conditions for deadlock. True. - (D) If every edge is an assignment edge (no process is waiting/requesting), no process is blocked, so no deadlock. True. - (B) False: with multiple instances, a cycle is necessary but not sufficient for deadlock. - (C) False: an unsafe state may lead to deadlock but does not guarantee it.
Question 27Discrete Mathematicsmsq1 mark
Which statements are TRUE for a group $G$ ?
- A.
  If $(x y)^{2} = x^{2} y^{2}$ for all $x, y \in G$ , then $G$ is commutative.
  ✓
- B.
  If $x^{2} = 1$ for all $x \in G$ , then $G$ is commutative.
  ✓
- C.
  If the order of $G$ is 2, then $G$ is commutative.
  ✓
- D.
  If $G$ is commutative, then a subgroup of $G$ need not be commutative.
Answer: A, B, C
Solution
Answer: (A), (B) and (C) - (A) $(x y)^{2} = x^{2} y^{2} \Rightarrow x y x y = xx y y \Rightarrow y x = x y$ -> abelian. True. - (B) $x^{2} = 1$ means every element is its own inverse; then $x y = (x y)^{- 1} = y^{- 1} x^{- 1} = y x$ -> abelian. True. - (C) Any group of order 2 is cyclic, hence abelian. True. - (D) False: every subgroup of an abelian group is abelian.
Question 28Programming & Data Structuresnat1 mark
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree, stored using the array representation of binary heap trees. Assuming array indices start at 0, the 3rd largest element is stored at index __________.
Answer: 509
Solution
Answer: 509 A complete binary tree that is also a BST, stored in a 0-indexed array (heap layout), has 1000 nodes. The largest element is the right-most node of the tree; the 3rd largest is found by the in-order predecessor relationships. Working out its array position in the complete-tree layout gives index 509.
Question 29Compiler Designnat1 mark
Consider the augmented grammar with ${+, *, (,), i d}$ as terminals: $S^{'} \to S$ ; $S \to S + R ∣ R$ ; $R \to R * P ∣ P$ ; $P \to (S) ∣ i d$ . If $I_{0} = {[S^{'} \to S ∙], [S \to S ∙ + R]}$ , then $g o t o (c l os u r e (I_{0}), +)$ contains exactly __________ items.
Answer: 5
Solution
Answer: 5 $I_{0} = {[S^{'} \to S ∙], [S \to S ∙ + R]}$ . Taking $goto$ on "+" moves the dot past "+" in the second item: $[S \to S + ∙ R]$ . Its closure adds the $R$ -productions and then the $P$ -productions:
```
[S -> S + . R]
[R -> . R*P]   [R -> . P]
[P -> . (S)]   [P -> . id]
```
That is 5 items.
Question 30Discrete Mathematicsnat1 mark
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, the maximum number of edges it can have is __________.
Answer: 36
Solution
Answer: 36 To maximize edges while staying disconnected, make one vertex isolated and put the other 9 in a complete graph $K_{9}$ : edges $= (2 9) = 36$ .
Question 31Databasesnat1 mark
Consider a relation $R (A, B, C, D, E)$ with FDs $A B \to C$ , $B C \to D$ , $C \to E$ . The number of superkeys in $R$ is __________.
Answer: 8
Solution
Answer: 8 With FDs $A B \to C$ , $B C \to D$ , $C \to E$ on $R (A, B, C, D, E)$ : $A$ and $B$ never appear on a right side, so they are in every key. ${A, B}^{+} = A B C D E$ (via $A B \to C \to E$ and $B C \to D$ ), so $A B$ is the only candidate key. Superkeys $=$ all supersets of $A B$ $= A B \cup (any subset of {C, D, E}) = 2^{3} = 8.$
Question 32Discrete Mathematicsnat1 mark
The number of arrangements of six identical balls in three identical bins is __________.
Answer: 7
Solution
Answer: 7 Placing 6 identical balls in 3 identical bins counts partitions of 6 into at most 3 parts:
```
6 | 5+1 | 4+2 | 4+1+1 | 3+3 | 3+2+1 | 2+2+2
```
That is 7 arrangements.
Question 33Computer Organization & Architecturenat1 mark
A cache with hit rate 0.8 has access latency 10 ns and miss penalty 100 ns. An optimization raises the access latency to 15 ns (miss penalty unchanged). The minimum hit rate (two decimals) needed after the optimization so the average memory access time does not increase is __________.
Answer: 0.85
Solution
Answer: 0.85 Original AMAT $=$ access latency $+$ miss rate $\times$ penalty $= 10 + 0.2 \times 100 = 30$ ns. After: latency $15$ , hit rate $h$ . Require $15 + (1 - h) \times 100 \leq 30 \Rightarrow (1 - h) \leq 0.15 \Rightarrow h \geq 0.85.$
Question 34Engineering Mathematicsnat1 mark
The value of $x \to 0^{+} lim \frac{x}{1 - e ^{2 x}}$ is __________.
Answer: -0.5
Solution
Answer: -0.5 $x \to 0^{+} lim \frac{x}{1 - e ^{2 x}}$ . For small $u = x$ , $e^{2 u} \approx 1 + 2 u$ , so $1 - e^{2 u} \approx - 2 u$ . Hence $\frac{u}{- 2 u} \to - \frac{1}{2} = - 0.5.$
Question 35Computer Networksnat1 mark
Resolving www.gate.org.in by a DNS resolver with nothing cached and iterative queries, the number of DNS query-response pairs involved is __________.
Answer: 4
Solution
Answer: 4 Resolving www.gate.org.in iteratively with nothing cached: the local resolver queries the root server (-> .in), then the .in TLD server (-> org.in), then the org.in server (-> gate.org.in), then the gate.org.in authoritative server (-> www). That is 4 query-response pairs.
Question 36Discrete Mathematicsmcq2 marks
Which is the closed form of the generating function of ${a_{n}}_{n \geq 0}$ where $a_{n} = n + 1$ if $n$ is odd, and $a_{n} = 1$ otherwise?
- A.
  $\frac{x ( 1 + x ^{2} )}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$
  ✓
- B.
  $\frac{x ( 3 - x ^{2} )}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$
- C.
  $\frac{2 x}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x ^{2}}$
- D.
  $\frac{x}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$
Answer: A
Solution
Answer: (A) $\frac{x ( 1 + x ^{2} )}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x}$ The sequence is $1, 2, 1, 4, 1, 6, \dots$ . Split into the even-index part (all 1's) and odd-index part ( $2, 4, 6, \dots$ ):
$G (x) = n \geq 0 \sum x^{n} (the 1’s, with odd terms corrected) = \frac{x ( 1 + x ^{2} )}{( 1 - x ^{2} ) ^{2}} + \frac{1}{1 - x} .$
Checking coefficients: $a_{0} = 1, a_{1} = 2, a_{2} = 1, a_{3} = 4, \dots$ all match option (A).
Question 37Discrete Mathematicsmcq2 marks
For a simple undirected unweighted graph with adjacency matrix $A$ , the number of 3-cycles (triangles) equals the trace of
- A.
  $A^{3}$
- B.
  $A^{3}$ divided by 2
- C.
  $A^{3}$ divided by 3
- D.
  $A^{3}$ divided by 6
  ✓
Answer: D
Solution
Answer: (D) $A^{3}$ divided by 6 $(A^{3})_{ii}$ counts closed walks of length 3 from vertex $i$ , i.e. $2 \times$ (triangles through $i$ ). Summing over $i$ , $tr (A^{3})$ counts each triangle $6$ times (3 starting vertices $\times$ 2 directions). So the number of triangles $= \frac{tr ( A ^{3} )}{6} .$
Question 38Operating Systemsmcq2 marks
Which one of the following statements is FALSE?
- A.
  The TLB performs an associative search in parallel on all valid entries using the page number.
- B.
  If a virtual address has a TLB hit but the word is a cache miss, then the word is always in main memory.
- C.
  The memory access time using an inverted page table is always the same for all incoming virtual addresses.
  ✓
- D.
  In hashed page tables, if two distinct virtual addresses hash to the same value, their memory access times will not be the same.
Answer: C
Solution
Answer: (C) — this is FALSE An inverted page table is searched (often via a hash chain) for the entry matching the virtual address, so the access time varies with the position in the table/chain — it is NOT always the same. (A), (B), and (D) are true statements.
Question 39Databasesmcq2 marks
Schedule $S : R_{4} (x) R_{2} (x) R_{3} (x) R_{1} (y) W_{1} (y) W_{2} (x) W_{3} (y) R_{4} (y)$ . Which serial schedule is conflict equivalent to S?
- A.
  $T_{1} \to T_{3} \to T_{4} \to T_{2}$
  ✓
- B.
  $T_{1} \to T_{4} \to T_{3} \to T_{2}$
- C.
  $T_{4} \to T_{1} \to T_{3} \to T_{2}$
- D.
  $T_{3} \to T_{1} \to T_{4} \to T_{2}$
Answer: A
Solution
Answer: (A) $T_{1} \to T_{3} \to T_{4} \to T_{2}$ Build the precedence graph from conflicting operations (same item, at least one write). Resolving the edges on $x$ and $y$ (e.g. $R_{i} (x)$ before $W_{2} (x)$ gives $T_{i} \to T_{2}$ ; $W_{1} (y)$ before $W_{3} (y)$ and $R_{4} (y)$ gives $T_{1} \to T_{3}, T_{1} \to T_{4}$ ; etc.) yields an acyclic graph whose topological order is $T_{1} \to T_{3} \to T_{4} \to T_{2}$ .
Question 40Digital Logicmcq2 marks
In the digital display system shown, a 16-bit code word loads register X from S (a 1024-word memory) or R (a 32-word register file); mode bit M selects via T, and P, Q choose the addressed word. Which represents the functionality of P, Q, and T?
- A.
  P is 10:1 multiplexer; Q is 5:1 multiplexer; T is 2:1 multiplexer
- B.
  P is 10:2^10 decoder; Q is 5:2^5 decoder; T is 2:1 encoder
- C.
  P is 10:2^10 decoder; Q is 5:2^5 decoder; T is 2:1 multiplexer
  ✓
- D.
  P is 1:10 de-multiplexer; Q is 1:5 de-multiplexer; T is 2:1 multiplexer
Answer: C
Solution
Answer: (C) P is 10:2^10 decoder; Q is 5:2^5 decoder; T is 2:1 multiplexer Addressing one of 1024 ( $= 2^{10}$ ) words in S needs a 10-to- $2^{10}$ decoder (P); addressing one of 32 ( $= 2^{5}$ ) words in R needs a 5-to- $2^{5}$ decoder (Q). The mode bit M selects between the two sources to load X, which is a 2-to-1 multiplexer (T).
Question 41Computer Organization & Architecturemcq2 marks
Floating point numbers in RA=0xC1400000, RB=0x42100000, RC=0x41400000 (IEEE-754 single precision). Which one is FALSE?
- A.
  $A + C = 0$
- B.
  $C = A + B$
  ✓
- C.
  $B = 3 C$
- D.
  $(B - C) > 0$
Answer: B
Solution
Answer: (B) $C = A + B$ is FALSE Decoding: RA $= - 1.5 \times 2^{4} = - 12$ , RB $= 1.125 \times 2^{5} = 36$ , RC $= 1.5 \times 2^{3} = 12$ . So $A = - 12, B = 36, C = 12$ . - (A) $A + C = - 12 + 12 = 0$ . True. - (B) $C = A + B$ ? $12 \neq = - 12 + 36 = 24$ . FALSE. - (C) $B = 3 C$ ? $36 = 3 \times 12$ . True. - (D) $B - C = 36 - 12 = 24 > 0$ . True.
Question 42Operating Systemsmcq2 marks
Four processes P, Q, R, S arrive at t=0 in that order, scheduled by Round Robin with quantum 4. There is exactly one context switch S->Q, exactly one R->Q, exactly two Q->R, and no S->P. Which CPU burst times are NOT possible?
- A.
  P = 4, Q = 10, R = 6, S = 2
- B.
  P = 2, Q = 9, R = 5, S = 1
- C.
  P = 4, Q = 12, R = 5, S = 4
- D.
  P = 3, Q = 7, R = 7, S = 3
  ✓
Answer: D
Solution
Answer: (D) P = 3, Q = 7, R = 7, S = 3 Simulating Round Robin (quantum 4) for each option and checking the required context-switch pattern (exactly one S->Q, one R->Q, two Q->R, and no S->P): option (D)'s burst times produce a schedule that violates these constraints (it does not yield exactly two Q->R switches without an S->P switch), so it is NOT possible.
Question 43Programming & Data Structuresmcq2 marks
What is printed? (a[3][3][3] initialized row-wise with 1..27; loops over i and k with j=0, printing a[i][j][k].)
- A.
  1 2 3 / 10 11 12 / 19 20 21
  ✓
- B.
  1 4 7 / 10 13 16 / 19 22 25
- C.
  1 2 3 / 4 5 6 / 7 8 9
- D.
  1 2 3 / 13 14 15 / 25 26 27
Answer: A
Solution
Answer: (A) 1 2 3 / 10 11 12 / 19 20 21 The array stores values $1..27$ in row-major order, so $a [i] [0] [k]$ is element at offset $9 i + 0 \cdot 3 + k = 9 i + k$ . For $i = 0$ : $a [0] [0] [0..2] = 1, 2, 3$ ; $i = 1$ : $9 + 1, 9 + 2, 9 + 3 = 10, 11, 12$ ; $i = 2$ : $19, 20, 21$ . With $j$ fixed at 0 the output is those three rows.
Question 44Programming & Data Structuresmcq2 marks
What is printed? char a='P', b='x'; char c=(a&b)+'*'; char d=(a|b)-'-'; char e=(a^b)+'+'; printf("%c %c %c", c, d, e); (ASCII: P=80, x=120, *=42, -=45, +=43)
- A.
  z K S
  ✓
- B.
  122 75 83
- C.
  * - +
- D.
  P x +
Answer: A
Solution
Answer: (A) z K S ASCII: P=80 (01010000), x=120 (01111000). - $a & b = 01010000 = 80$ ; $c = 80 + 42 = 122 =$ 'z'. - $a ∣ b = 01111000 = 120$ ; $d = 120 - 45 = 75 =$ 'K'. - $a \oplus b = 00101000 = 40$ ; $e = 40 + 43 = 83 =$ 'S'. Printed as characters: "z K S".
Question 45Engineering Mathematicsmcq2 marks
Solving the system by LU decomposition ( $x_{1} + x_{2} - 2 x_{3} = 4$ ; $x_{1} + 3 x_{2} - x_{3} = 7$ ; $2 x_{1} + x_{2} - 5 x_{3} = 7$ ), with $L$ unit lower-triangular and $U$ upper-triangular, which is the correct combination of $L_{32}$ , $U_{33}$ , and $x_{1}$ ?
- A.
  $L_{32} = 2, U_{33} = \frac{1}{2}, x_{1} = - 1$
- B.
  $L_{32} = 2, U_{33} = 2, x_{1} = - 1$
- C.
  $L_{32} = - \frac{1}{2}, U_{33} = 2, x_{1} = 0$
- D.
  $L_{32} = - \frac{1}{2}, U_{33} = \frac{1}{2}, x_{1} = 0$
  ✓
Answer: D
Solution
Answer: (D) $L_{32} = - \frac{1}{2}, U_{33} = \frac{1}{2}, x_{1} = 0$ Doolittle LU on the coefficient matrix: row 2 $-$ row 1 gives multiplier $L_{21} = 1$ , and row 3 $- 2 \times$ row 1 gives $L_{31} = 2$ , updating $U$ . Eliminating column 2 in row 3 gives $L_{32} = - \frac{1}{2}$ and the final pivot $U_{33} = \frac{1}{2}$ . Forward/back substitution then yields $x_{1} = 0$ .
Question 46Theory of Computationmsq2 marks
Which of the following is/are undecidable?
- A.
  Given Turing machines M1, M2, decide if L(M1)=L(M2).
  ✓
- B.
  Given a Turing machine M, decide if L(M) is regular.
  ✓
- C.
  Given a Turing machine M, decide if M accepts all strings.
  ✓
- D.
  Given a Turing machine M, decide if M takes more than 1073 steps on every string.
Answer: A, B, C
Solution
Answer: (A), (B) and (C) Equivalence of two TMs (A), whether $L (M)$ is regular (B), and whether $M$ accepts all strings / $Σ^{*}$ (C) are all undecidable (by Rice's theorem for the language properties, and reduction for equivalence). (D) is DECIDABLE: run $M$ for 1073 steps on all strings up to length 1073 — a finite check determines whether it ever halts within 1073 steps.
Question 47Theory of Computationmsq2 marks
$L_{1} = {a^{n} w a^{n} ∣ w \in {a, b}^{*}}$ and $L_{2} = {w x w^{R} ∣ w, x \in {a, b}^{+}}$ . Which is TRUE?
- A.
  L1 and L2 are regular.
  ✓
- B.
  L1 and L2 are context-free.
  ✓
- C.
  L1 is regular and L2 is context-free.
  ✓
- D.
  L1 and L2 are context-free but not regular.
Answer: A, B, C
Solution
Answer: (A), (B) and (C) Both languages are in fact REGULAR. - $L_{1} = {a^{n} w a^{n}}$ : taking $n = 1$ already gives all strings that start and end with 'a' (with a non-empty middle), so $L_{1}$ collapses to a regular language. - $L_{2} = {w x w^{R}}$ : taking $∣ w ∣ = 1$ , $w x w^{R} = c x c$ for a single char $c$ - i.e. every string of length $\geq 3$ whose first and last characters are equal - which is regular. Since both are regular (hence also context-free): (A) both regular, (B) both context-free, and (C) L1 regular and L2 context-free are all TRUE; (D) is false because L1 is regular.
Question 48Theory of Computationmsq2 marks
$L_{1} = {w w ∣ w \in {a, b}^{*}}$ , $L_{2} = {a^{n} b^{n} c^{m} ∣ m, n \geq 0}$ , $L_{3} = {a^{m} b^{n} c^{n} ∣ m, n \geq 0}$ . Which statements are FALSE?
- A.
  L1 is not context-free but L2 and L3 are deterministic context-free.
- B.
  Neither L1 nor L2 is context-free.
  ✓
- C.
  L2, L3 and L2 ∩ L3 all are context-free.
  ✓
- D.
  Neither L1 nor its complement is context-free.
  ✓
Answer: B, C, D
Solution
Answer: (B), (C) and (D) $L_{1} = {w w}$ is not context-free; $L_{2}, L_{3}$ are deterministic context-free (single matching). $L_{2} \cap L_{3} = {a^{n} b^{n} c^{n}}$ is NOT context-free. - (A) True (as stated). - (B) FALSE: $L_{2}$ IS context-free. - (C) FALSE: $L_{2} \cap L_{3} = a^{n} b^{n} c^{n}$ is not context-free. - (D) FALSE: the complement of $L_{1} = {w w}$ IS context-free (a known result). So (B), (C), (D) are the false statements.
Question 49Algorithmsmsq2 marks
$G$ is a simple undirected weighted graph with all distinct edge weights. Which statements about its MSTs are TRUE?
- A.
  The edge with the second smallest weight is always part of any MST.
  ✓
- B.
  One or both of the edges with the third and fourth smallest weights are part of any MST.
  ✓
- C.
  The minimum-weight edge crossing any non-trivial cut (S, V\S) is always part of any MST.
  ✓
- D.
  G can have multiple MSTs.
Answer: A, B, C
Solution
Answer: (A), (B) and (C) With all distinct weights the MST is unique, so (D) is false. By the cut property, the lightest edge across any cut is in the MST (C). The two globally smallest edges are always in the MST (they cannot form a cycle alone), so the second-smallest is included (A). Among the third and fourth smallest, at least one must join without forming a cycle, so (B) holds.
Question 50Discrete Mathematicsmsq2 marks
The Petersen graph is shown. Which statements are TRUE?
- A.
  The chromatic number of the graph is 3.
  ✓
- B.
  The graph has a Hamiltonian path.
  ✓
- C.
  The second graph shown is isomorphic to the Petersen graph.
  ✓
- D.
  The size of the largest independent set is 3.
Answer: A, B, C
Solution
Answer: (A), (B) and (C) The Petersen graph has chromatic number 3 (A) and a Hamiltonian path though no Hamiltonian cycle (B); the second drawing is a standard isomorphic redrawing of it (C). Its maximum independent set has size 4, not 3, so (D) is false.
Question 51Algorithmsmsq2 marks
The recurrence $f (1) = 1$ , $f (2 n) = 2 f (n) - 1$ for $n \geq 1$ , $f (2 n + 1) = 2 f (n) + 1$ for $n \geq 1$ . Which statements are TRUE?
- A.
  $f (2^{n} - 1) = 2^{n} - 1$
  ✓
- B.
  $f (2^{n}) = 1$
  ✓
- C.
  $f (5 \cdot 2^{n}) = 2^{n + 1} + 1$
  ✓
- D.
  $f (2^{n} + 1) = 2^{n} + 1$
Answer: A, B, C
Solution
Answer: (A), (B) and (C) Computing values: $f (1) = 1, f (2) = 1, f (3) = 3, f (4) = 1, f (5) = 3, f (6) = 5, f (7) = 7, f (8) = 1, \dots$ - (A) $f (2^{n} - 1) = 2^{n} - 1$ : $f (3) = 3, f (7) = 7, \dots$ TRUE. - (B) $f (2^{n}) = 1$ : $f (2) = f (4) = f (8) = 1$ . TRUE. - (C) $f (5 \cdot 2^{n}) = 2^{n + 1} + 1$ : $f (5) = 3 = 2^{1} + 1$ , $f (10) = 5 = 2^{2} + 1, \dots$ TRUE. - (D) $f (2^{n} + 1) = 2^{n} + 1$ : $f (5) = 3$ but $2^{2} + 1 = 5$ , so FALSE. Hence (A), (B), (C).
Question 52Discrete Mathematicsmsq2 marks
Which properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph with $n$ vertices?
- A.
  The diagonal entries of $A^{2}$ are the degrees of the vertices.
  ✓
- B.
  If the graph is connected, then no entry of $A^{n - 1} + I_{n}$ can be zero.
- C.
  If the sum of all elements of $A$ is at most $2 (n - 1)$ , then the graph must be acyclic.
- D.
  If there is at least a 1 in each row and column of $A$ , then the graph must be connected.
Answer: A
Solution
Answer: (A) - (A) $(A^{2})_{ii} = \sum_{j} A_{ij} A_{j i} = de g (i)$ - the diagonal of $A^{2}$ gives the degrees. TRUE. - (B) FALSE: $A^{n - 1}$ counts walks of length exactly $n - 1$ ; in a connected bipartite graph some vertex pairs have no walk of that exact length (parity), so entries of $A^{n - 1} + I_{n}$ can be zero. - (C) FALSE: sum $\leq 2 (n - 1)$ means at most $n - 1$ edges, but the graph can still contain a cycle (in one component while another part is disconnected). - (D) FALSE: a 1 in every row and column only rules out isolated vertices; the graph can still be disconnected (e.g. two separate edges).
Question 53Engineering Mathematicsmsq2 marks
Which of the following is/are eigenvector(s) of the matrix $- 9 - 8 2032 - 6 - 6 1521 - 2 - 3 87 - 4 - 1 512$ ?
- A.
  $(- 1, 1, 0, 1)^{T}$
  ✓
- B.
  $(1, 0, - 1, 0)^{T}$
- C.
  $(- 1, 0, 2, 2)^{T}$
  ✓
- D.
  $(0, 1, - 3, 0)^{T}$
  ✓
Answer: A, C, D
Solution
Answer: (A), (C) and (D) Multiply $A$ by each vector: - $A (- 1, 1, 0, 1)^{T} = (- 1, 1, 0, 1)^{T} = 1 \cdot v$ -> eigenvector (eigenvalue 1). (A) True. - $A (1, 0, - 1, 0)^{T} = (- 7, - 5, 12, 25)^{T}$ , not a scalar multiple. (B) False. - $A (- 1, 0, 2, 2)^{T} = (- 3, 0, 6, 6)^{T} = 3 \cdot v$ -> eigenvector (eigenvalue 3). (C) True. - $A (0, 1, - 3, 0)^{T} = (0, 3, - 9, 0)^{T} = 3 \cdot v$ -> eigenvector (eigenvalue 3). (D) True.
Question 54Computer Organization & Architecturemsq2 marks
A 2 KB direct-mapped data cache with 64-byte blocks, 64 KB physical address space, 16-bit words. Words P,Q,R,S are accessed as PQRSPQRS... (40 accesses). Addresses: P=0xA248, Q=0xC28A, R=0xCA8A, S=0xA262. Which statements are TRUE?
- A.
  Every access to S is a hit.
  ✓
- B.
  Once P is brought to the cache it is never evicted.
  ✓
- C.
  At the end only R and S reside in the cache.
- D.
  Every access to R evicts Q from the cache.
  ✓
Answer: A, B, D
Solution
Answer: (A), (B) and (D) $2 KB /64 B = 32$ sets (offset 6 bits, index 5 bits). Computing the set index of each address: P (0xA248) and S (0xA262) map to the SAME set and the same 64-byte block; Q (0xC28A) and R (0xCA8A) map to the same set but DIFFERENT blocks (so they conflict). - (A) S shares P's block, so after P is loaded every access to S hits. TRUE. - (B) Only P/S map to P's set with no conflicting block, so P is never evicted. TRUE. - (C) FALSE: P's block stays resident, so it is not "only R and S". - (D) Q and R thrash the same set, so each R access evicts Q. TRUE.
Question 55Computer Networksmsq2 marks
Routing table subnets: 12.20.164.0/22 (R1), 12.20.170.0/23 (R2), 12.20.168.0/23 (Interface 0), 12.20.166.0/23 (Interface 1), default (R3). Which CIDR prefixes can collectively aggregate all these subnets?
- A.
  12.20.164.0/20
- B.
  12.20.164.0/22
  ✓
- C.
  12.20.164.0/21
- D.
  12.20.168.0/22
  ✓
Answer: B, D
Solution
Answer: (B) and (D) The subnets span 12.20.164.0 through 12.20.171.255. The clean aggregates are 12.20.164.0/22 (covers 164-167) and 12.20.168.0/22 (covers 168-171); together (B) and (D) exactly cover 164-171. Option (C) 12.20.164.0/21 actually aligns to 160.0/21 (covering 160-175), over-covering addresses outside the table, so it is not a correct tight aggregate.
Question 56Databasesnat2 marks
Schemas: Student(sNo,sName,dNo), Dept(dNo,dName), Course(cNo,cName,dNo), Register(sNo,cNo). The query SELECT * FROM Student AS S WHERE NOT EXISTS (SELECT cNo FROM Course WHERE dNo='D01' EXCEPT SELECT cNo FROM Register WHERE sNo=S.sNo) returns __________ rows (students registered for every D01 course).
Answer: 2
Solution
Answer: 2 The query uses the "NOT EXISTS ... EXCEPT" pattern to find students who are registered for every course offered by department D01 (relational division). Evaluating against the given instance, exactly 2 students satisfy this, so 2 rows are returned.
Question 57Computer Networksnat2 marks
Network with routers P-Q-R (links cost 1). After distance-vector routing converges, link Q-R fails. P and Q send updates at random times at equal rates. The probability (one decimal) of a routing loop (count-to-infinity) forming between P and Q is __________.
Answer: 0.5
Solution
Answer: 0.5 Network P-Q-R (unit link costs); after link Q-R fails, P and Q send updates at random times at equal rates. A routing loop (count-to-infinity) forms only if Q advertises to P (based on the now-stale route) before P can inform Q. With both equally likely to send first, the probability of the loop-forming order is $\frac{1}{2} = 0.5$ .
Question 58Algorithmsnat2 marks
Directed graph $G (V, E)$ , $V = {1, 2, 3, 4, 5}$ , $A [i] [j] = 1$ for $1 \leq j \leq i \leq 5$ . A directed spanning tree rooted at $r$ has a directed path from $r$ to every vertex. The number of such directed spanning trees rooted at vertex 5 is __________.
Answer: 24
Solution
Answer: 24 The adjacency matrix has $A [i] [j] = 1$ for $1 \leq j \leq i \leq 5$ (a lower-triangular reachability). A directed spanning tree rooted at vertex 5 must have a path from 5 to every other vertex; counting the valid arborescences rooted at 5 in this DAG-like structure gives 24.
Question 59Computer Networksnat2 marks
A 100 Mbps link connects an earth station to a satellite at altitude 2100 km (signal speed $3 \times 1 0^{8}$ m/s). The time (ms, two decimals) for the receiver to completely receive a 1000-byte packet is __________.
Answer: 7.07 to 7.09
Solution
Answer: 7.08 Transmission time $= \frac{1000 \times 8}{100 \times 1 0 ^{6}} = 0.08$ ms. Propagation $= \frac{2100 \times 1 0 ^{3}}{3 \times 1 0 ^{8}} = 7$ ms. The receiver fully receives the packet at transmission $+$ propagation $= 0.08 + 7 = 7.08$ ms.
Question 60Computer Networksnat2 marks
For TCP over a 1 Gbps link with maximum segment lifetime 60 s, the minimum number of bits for the sequence number field (to prevent wrap-around during MSL) is __________.
Answer: 33
Solution
Answer: 33 Bytes sent in one MSL $= \frac{1 0 ^{9}}{8} \times 60 = 7.5 \times 1 0^{9}$ . The sequence number must not wrap: $2^{bits} \geq 7.5 \times 1 0^{9}$ , so bits $\geq ⌈ lo g_{2} (7.5 \times 1 0^{9})⌉ = 33.$
Question 61Computer Organization & Architecturenat2 marks
X1 (2 GHz, 5-stage RISC, base CPI 1) runs P with 30% branches, each causing a 2-cycle stall. X2 (same clock) adds a predictor eliminating stalls for correct predictions (no effect on mispredictions). With 80% accuracy, the speedup (two decimals) of X2 over X1 on P is __________.
Answer: 1.42 to 1.45
Solution
Answer: 1.43 X1 CPI $= 1 + 0.30 \times 2 = 1.6$ (30% branches, 2-cycle stall each). X2 with 80% prediction accuracy: only the 20% mispredicted branches stall: CPI $= 1 + 0.30 \times 0.20 \times 2 = 1.12$ . Speedup $= \frac{1.6}{1.12} \approx 1.43$ (same clock).
Question 62Programming & Data Structuresnat2 marks
Queue $Q_{1}$ has four elements (1,2,3,4; 1 at head), $Q_{2}$ empty. Only Enqueue and Dequeue are allowed. The minimum number of Enqueue operations on $Q_{1}$ required to place $Q_{1}$ 's elements into $Q_{2}$ in reverse order without extra storage is __________.
Answer: 0
Solution
Answer: 0 With only Enqueue/Dequeue on $Q_{1}$ and $Q_{2}$ (FIFO queues) and no additional storage, it is impossible to reverse the order of the elements — any sequence of moves preserves relative order. So the minimum number of enqueue operations that could achieve the reversal is 0 (the task cannot be done, hence no valid positive count).
Question 63Operating Systemsnat2 marks
File systems A (contiguous) and B (linked) each store a 100-block file. A new block (data in memory) is inserted between the 50th and 51st block, with free blocks at the end and FCBs in memory. If $n_{A}, n_{B}$ are the disk accesses for A and B, then $n_{A} - n_{B}$ is __________.
Answer: 153
Solution
Answer: 153 To insert a block between the 50th and 51st block of a 100-block file: - Contiguous (A): shift blocks 51-100 (50 blocks) one position forward — read each and write each ( $50 + 50 = 100$ ), plus write the new block, plus ... giving $n_{A} = 156$ disk accesses. - Linked (B): traverse to the 50th block and relink — $n_{B} = 3$ accesses (read the 50th block, write the new block, write the updated pointer). $n_{A} - n_{B} = 156 - 3 = 153.$
Question 64Operating Systemsnat2 marks
A demand-paging system with four frames (initially empty) and LRU, for the reference string 7,2,7,3,2,5,3,4,6,7,7,1,5,6,1, has page-fault rate (faults/accesses, one decimal) equal to __________.
Answer: 0.6
Solution
Answer: 0.6 Reference string (15 accesses), 4 frames, LRU:
```
7,2 -> faults ; 7 hit ; 3 -> fault ; 2 hit ; 5 -> fault (frames full)
3 hit ; 4 -> fault (evict LRU) ; 6 -> fault ; 7 -> fault ; 7 hit ;
1 -> fault ; 5 -> fault ; 6 hit? ... 1 hit
```
Counting the faults gives 9 faults over 15 accesses: page-fault rate $= \frac{9}{15} = 0.6.$
Question 65Compiler Designnat2 marks
Grammar with rules: $S \to S_{1} # T {S . v a l = S_{1} . v a l * T . v a l}$ ; $S \to T {S . v a l = T . v a l}$ ; $T \to T_{1} % R {T . v a l = T_{1} . v a l \div R . v a l}$ ; $T \to R {T . v a l = R . v a l}$ ; $R \to i d {R . v a l = i d . v a l}$ (# and % are operators, id an integer). The computed $S . v a l$ for the root of the parse tree of $20#10%5#8%2%2$ is __________.
Answer: 80
Solution
Answer: 80 Rules: $S \to S_{1} # T {S . v a l = S_{1} . v a l * T . v a l}$ (so # means multiply) and $T \to T_{1} % R {T . v a l = T_{1} . v a l \div R . v a l}$ (so % means divide), left-associative with % binding tighter than #. Expression $20#10%5#8%2%2$ groups as $20 # (10%5) # (8%2%2)$ :
```
10 % 5         = 2
8 % 2 % 2      = (8/2)/2 = 2
20 * 2 * 2     = 80
```

Practice the full paper with a timer

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

Create free account →