Ravi had ______ younger brother who taught at ______ university. He was widely regarded as ______ honorable man. Select the option with the correct sequence of articles to fill in the blanks.

A. Answer: (A) a; a; an Articles depend on the sound that follows, not the spelling. - "younger" starts with a consonant sound /j/ → "a". - "university" starts with a consonant sound /ju:/ → "a". - "honorable" starts with a vowel sound (silent h) → "an". So the sequence is "a; a; an".

The CEO's decision to downsize the workforce was considered myopic because it sacrificed long-term stability to accommodate short-term gains. Select the most appropriate option that can replace the word "myopic" without changing the meaning of the sentence.

B. Answer: (B) shortsighted "Myopic" literally means near-sighted; figuratively it means lacking foresight. The sentence confirms this ("sacrificed long-term stability ... for short-term gains"). The synonym is "shortsighted". "Visionary", "progressive" and "innovative" all mean the opposite (forward-looking).

The average marks obtained by a class in an examination were calculated as 30.8. However, while checking the marks entered, the teacher found that the marks of one student were entered incorrectly as 24 instead of 42. After correcting the marks, the average becomes 31.4. How many students does the class have?

C. Answer: (C) 30 The total increases by 42-24 = 18 after correction. This raised the average by 31.4 - 30.8 = 0.6. If n is the number of students, the extra 18 marks are spread over n students: \frac{18}{n} = 0.6 \;\Rightarrow\; n = \frac{18}{0.6} = 30.

Consider the relationships among P, Q, R, S, and T: - P is the brother of Q. - S is the daughter of Q. - T is the sister of S. - R is the mother of Q. The following statements are made based on the relationships given above. (1) R is the grandmother of S. (2) P is the uncle of S and T. (3) R has only one son. (4) Q has only one daughter. Which one of the following options is correct?

A. Answer: (A) Both (1) and (2) are true. - R is mother of Q, and Q is parent of S → R is the grandmother of S. (1) True. - P is brother of Q, and Q is parent of S and T → P is the uncle of S and T. (2) True. - (3) R has only one son: P is a son of R, but Q's sex is not given; Q could also be a son. Not guaranteed → not necessarily true. - (4) Q has only one daughter: Q has two daughters, S and T (T is the sister of S) → False. So only (1) and (2) are guaranteed.

According to the map shown in the figure, which one of the following statements is correct? Note: The figure shown is representative.

C. Answer: (C) The chemistry lab is to the southeast of physics lab. The two roads divide the map into four quadrants (compass: N up, E right): - NW: Library, Physics Lab - NE: Canteen, Hospital - SW: Hostels, Classrooms - SE: Chemistry Lab Physics Lab is in the NW block and Chemistry Lab is in the SE block → the chemistry lab is southeast of the physics lab. (C) is correct. - (A) Library and Canteen are in the same (top) row → library is west, not north-west, of the canteen. - (B) Hospital (NE) is

"I put the brown paper in my pocket along with the chalks, and possibly other things. I suppose every one must have reflected how primeval and how poetical are the things that one carries in one's pocket: the pocket-knife, for instance the type of all human tools, the infant of the sword. Once I planned to write a book of poems entirely about the things in my pocket. But I found it would be too long: and the age of the great epics is past." (From G.K. Chesterton's "A Piece of Chalk") Based only

C. Answer: (C) The pocket-knife is described as the infant of the sword. The passage literally states: the pocket-knife is "the type of all human tools, the infant of the sword." So (C) is directly supported. - (A) "reflected" is used figuratively (to ponder); there is no mirror. - (B) He planned a book of poems about the things in his pocket, not about epics. - (D) The book of poems would be "too long"; he does not call epics inconvenient to write.

In the diagram, the lines QR and ST are parallel to each other. The shortest distance between these two lines is half the shortest distance between the point P and line QR. What is the ratio of the area of the triangle PST to the area of the trapezium SQRT? Note: The figure shown is representative.

A. Answer: (A) \dfrac{1}{3} Let the distance from P to QR be h. The distance between ST and QR is h/2, so ST lies at height h-\tfrac{h}{2}=\tfrac{h}{2} below P. Since ST \parallel QR, triangle PST \sim triangle PQR with ratio of heights \tfrac{h/2}{h}=\tfrac12. Areas scale as the square: \frac{[PST]}{[PQR]}=\left(\tfrac12\right)^2=\frac14. The trapezium SQRT = [PQR]-[PST] = \tfrac34\,[PQR]. Therefore \frac{[PST]}{[SQRT]}=\frac{\tfrac14}{\tfrac34}=\frac13.

A fair six-faced dice, with the faces labelled '1', '2', '3', '4', '5', and '6', is rolled thrice. What is the probability of rolling '6' exactly once?

A. Answer: (A) \dfrac{75}{216} This is a binomial trial with n=3, success = rolling a 6, p=\tfrac16, q=\tfrac56. P(\text{exactly one }6)=\binom{3}{1}\left(\tfrac16\right)^1\left(\tfrac56\right)^2=3\cdot\tfrac16\cdot\tfrac{25}{36}=\frac{75}{216}.

A square paper, shown in figure (I), is folded along the dotted lines as shown in the figures (II) and (III). Then a few cuts are made as shown in figure (IV). Which one of the following patterns will be obtained when the paper is unfolded? Note: The figures shown are representative.

A. Answer: (A) The square is folded twice along the two diagonals, bringing all four corners together, and the cuts in figure (IV) are made on the folded quarter. When unfolding, each cut is reflected across both fold lines (the two diagonals), so every cut appears at four symmetric positions — once in each quadrant, with the pattern mirrored about both diagonals. Reconstructing the four-fold symmetric pattern from the cuts in (IV) gives the arrangement in option (A). Options (B), (C) and (D) break

A shop has 4 distinct flavors of ice-cream. One can purchase any number of scoops of any flavor. The order in which the scoops are purchased is inconsequential. If one wants to purchase 3 scoops of ice-cream, in how many ways can one make that purchase?

B. Answer: (B) 20 Choosing 3 scoops from 4 flavors with repetition allowed, order irrelevant, is a combination with repetition (stars and bars): \binom{n+k-1}{k}=\binom{4+3-1}{3}=\binom{6}{3}=20.

Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. The processor needs to execute the interrupt service routine (ISR) to serve this interrupt. The following steps (not necessarily in order) are taken by the processor when the interrupt arrives: (i) The processor saves the content of the program counter. (ii) The program counter is loaded with the start address of the IS

A. Answer: (A) (iii), (i), (ii) On an interrupt, the processor: 1. (iii) finishes the current instruction (interrupts are checked at instruction boundaries), 2. (i) saves the PC (return address) so it can resume later, 3. (ii) loads the PC with the ISR start address to begin servicing. Saving the PC must happen before overwriting it with the ISR address, so the order is (iii) → (i) → (ii).

Which ONE of the following statements is FALSE regarding the symbol table?

C. Answer: (C) — this statement is FALSE. The symbol table is used well beyond parsing — in semantic analysis (type checking, scope resolution), intermediate code generation, optimization and final code generation. So "not required after the parsing phase" is false. The other statements are true: the symbol table tracks scope (A), can be implemented with a BST/hash table (B), and entries begin to be created as early as lexical analysis (D).

Which ONE of the following techniques used in compiler code optimization uses live variable analysis?

B. Answer: (B) Register assignment to variables Live variable analysis computes, for each program point, which variables are live (will be used before being redefined). This is exactly the information needed for register allocation: two variables that are never simultaneously live can share a register, and dead values need not be kept in registers. Strength reduction and constant folding are algebraic/value optimizations; run-time call management is unrelated to liveness.

Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?

A. Answer: (A) 2^{21} Page size =2048=2^{11} bytes, so the page offset is 11 bits. With a 32-bit logical address, the page-number field is 32-11 = 21 bits. The number of page-table entries equals the number of pages in the logical address space: 2^{21}. (The physical address width determines frame-number size, not the number of page-table entries.)

A schedule of three database transactions T_1, T_2, and T_3 is shown. R_i(A) and W_i(A) denote read and write of data item A by transaction T_i, i=1,2,3. The transaction T_1 aborts at the end. Which other transaction(s) will be required to be rolled back? R_1(X)\ \ W_1(Y)\ \ R_2(X)\ \ R_2(Y)\ \ R_3(Y)\ \ ABORT(T_1)

C. Answer: (C) Both T_2 and T_3 T_1 writes Y with W_1(Y) and later aborts, so every transaction that read the uncommitted value of Y performs a dirty read and must be rolled back (cascading rollback). - R_2(Y) reads Y after W_1(Y) → T_2 read dirty data → roll back T_2. - R_3(Y) also reads Y (whose last writer is T_1, since T_2 never wrote Y) → T_3 read dirty data → roll back T_3. Hence both T_2 and T_3 must be rolled back.

Identify the ONE CORRECT matching between the OSI layers and their corresponding functionalities as shown. OSI Layer | Functionality --------------------+---------------------------- (a) Network layer | (I) Packet routing (b) Transport layer | (II) Framing and error handling (c) Datalink layer | (III) Host to host communication

B. Answer: (B) (a)-(I), (b)-(III), (c)-(II) - Network layer → packet routing (logical addressing, path selection): (I). - Transport layer → end-to-end / host-to-host communication (e.g. TCP, UDP): (III). - Data-link layer → framing and error handling (frames, CRC): (II).

g(\cdot) is a function from A to B, f(\cdot) is a function from B to C, and their composition defined as f(g(\cdot)) is a mapping from A to C. If f(\cdot) and f(g(\cdot)) are onto (surjective) functions, which ONE of the following is TRUE about the function g(\cdot)?

D. Answer: (D) g(\cdot) is not required to be one-to-one or onto. If f\circ g is onto then f must be onto — but nothing forces g to be onto or injective. Counterexample: A=\{1\}, B=\{p,q\}, C=\{x\}. Let g(1)=p (not onto B, trivially injective but need not be) and f(p)=f(q)=x. Then f is onto C and f(g(1))=x is onto C, yet g is not onto B. One can likewise make g non-injective. So g need not be injective or surjective.

Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices, u and v, let d_1(u,v) and d_2(u,v) be the shortest distances between u and v in G and T, respectively. Which ONE of the options is CORRECT for all possible G, T, u and v?

B. Answer: (B) d_1(u,v)\le d_2(u,v) T is a subgraph of G (it uses only edges of G). Any u–v path in T is also a path in G, so the shortest path in G can only be shorter or equal: d_1(u,v)\le d_2(u,v). Equality can occur (e.g. a tree edge), and strict inequality is common (a direct non-tree edge in G may be shorter), so (A), (C), (D) fail in general.

Consider the following context-free grammar G, where S, A, B are the variables (non-terminals), a and b are the terminal symbols, S is the start variable, and the rules of G are: S -> aaB | Abb A -> a | aA B -> b | bB Which ONE of the languages L(G) is accepted by G?

A. Answer: (A) \{a^2 b^n\mid n\ge1\}\cup\{a^n b^2\mid n\ge1\} A\Rightarrow a\mid aA generates a^{+} (one or more a's); B\Rightarrow b\mid bB generates b^{+}. - S\Rightarrow aaB \Rightarrow aa\,b^{n}=a^2 b^n with n\ge1. - S\Rightarrow Abb \Rightarrow a^{n}\,bb = a^n b^2 with n\ge1. Their union is exactly option (A).

Consider the following recurrence relation: T(n)=2T(n-1)+n\,2^n \text{ for } n>0,\qquad T(0)=1. Which ONE of the following options is CORRECT?

A. Answer: (A) T(n)=\Theta(n^2 2^n) Divide by 2^n. Let S(n)=T(n)/2^n: \frac{T(n)}{2^n}=\frac{T(n-1)}{2^{n-1}}+n \;\Rightarrow\; S(n)=S(n-1)+n. With S(0)=1, S(n)=1+\sum_{k=1}^{n}k = 1+\tfrac{n(n+1)}{2}=\Theta(n^2). Therefore T(n)=2^n S(n)=\Theta(n^2 2^n).

Consider the shown B^{+} tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the B^{+} tree. Which of the following option(s) is/are CORRECT?

B, D. Answer: (B) and (D) The rightmost leaf [20,21,22] is already full (max 3 keys). Inserting 23 gives [20,21,22,23] → overflow, so this leaf splits and a separator key is copied up to the root. The root is [6,12,19] (also full). Adding the copied-up key makes it [6,12,19,22] → the root overflows and splits too, creating a new root. A new root means the height increases. So (B) a split/redistribution happens, and (D) the height increases. (A) is false, and (C) is false because the node count rises f

Consider the 3-way handshaking protocol for TCP connection establishment. Let the three packets exchanged during the connection establishment be denoted as P1, P2, and P3, in order. Which of the following option(s) is/are TRUE with respect to TCP header flags that are set in the packets?

B, D. Answer: (B) and (D) TCP's three-way handshake: - P1 (client → server): SYN =1 (request). → (D) True. - P2 (server → client): SYN =1, ACK =1 (SYN-ACK). → (B) True, so (C) is False. - P3 (client → server): SYN =0, ACK =1 (pure ACK). → (A) is False.

Consider the given system of linear equations for variables x and y, where k is a real-valued constant. Which of the following option(s) is/are CORRECT? x+ky=1,\qquad kx+y=-1

A, D. Answer: (A) and (D) The coefficient determinant is \begin{vmatrix}1&k\\k&1\end{vmatrix}=1-k^2, which is zero only at k=\pm1. - For k\ne\pm1: unique solution (so (C) is false — there are infinitely many such k, not one). - k=1: equations become x+y=1 and x+y=-1 — inconsistent → no solution. This is the only such k → (A) True, and (B) False. - k=-1: equations become x-y=1 and -x+y=-1, i.e. the same line → infinitely many solutions, the only such k → (D) True.

Let X be a 3-variable Boolean function that produces output '1' when at least two of the input variables are '1' (the majority function). Which of the following statement(s) is/are CORRECT, where a,b,c,d,e are Boolean variables?

B, D. Answer: (B) and (D) X is the majority function M(p,q,r)=pq+qr+rp. - (B) Let m=M(a,b,c). If a=b then m=a and M(a,b,m)=M(a,a,a)=a=m. If a\ne b then m=c and M(a,b,c)=c=M(a,b,m). In all cases M(a,b,M(a,b,c))=M(a,b,c). True. - (D) M(a,c,c)=c, so RHS =M\big(a,\,m,\,c\big) with m=M(a,b,c). If a=c it equals a=c=m; if a\ne c then M(a,m,c)=m. So RHS =m=M(a,b,c)= LHS. True. - (A) Majority is not associative in this nested sense; a counterexample (e.g. a=b=1, c=d=e=0) makes the two sides differ. False. - (C

The number -6 can be represented as 1010 in 4-bit 2's complement representation. Which of the following is/are CORRECT 2's complement representation(s) of -6?

B, D. Answer: (B) and (D) To widen a 2's complement number, perform sign extension: copy the sign bit (here 1, since the number is negative) into all the new high-order bits. -6 = 1010_{(4)} → - 8-bit: 1111\,1010 → (B). - 16-bit: 1111\,1111\,1111\,1010 → (D). Options (A) and (C) pad with 0s (or a stray 1), which changes the value and is incorrect.

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having n distinct integers?

A, B. Answer: (A) and (B) - (A) A completely skewed BST (each node has one child) forms a chain of n nodes → longest root-to-node path has n-1 edges. True (this is the maximum). - (B) Inorder traversal of a BST always visits keys in increasing order. True. - (C) Search is O(h); in the worst case (skewed tree) h=n-1, so worst case is O(n), not O(\log n). False. - (D) A BST orders left < root < right; a Min-Heap requires parent \le children with no left/right ordering. A BST is generally not a min-heap.

A partial data path of a processor is given in the figure, where RA, RB, and RZ are 32-bit registers. Which option(s) is/are CORRECT related to arithmetic operations using the data path as shown?

A, B, C. Answer: (A), (B) and (C) Each ALU operand is driven by its own multiplexer: - Mux_A selects between register RA and a 32-bit immediate. - Mux_B selects between register RB and a 32-bit immediate. Because the two muxes are independent, the ALU inputs can be any combination: - (A) RA and RB → two registers. ✓ - (B) one register + one immediate (e.g. RA and immediate). ✓ - (C) immediate on Mux_A and immediate on Mux_B → two immediates. ✓ - (D) says it can only do register+immediate, which is false

A regular language L is accepted by a non-deterministic finite automaton (NFA) with n states. Which of the following statement(s) is/are FALSE?

D. Answer: (D) — this is the FALSE statement. By the subset construction, an n-state NFA has an equivalent DFA with at most 2^n states. So (C) is true, and (D) ("every DFA has more than 2^n states") is false — in fact the minimal DFA often has far fewer. (A) and (B) are true possibilities: the given NFA/DFA need not be minimal, so L may have an accepting NFA or DFA with fewer than n states.

Suppose in a multiprogramming environment, the following C program segment is executed. A process goes into I/O queue whenever an I/O related operation is performed. Assume that there will always be a context switch whenever a process requests for an I/O, and also whenever the process returns from an I/O. The number of times the process will enter the ready queue during its lifetime (not counting the time the process enters the ready queue when it is run initially) is _______. (Answer in integer

21. Answer: 21 Each I/O operation causes the process to move to the I/O queue; when the I/O completes, the process returns to the ready queue. So the process re-enters the ready queue once per I/O operation (the initial entry is excluded by the question). I/O operations here: - scanf → 1 I/O. - printf inside the loop, executed 20 times → 20 I/O. Total re-entries =1+20=\mathbf{21}.

Let S be the set of all ternary strings defined over the alphabet \{a,b,c\}. Consider all strings in S that contain at least one occurrence of two consecutive symbols, that is, "aa", "bb" or "cc". The number of such strings of length 5 that are possible is _______. (Answer in integer)

195. Answer: 195 Use complementary counting. - Total strings of length 5: 3^5 = 243. - Strings with no two consecutive equal symbols: the first symbol has 3 choices, each later symbol has 2 choices (anything except the previous one): 3\cdot 2^4 = 48. Strings with at least one "aa"/"bb"/"cc" =243-48=\mathbf{195}.

Consider the given function f(x): f(x)=\begin{cases} ax+b & \text{for } x<1\\ x^3+x^2+1 & \text{for } x\ge1\end{cases} If the function is differentiable everywhere, the value of b must be ________. (rounded off to one decimal place)

-2.1 to -1.9. Answer: -2.0 For differentiability at x=1, both the value and the derivative must match. Derivative of the right piece: 3x^2+2x; at x=1 it is 3+2=5. The left piece has slope a, so a=5. Continuity at x=1: left value =a(1)+b=5+b; right value =1+1+1=3. Setting them equal: 5+b=3 \;\Rightarrow\; b=-2.

A box contains 5 coins: 4 regular coins and 1 fake coin. When a regular coin is tossed, P(\text{head})=0.5 and for a fake coin P(\text{head})=1. You pick a coin at random and toss it twice, and get two heads. The probability that the coin you have chosen is the fake coin is _______. (rounded off to two decimal places)

0.49 to 0.51. Answer: 0.50 Let F = fake, R = regular. P(F)=\tfrac15, P(R)=\tfrac45. P(HH\mid F)=1,\qquad P(HH\mid R)=0.5^2=0.25. By total probability: P(HH)=\tfrac15(1)+\tfrac45(0.25)=0.2+0.2=0.4. By Bayes' theorem: P(F\mid HH)=\frac{P(HH\mid F)P(F)}{P(HH)}=\frac{0.2}{0.4}=0.50.

The pseudocode of a function fun() is given below: fun(int A[0..n-1]){ for i=0 to n-2 for j=0 to n-i-2 if (A[j] > A[j+1]) then swap A[j] and A[j+1] } Let A[0\ldots29] be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if fun() is called with A[0\ldots29], is __________. (Answer in integer)

435. Answer: 435 fun is bubble sort. For an array sorted in strictly descending order (the worst case), every compared adjacent pair is out of order, so each comparison causes a swap. The number of comparisons (and hence swaps) is \binom{n}{2}=\frac{n(n-1)}{2}=\frac{30\cdot 29}{2}=\mathbf{435}.

Consider the C program: #include void foo(int *p, int x){ *p = x; } int main(){ int *z; int a = 20, b = 25; z = &a; foo(z, b); printf("%d", a); return 0; } The output of the given C program is __________. (Answer in integer)

25. Answer: 25 z points to a. The call foo(z, b) passes this pointer and the value b = 25. Inside foo, *p = x writes 25 through the pointer, i.e. into a. So a becomes 25, and printf("%d", a) prints \mathbf{25}.

The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node. Suppose a Min-Heap T stores 32 keys. The height of T is _____________. (Answer in integer)

5. Answer: 5 A heap is a complete binary tree, whose height (in edges) for n nodes is \lfloor \log_2 n\rfloor. \lfloor\log_2 32\rfloor=\lfloor 5\rfloor = 5. (Levels 0–4 hold 1+2+4+8+16=31 nodes; the 32nd node sits on level 5, so the longest root-to-leaf path has 5 edges.)

Consider a memory system with 1M bytes of main memory and 16K bytes of cache memory. Assume that the processor generates 20-bit memory address, and the cache block size is 16 bytes. If the cache uses direct mapping, how many bits will be required to store all the tag values? [Assume memory is byte addressable, 1\text{K}=2^{10}, 1\text{M}=2^{20}.]

A. Answer: (A) 6\times 2^{10} Address =20 bits. Block size =16=2^4 → offset =4 bits. Number of cache lines =\dfrac{16\text{K}}{16}=1\text{K}=2^{10} → index (line) =10 bits. Tag =20-10-4=\mathbf{6} bits per line. Total tag storage =(\text{tag bits})\times(\text{number of lines})=6\times 2^{10} bits.

A processor has 64 general-purpose registers and 50 distinct instruction types. An instruction is encoded in 32-bits. What is the maximum number of bits that can be used to store the immediate operand for the given instruction? ADD R1, #25 // R1 = R1 + 25

B. Answer: (B) 20 Field sizes: - Opcode: 50 instruction types need \lceil\log_2 50\rceil = 6 bits. - Register: 64 registers need \log_2 64 = 6 bits (one register operand, R1). The instruction ADD R1, #imm uses one opcode + one register + the immediate. In 32 bits: \text{immediate} = 32 - 6 - 6 = \mathbf{20}\text{ bits}.

A computer has two processors, M_1 and M_2. Four processes P_1,P_2,P_3,P_4 with CPU bursts of 20, 16, 25, and 10 ms, respectively, arrive at the same time and are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities: - M_1: P_1 > P_3 > P_2 > P_4 (so P_1 highest, P_4 lowest). - M_2: P_2 > P_3 > P_4 > P_1 (so P_2 highest, P_1 lowest). A process P_i is scheduled on a free processor M_k if no higher-priority process is waiting. A process can go to

A. Answer: (A) 9.00 At t=0 both processors are free: - M_1 picks its highest-priority process P_1 (burst 20) → runs [0,20]. - M_2 picks its highest-priority process P_2 (burst 16) → runs [0,16]. At t=16, M_2 frees. Remaining P_3,P_4; by M_2's order P_3>P_4, so P_3 (burst 25) → runs [16,41]. At t=20, M_1 frees. Only P_4 left → P_4 (burst 10) → runs [20,30]. Waiting times (start - arrival): P_1=0,\ P_2=0,\ P_3=16,\ P_4=20. \text{Avg}=\frac{0+0+16+20}{4}=\frac{36}{4}=\mathbf{9.00}\text{ ms}.

Consider two relations describing teams and players: - teams(tid, tname) - players(pid, pname, tid) Which ONE of the following tuple relational calculus queries returns the name of the players who play for the team having tname as 'MI'?

A. Answer: (A) We want player names, so p must range over players (eliminating (B),(D)). We must link the player's team to a teams tuple named 'MI', which requires the join condition p.tid=t.tid and t.tname='MI'. Option (C) drops the join p.tid=t.tid, so it would return every player's name as long as some 'MI' team exists — wrong. Only (A) correctly joins the player to the 'MI' team.

A packet with destination IP address 145.36.109.70 arrives at a router whose routing table is shown. Which interface will the packet be forwarded to? Subnet Address | Subnet Mask (CIDR) | Interface ---------------+--------------------+---------- 145.36.0.0 | /16 | E1 145.36.128.0 | /17 | E2 145.36.64.0 | /18 | E3 145.36.255.0 | /24 | E4 Default | -- | E5

A. Answer: (A) E3 Routers use longest-prefix match. The third octet is 109 = 01101101_2. - /16 (145.36.0.0): matches. - /17 (145.36.128.0): needs third-octet top bit =1 (\ge128); 109<128 → no match. - /18 (145.36.64.0): needs third-octet top two bits =01 (range 64–127); 109 is in [64,127] → match. - /24 (145.36.255.0): third octet must be 255 → no. The longest matching prefix is /18 → interface E3.

Let A be the 2\times2 matrix A=\begin{bmatrix}1&1\\1&-1\end{bmatrix}. What are the eigenvalues of the matrix A^{13}?

D. Answer: (D) 64\sqrt2,\ -64\sqrt2 Eigenvalues of A: \det(A-\lambda I)=(1-\lambda)(-1-\lambda)-1=\lambda^2-2=0 \Rightarrow \lambda=\pm\sqrt2. Eigenvalues of A^{13} are \lambda^{13}: (\sqrt2)^{13}=2^{6.5}=2^6\sqrt2=64\sqrt2,\qquad (-\sqrt2)^{13}=-64\sqrt2.

Consider the four-variable Boolean function in sum-of-products form F(b_3,b_2,b_1,b_0)=\sum(0,2,4,8,10,11,12), where b_3b_2b_1b_0 is read as a 4-bit binary number (b_3 MSB). There are no don't-care terms. Which ONE of the following is the CORRECT minimized Boolean expression for F?

A. Answer: (A) \bar b_1\bar b_0 + \bar b_2\bar b_0 + b_1\bar b_2 b_3 Plot minterms 0,2,4,8,10,11,12 on a K-map: - 0,2,8,10 share b_1=0,b_0=0 → group \bar b_1\bar b_0. - 0,4,8,12 share b_2=0,b_0=0 → group \bar b_2\bar b_0. - Minterm 11=1011 is covered only together with 10=1010: they share b_3=1,b_2=0,b_1=1 → group b_1\bar b_2 b_3. Covering all seven minterms minimally gives F=\bar b_1\bar b_0+\bar b_2\bar b_0+b_1\bar b_2 b_3, which is option (A). The other options miss minterm 11 or include extra m

Let G(V,E) be an undirected, unweighted graph with 100 vertices. Let d(u,v) denote the number of edges in a shortest path between u and v. Suppose \max_{u\ne v} d(u,v)=30 (the diameter). Let T be any breadth-first-search tree of G. Which ONE of the options is CORRECT for every such graph G?

C. Answer: (C) The height of T is at least 15. A BFS tree rooted at r has height equal to the eccentricity of r (the maximum distance from r to any vertex). For any root r and the diametral pair u,v with d(u,v)=30: 30=d(u,v)\le d(u,r)+d(r,v)\le 2\cdot\text{ecc}(r). So \text{ecc}(r)\ge 15, i.e. the BFS-tree height is at least 15 for every root. It can be exactly 15 (root at the center) or as large as 30 (root at a diametral endpoint), so "exactly 15/30" and "at least 30" are not guaranteed.

Consider the following two languages over the alphabet \{a,b\}: L_1=\{\alpha\beta\alpha \mid \alpha\in\{a,b\}^{+}\ \text{AND}\ \beta\in\{a,b\}^{+}\} L_2=\{\alpha\beta\alpha \mid \alpha\in\{a\}^{+}\ \text{AND}\ \beta\in\{a,b\}^{+}\} Which ONE of the following statements is CORRECT?

C. Answer: (C) L_1 is not regular but L_2 is regular. L_2 is regular. Since \alpha consists only of a's, we can always take \alpha=a (a single a) and let \beta be the middle. So L_2 is exactly the set of strings that start with a, end with a, and have length \ge 3 — described by the regular expression a(a+b)^{+}a. L_1 is not regular. Here \alpha may be any non-empty string, and the same \alpha must appear as both a prefix and a suffix. When the first and last symbols differ (e.g. \alpha=ab), a sing

Consider the following two languages over \{a,b,c\}, where m,n are natural numbers: L_1=\{a^m b^m c^{m+n}\mid m,n\ge1\},\qquad L_2=\{a^m b^n c^{m+n}\mid m,n\ge1\}. Which ONE of the following statements is CORRECT?

C. Answer: (C) L_1 is not context-free but L_2 is context-free. L_2 is context-free. We need \#c=\#a+\#b. A PDA (or grammar) pushes one symbol for each a and each b, then pops one for each c: S -> a S c | B B -> b B c | b c This generates a^m b^n c^{m+n}. L_1 is not context-free. It requires \#a=\#b=m and \#c=m+n>m, i.e. two independent comparisons tied to m. A single stack can match a's with b's, but after that the count m is lost and cannot be compared again with the c's. By the pumping lemma for

Which of the following statement(s) is/are TRUE while computing First and Follow during top-down parsing by a compiler?

A, D. Answer: (A) and (D) - (A) By definition, if A\to\epsilon then \epsilon\in First(A). True. - (D) The end-of-input marker is always placed in Follow of the start symbol S. True. - (B) The end-of-input marker goes into Follow(S), never into any First set. False. - (C) \epsilon is never added to any Follow set; Follow sets contain only terminals and the end-of-input marker. False.

Consider a relational schema team(name, city, owner) with functional dependencies \{name\to city,\ name\to owner\}. The relation team is decomposed into t_1(name, city) and t_2(name, owner). Which of the following statement(s) is/are TRUE?

B, C. Answer: (B) and (C) The only determinant is name, and name is the (candidate) key of team. Every FD has a superkey on its left, so team is in BCNF (hence also in 3NF). Therefore (A) and (D) are false. - (B) Each decomposed relation has name as its key with FDs name\to city and name\to owner respectively — both in BCNF. True. - (C) The common attribute name is a key of both t_1 and t_2, so the decomposition is lossless. True.

Which of the following predicate logic formulae is/are CORRECT representation(s) of: "Everyone has exactly one mother"? Predicates: mother(y,x) means "y is the mother of x"; noteq(x,y) means "x and y are not equal".

B, D. Answer: (B) and (D) "Exactly one mother" = there exists a mother, and no other individual is also a mother. - (B) \exists y a mother y, and every z\ne y is not a mother → existence + uniqueness. True. - (D) \exists y a mother y, and there is no z\ne y that is a mother → same meaning. True. - (A) merely says some y is a mother and some z is not a mother — does not enforce uniqueness. False. - (C) z can be taken equal to y (since \neg noteq(z,y) means z=y), making it trivially true; it enforces ne

A=\{0,1,2,3,\dots\} is the set of non-negative integers. Let \mathbb{F} be the set of functions from A to itself. For f_1,f_2\in\mathbb{F}, define (f_1\odot f_2)(n)=f_1(n)+f_2(n) for every n\in A. Which of the following is/are CORRECT about the structure (\mathbb{F},\odot)?

B. Answer: (B) an Abelian monoid The operation is pointwise addition of functions. - Closure & associativity: inherited from integer addition. ✓ - Identity: the zero function z(n)=0 satisfies f\odot z=f, and z\in\mathbb{F}. ✓ → it is a monoid. - Commutative: f_1(n)+f_2(n)=f_2(n)+f_1(n) → Abelian. ✓ - Inverses: an inverse of f would need g(n)=-f(n), but negative values are not in A (non-negative integers). So only f=0 has an inverse → not a group. Hence (\mathbb{F},\odot) is an Abelian monoid, but n

Consider the deterministic finite automaton (DFA) shown, over \Sigma=\{a,b\}. Identify which of the following language(s) is/are accepted by the given DFA.

C. Answer: (C) The set of all strings ending with the pattern bab. The DFA is the standard 4-state minimal automaton that tracks the longest suffix matching a prefix of bab: q_0 (nothing) \xrightarrow{b} q_1 (b) \xrightarrow{a} q_2 (ba) \xrightarrow{b} q_3 (bab, accepting); with q_2\xrightarrow{a}q_0, q_3\xrightarrow{a}q_2, q_3\xrightarrow{b}q_1, and the self-loops shown. The only accepting state q_3 is reached exactly after reading a suffix bab. If another b follows, q_3\xrightarrow{b}q_1 leaves t

A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored using linked allocation. Each data block reserves 4 bytes to store the pointer to the next block; the last block's link is a NULL pointer (also 4 bytes). A file of 1M bytes is stored. Assume 1\text{K}=2^{10}, 1\text{M}=2^{20}. The amount of space in bytes wasted due to internal fragmentation is ______. (Answer in integer)

65468. Answer: 65468 Each 64\text{K}=65536-byte block reserves 4 bytes for the pointer, leaving 65536-4=65532 bytes of data per block. File size =1\text{M}=1048576 bytes. Blocks needed =\lceil 1048576/65532\rceil = \lceil 16.0009\rceil = 17 blocks. - First 16 blocks hold 16\times65532=1048512 bytes. - Remaining file data =1048576-1048512=64 bytes, placed in the 17th block. Internal fragmentation is the unused data area of the last block: 65532-64=\mathbf{65468}\text{ bytes}.

GATE CS 2025 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
Ravi had ______ younger brother who taught at ______ university. He was widely regarded as ______ honorable man. Select the option with the correct sequence of articles to fill in the blanks.
- A.
  a; a; an
  ✓
- B.
  the; an; a
- C.
  a; an; a
- D.
  an; an; a
Answer: A
Solution
Answer: (A) a; a; an Articles depend on the sound that follows, not the spelling. - "younger" starts with a consonant sound /j/ → "a". - "university" starts with a consonant sound /ju:/ → "a". - "honorable" starts with a vowel sound (silent h) → "an". So the sequence is "a; a; an".
Question 2General Aptitudemcq1 mark
The CEO's decision to downsize the workforce was considered myopic because it sacrificed long-term stability to accommodate short-term gains. Select the most appropriate option that can replace the word "myopic" without changing the meaning of the sentence.
- A.
  visionary
- B.
  shortsighted
  ✓
- C.
  progressive
- D.
  innovative
Answer: B
Solution
Answer: (B) shortsighted "Myopic" literally means near-sighted; figuratively it means lacking foresight. The sentence confirms this ("sacrificed long-term stability ... for short-term gains"). The synonym is "shortsighted". "Visionary", "progressive" and "innovative" all mean the opposite (forward-looking).
Question 3General Aptitudemcq1 mark
The average marks obtained by a class in an examination were calculated as $30.8$ . However, while checking the marks entered, the teacher found that the marks of one student were entered incorrectly as $24$ instead of $42$ . After correcting the marks, the average becomes $31.4$ . How many students does the class have?
- A.
  25
- B.
  28
- C.
  30
  ✓
- D.
  32
Answer: C
Solution
Answer: (C) 30 The total increases by $42 - 24 = 18$ after correction. This raised the average by $31.4 - 30.8 = 0.6$ . If $n$ is the number of students, the extra $18$ marks are spread over $n$ students:
$\frac{18}{n} = 0.6 \Rightarrow n = \frac{18}{0.6} = 30.$
Question 4General Aptitudemcq1 mark
Consider the relationships among P, Q, R, S, and T: - P is the brother of Q. - S is the daughter of Q. - T is the sister of S. - R is the mother of Q. The following statements are made based on the relationships given above. (1) R is the grandmother of S. (2) P is the uncle of S and T. (3) R has only one son. (4) Q has only one daughter. Which one of the following options is correct?
- A.
  Both (1) and (2) are true.
  ✓
- B.
  Both (1) and (3) are true.
- C.
  Only (3) is true.
- D.
  Only (4) is true.
Answer: A
Solution
Answer: (A) Both (1) and (2) are true. - R is mother of Q, and Q is parent of S → R is the grandmother of S. (1) True. - P is brother of Q, and Q is parent of S and T → P is the uncle of S and T. (2) True. - (3) R has only one son: P is a son of R, but Q's sex is not given; Q could also be a son. Not guaranteed → not necessarily true. - (4) Q has only one daughter: Q has two daughters, S and T (T is the sister of S) → False. So only (1) and (2) are guaranteed.
Question 5General Aptitudemcq1 mark
According to the map shown in the figure, which one of the following statements is correct? Note: The figure shown is representative.
- A.
  The library is located to the northwest of the canteen.
- B.
  The hospital is located to the east of the chemistry lab.
- C.
  The chemistry lab is to the southeast of physics lab.
  ✓
- D.
  The classrooms and canteen are next to each other.
Answer: C
Solution
Answer: (C) The chemistry lab is to the southeast of physics lab. The two roads divide the map into four quadrants (compass: N up, E right): - NW: Library, Physics Lab - NE: Canteen, Hospital - SW: Hostels, Classrooms - SE: Chemistry Lab Physics Lab is in the NW block and Chemistry Lab is in the SE block → the chemistry lab is southeast of the physics lab. (C) is correct. - (A) Library and Canteen are in the same (top) row → library is west, not north-west, of the canteen. - (B) Hospital (NE) is to the north of the chemistry lab (SE), not east. - (D) Classrooms (SW) and Canteen (NE) are in opposite corners, not next to each other.
Question 6General Aptitudemcq2 marks
"I put the brown paper in my pocket along with the chalks, and possibly other things. I suppose every one must have reflected how primeval and how poetical are the things that one carries in one's pocket: the pocket-knife, for instance the type of all human tools, the infant of the sword. Once I planned to write a book of poems entirely about the things in my pocket. But I found it would be too long: and the age of the great epics is past." (From G.K. Chesterton's "A Piece of Chalk") Based only on the information provided in the above passage, which one of the following statements is true?
- A.
  The author of the passage carries a mirror in his pocket to reflect upon things.
- B.
  The author of the passage had decided to write a poem on epics.
- C.
  The pocket-knife is described as the infant of the sword.
  ✓
- D.
  Epics are described as too inconvenient to write.
Answer: C
Solution
Answer: (C) The pocket-knife is described as the infant of the sword. The passage literally states: the pocket-knife is "the type of all human tools, the infant of the sword." So (C) is directly supported. - (A) "reflected" is used figuratively (to ponder); there is no mirror. - (B) He planned a book of poems about the things in his pocket, not about epics. - (D) The book of poems would be "too long"; he does not call epics inconvenient to write.
Question 7General Aptitudemcq2 marks
In the diagram, the lines QR and ST are parallel to each other. The shortest distance between these two lines is half the shortest distance between the point P and line QR. What is the ratio of the area of the triangle PST to the area of the trapezium SQRT? Note: The figure shown is representative.
- A.
  $\frac{1}{3}$
  ✓
- B.
  $\frac{1}{4}$
- C.
  $\frac{2}{5}$
- D.
  $\frac{1}{2}$
Answer: A
Solution
Answer: (A) $\frac{1}{3}$ Let the distance from $P$ to $QR$ be $h$ . The distance between $S T$ and $QR$ is $h /2$ , so $S T$ lies at height $h - \frac{h}{2} = \frac{h}{2}$ below $P$ . Since $S T ∥ QR$ , triangle $P S T \sim$ triangle $P QR$ with ratio of heights $\frac{h /2}{h} = \frac{1}{2}$ . Areas scale as the square:
$\frac{[ P S T ]}{[ P QR ]} = (\frac{1}{2})^{2} = \frac{1}{4} .$
The trapezium $S QR T = [P QR] - [P S T] = \frac{3}{4} [P QR]$ . Therefore
$\frac{[ P S T ]}{[ S QR T ]} = \frac{\frac{1}{4}}{\frac{3}{4}} = \frac{1}{3} .$
Question 8General Aptitudemcq2 marks
A fair six-faced dice, with the faces labelled '1', '2', '3', '4', '5', and '6', is rolled thrice. What is the probability of rolling '6' exactly once?
- A.
  $\frac{75}{216}$
  ✓
- B.
  $\frac{1}{6}$
- C.
  $\frac{1}{18}$
- D.
  $\frac{25}{216}$
Answer: A
Solution
Answer: (A) $\frac{75}{216}$ This is a binomial trial with $n = 3$ , success $=$ rolling a 6, $p = \frac{1}{6}$ , $q = \frac{5}{6}$ .
$P (exactly one 6) = (1 3) (\frac{1}{6})^{1} (\frac{5}{6})^{2} = 3 \cdot \frac{1}{6} \cdot \frac{25}{36} = \frac{75}{216} .$
Question 9General Aptitudemcq2 marks
A square paper, shown in figure (I), is folded along the dotted lines as shown in the figures (II) and (III). Then a few cuts are made as shown in figure (IV). Which one of the following patterns will be obtained when the paper is unfolded? Note: The figures shown are representative.
- A.✓
- B.
- C.
- D.
Answer: A
Solution
Answer: (A) The square is folded twice along the two diagonals, bringing all four corners together, and the cuts in figure (IV) are made on the folded quarter. When unfolding, each cut is reflected across both fold lines (the two diagonals), so every cut appears at four symmetric positions — once in each quadrant, with the pattern mirrored about both diagonals. Reconstructing the four-fold symmetric pattern from the cuts in (IV) gives the arrangement in option (A). Options (B), (C) and (D) break the required diagonal (4-fold) symmetry, so they cannot result from folding along both diagonals.
Question 10General Aptitudemcq2 marks
A shop has 4 distinct flavors of ice-cream. One can purchase any number of scoops of any flavor. The order in which the scoops are purchased is inconsequential. If one wants to purchase 3 scoops of ice-cream, in how many ways can one make that purchase?
- A.
  4
- B.
  20
  ✓
- C.
  24
- D.
  48
Answer: B
Solution
Answer: (B) 20 Choosing 3 scoops from 4 flavors with repetition allowed, order irrelevant, is a combination with repetition (stars and bars):
$(k n + k - 1) = (3 4 + 3 - 1) = (3 6) = 20.$
Question 11Computer Organization & Architecturemcq1 mark
Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. The processor needs to execute the interrupt service routine (ISR) to serve this interrupt. The following steps (not necessarily in order) are taken by the processor when the interrupt arrives: (i) The processor saves the content of the program counter. (ii) The program counter is loaded with the start address of the ISR. (iii) The processor finishes the present instruction. Which ONE of the following is the CORRECT sequence of steps?
- A.
  (iii), (i), (ii)
  ✓
- B.
  (i), (iii), (ii)
- C.
  (i), (ii), (iii)
- D.
  (iii), (ii), (i)
Answer: A
Solution
Answer: (A) (iii), (i), (ii) On an interrupt, the processor: 1. (iii) finishes the current instruction (interrupts are checked at instruction boundaries), 2. (i) saves the PC (return address) so it can resume later, 3. (ii) loads the PC with the ISR start address to begin servicing. Saving the PC must happen before overwriting it with the ISR address, so the order is (iii) → (i) → (ii).
Question 12Compiler Designmcq1 mark
Which ONE of the following statements is FALSE regarding the symbol table?
- A.
  Symbol table is responsible for keeping track of the scope of variables.
- B.
  Symbol table can be implemented using a binary search tree.
- C.
  Symbol table is not required after the parsing phase.
  ✓
- D.
  Symbol table is created during the lexical analysis phase.
Answer: C
Solution
Answer: (C) — this statement is FALSE. The symbol table is used well beyond parsing — in semantic analysis (type checking, scope resolution), intermediate code generation, optimization and final code generation. So "not required after the parsing phase" is false. The other statements are true: the symbol table tracks scope (A), can be implemented with a BST/hash table (B), and entries begin to be created as early as lexical analysis (D).
Question 13Compiler Designmcq1 mark
Which ONE of the following techniques used in compiler code optimization uses live variable analysis?
- A.
  Run-time function call management
- B.
  Register assignment to variables
  ✓
- C.
  Strength reduction
- D.
  Constant folding
Answer: B
Solution
Answer: (B) Register assignment to variables Live variable analysis computes, for each program point, which variables are live (will be used before being redefined). This is exactly the information needed for register allocation: two variables that are never simultaneously live can share a register, and dead values need not be kept in registers. Strength reduction and constant folding are algebraic/value optimizations; run-time call management is unrelated to liveness.
Question 14Operating Systemsmcq1 mark
Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?
- A.
  $2^{21}$
  ✓
- B.
  $2^{20}$
- C.
  $2^{22}$
- D.
  $2^{24}$
Answer: A
Solution
Answer: (A) $2^{21}$ Page size $= 2048 = 2^{11}$ bytes, so the page offset is $11$ bits. With a $32$ -bit logical address, the page-number field is $32 - 11 = 21$ bits. The number of page-table entries equals the number of pages in the logical address space:
$2^{21} .$
(The physical address width determines frame-number size, not the number of page-table entries.)
Question 15Databasesmcq1 mark
A schedule of three database transactions $T_{1}$ , $T_{2}$ , and $T_{3}$ is shown. $R_{i} (A)$ and $W_{i} (A)$ denote read and write of data item $A$ by transaction $T_{i}$ , $i = 1, 2, 3$ . The transaction $T_{1}$ aborts at the end. Which other transaction(s) will be required to be rolled back?
$R_{1} (X) W_{1} (Y) R_{2} (X) R_{2} (Y) R_{3} (Y) A B O R T (T_{1})$
- A.
  Only $T_{2}$
- B.
  Only $T_{3}$
- C.
  Both $T_{2}$ and $T_{3}$
  ✓
- D.
  Neither $T_{2}$ nor $T_{3}$
Answer: C
Solution
Answer: (C) Both $T_{2}$ and $T_{3}$ $T_{1}$ writes $Y$ with $W_{1} (Y)$ and later aborts, so every transaction that read the uncommitted value of $Y$ performs a dirty read and must be rolled back (cascading rollback). - $R_{2} (Y)$ reads $Y$ after $W_{1} (Y)$ → $T_{2}$ read dirty data → roll back $T_{2}$ . - $R_{3} (Y)$ also reads $Y$ (whose last writer is $T_{1}$ , since $T_{2}$ never wrote $Y$ ) → $T_{3}$ read dirty data → roll back $T_{3}$ . Hence both $T_{2}$ and $T_{3}$ must be rolled back.
Question 16Computer Networksmcq1 mark
Identify the ONE CORRECT matching between the OSI layers and their corresponding functionalities as shown.
```
OSI Layer           | Functionality
--------------------+----------------------------
(a) Network layer   | (I)   Packet routing
(b) Transport layer | (II)  Framing and error handling
(c) Datalink layer  | (III) Host to host communication
```
- A.
  (a)-(I), (b)-(II), (c)-(III)
- B.
  (a)-(I), (b)-(III), (c)-(II)
  ✓
- C.
  (a)-(II), (b)-(I), (c)-(III)
- D.
  (a)-(III), (b)-(II), (c)-(I)
Answer: B
Solution
Answer: (B) (a)-(I), (b)-(III), (c)-(II) - Network layer → packet routing (logical addressing, path selection): (I). - Transport layer → end-to-end / host-to-host communication (e.g. TCP, UDP): (III). - Data-link layer → framing and error handling (frames, CRC): (II).
Question 17Discrete Mathematicsmcq1 mark
$g (\cdot)$ is a function from $A$ to $B$ , $f (\cdot)$ is a function from $B$ to $C$ , and their composition defined as $f (g (\cdot))$ is a mapping from $A$ to $C$ . If $f (\cdot)$ and $f (g (\cdot))$ are onto (surjective) functions, which ONE of the following is TRUE about the function $g (\cdot)$ ?
- A.
  $g (\cdot)$ must be an onto (surjective) function.
- B.
  $g (\cdot)$ must be a one-to-one (injective) function.
- C.
  $g (\cdot)$ must be a bijective function, that is, both one-to-one and onto.
- D.
  $g (\cdot)$ is not required to be a one-to-one or onto function.
  ✓
Answer: D
Solution
Answer: (D) $g (\cdot)$ is not required to be one-to-one or onto. If $f \circ g$ is onto then $f$ must be onto — but nothing forces $g$ to be onto or injective. Counterexample: $A = {1}$ , $B = {p, q}$ , $C = {x}$ . Let $g (1) = p$ (not onto $B$ , trivially injective but need not be) and $f (p) = f (q) = x$ . Then $f$ is onto $C$ and $f (g (1)) = x$ is onto $C$ , yet $g$ is not onto $B$ . One can likewise make $g$ non-injective. So $g$ need not be injective or surjective.
Question 18Algorithmsmcq1 mark
Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$ . For any two vertices, $u$ and $v$ , let $d_{1} (u, v)$ and $d_{2} (u, v)$ be the shortest distances between $u$ and $v$ in $G$ and $T$ , respectively. Which ONE of the options is CORRECT for all possible $G, T, u$ and $v$ ?
- A.
  $d_{1} (u, v) = d_{2} (u, v)$
- B.
  $d_{1} (u, v) \leq d_{2} (u, v)$
  ✓
- C.
  $d_{1} (u, v) \geq d_{2} (u, v)$
- D.
  $d_{1} (u, v) \neq = d_{2} (u, v)$
Answer: B
Solution
Answer: (B) $d_{1} (u, v) \leq d_{2} (u, v)$ $T$ is a subgraph of $G$ (it uses only edges of $G$ ). Any $u$ – $v$ path in $T$ is also a path in $G$ , so the shortest path in $G$ can only be shorter or equal:
$d_{1} (u, v) \leq d_{2} (u, v) .$
Equality can occur (e.g. a tree edge), and strict inequality is common (a direct non-tree edge in $G$ may be shorter), so (A), (C), (D) fail in general.
Question 19Theory of Computationmcq1 mark
Consider the following context-free grammar $G$ , where $S, A, B$ are the variables (non-terminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and the rules of $G$ are:
```
S -> aaB | Abb
A -> a | aA
B -> b | bB
```
Which ONE of the languages $L (G)$ is accepted by $G$ ?
- A.
  $L (G) = {a^{2} b^{n} ∣ n \geq 1} \cup {a^{n} b^{2} ∣ n \geq 1}$
  ✓
- B.
  $L (G) = {a^{n} b^{2 n} ∣ n \geq 1} \cup {a^{2 n} b^{n} ∣ n \geq 1}$
- C.
  $L (G) = {a^{n} b^{n} ∣ n \geq 1}$
- D.
  $L (G) = {a^{2 n} b^{2 n} ∣ n \geq 1}$
Answer: A
Solution
Answer: (A) ${a^{2} b^{n} ∣ n \geq 1} \cup {a^{n} b^{2} ∣ n \geq 1}$ $A \Rightarrow a ∣ a A$ generates $a^{+}$ (one or more $a$ 's); $B \Rightarrow b ∣ b B$ generates $b^{+}$ . - $S \Rightarrow aa B \Rightarrow aa b^{n} = a^{2} b^{n}$ with $n \geq 1$ . - $S \Rightarrow A bb \Rightarrow a^{n} bb = a^{n} b^{2}$ with $n \geq 1$ . Their union is exactly option (A).
Question 20Algorithmsmcq1 mark
Consider the following recurrence relation:
$T (n) = 2 T (n - 1) + n 2^{n} for n > 0, T (0) = 1.$
Which ONE of the following options is CORRECT?
- A.
  $T (n) = Θ (n^{2} 2^{n})$
  ✓
- B.
  $T (n) = Θ (n 2^{n})$
- C.
  $T (n) = Θ ((lo g n)^{2} 2^{n})$
- D.
  $T (n) = Θ (4^{n})$
Answer: A
Solution
Answer: (A) $T (n) = Θ (n^{2} 2^{n})$ Divide by $2^{n}$ . Let $S (n) = T (n) / 2^{n}$ :
$\frac{T ( n )}{2 ^{n}} = \frac{T ( n - 1 )}{2 ^{n - 1}} + n \Rightarrow S (n) = S (n - 1) + n .$
With $S (0) = 1$ , $S (n) = 1 + \sum_{k = 1}^{n} k = 1 + \frac{n ( n + 1 )}{2} = Θ (n^{2})$ . Therefore $T (n) = 2^{n} S (n) = Θ (n^{2} 2^{n}) .$
Question 21Databasesmsq1 mark
Consider the shown $B^{+}$ tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the $B^{+}$ tree. Which of the following option(s) is/are CORRECT?
- A.
  None of the nodes will split.
- B.
  At least one node will split and redistribute.
  ✓
- C.
  The total number of nodes will remain same.
- D.
  The height of the tree will increase.
  ✓
Answer: B, D
Solution
Answer: (B) and (D) The rightmost leaf $[20, 21, 22]$ is already full (max 3 keys). Inserting 23 gives $[20, 21, 22, 23]$ → overflow, so this leaf splits and a separator key is copied up to the root. The root is $[6, 12, 19]$ (also full). Adding the copied-up key makes it $[6, 12, 19, 22]$ → the root overflows and splits too, creating a new root. A new root means the height increases. So (B) a split/redistribution happens, and (D) the height increases. (A) is false, and (C) is false because the node count rises from 5 to 7.
Question 22Computer Networksmsq1 mark
Consider the 3-way handshaking protocol for TCP connection establishment. Let the three packets exchanged during the connection establishment be denoted as P1, P2, and P3, in order. Which of the following option(s) is/are TRUE with respect to TCP header flags that are set in the packets?
- A.
  P3: SYN = 1, ACK = 1
- B.
  P2: SYN = 1, ACK = 1
  ✓
- C.
  P2: SYN = 0, ACK = 1
- D.
  P1: SYN = 1
  ✓
Answer: B, D
Solution
Answer: (B) and (D) TCP's three-way handshake: - P1 (client → server): SYN $= 1$ (request). → (D) True. - P2 (server → client): SYN $= 1$ , ACK $= 1$ (SYN-ACK). → (B) True, so (C) is False. - P3 (client → server): SYN $= 0$ , ACK $= 1$ (pure ACK). → (A) is False.
Question 23Engineering Mathematicsmsq1 mark
Consider the given system of linear equations for variables $x$ and $y$ , where $k$ is a real-valued constant. Which of the following option(s) is/are CORRECT?
$x + k y = 1, k x + y = - 1$
- A.
  There is exactly one value of $k$ for which the system has no solution.
  ✓
- B.
  There exist an infinite number of values of $k$ for which the system has no solution.
- C.
  There exists exactly one value of $k$ for which the system has exactly one solution.
- D.
  There exists exactly one value of $k$ for which the system has an infinite number of solutions.
  ✓
Answer: A, D
Solution
Answer: (A) and (D) The coefficient determinant is $1 k k 1 = 1 - k^{2}$ , which is zero only at $k = \pm 1$ . - For $k \neq = \pm 1$ : unique solution (so (C) is false — there are infinitely many such $k$ , not one). - $k = 1$ : equations become $x + y = 1$ and $x + y = - 1$ — inconsistent → no solution. This is the only such $k$ → (A) True, and (B) False. - $k = - 1$ : equations become $x - y = 1$ and $- x + y = - 1$ , i.e. the same line → infinitely many solutions, the only such $k$ → (D) True.
Question 24Digital Logicmsq1 mark
Let $X$ be a 3-variable Boolean function that produces output '1' when at least two of the input variables are '1' (the majority function). Which of the following statement(s) is/are CORRECT, where $a, b, c, d, e$ are Boolean variables?
- A.
  $X (a, b, X (c, d, e)) = X (X (a, b, c), d, e)$
- B.
  $X (a, b, X (a, b, c)) = X (a, b, c)$
  ✓
- C.
  $X (a, b, X (a, c, d)) = (X (a, b, a) AND X (c, d, c))$
- D.
  $X (a, b, c) = X (a, X (a, b, c), X (a, c, c))$
  ✓
Answer: B, D
Solution
Answer: (B) and (D) $X$ is the majority function $M (p, q, r) = pq + q r + r p$ . - (B) Let $m = M (a, b, c)$ . If $a = b$ then $m = a$ and $M (a, b, m) = M (a, a, a) = a = m$ . If $a \neq = b$ then $m = c$ and $M (a, b, c) = c = M (a, b, m)$ . In all cases $M (a, b, M (a, b, c)) = M (a, b, c)$ . True. - (D) $M (a, c, c) = c$ , so RHS $= M (a, m, c)$ with $m = M (a, b, c)$ . If $a = c$ it equals $a = c = m$ ; if $a \neq = c$ then $M (a, m, c) = m$ . So RHS $= m = M (a, b, c) =$ LHS. True. - (A) Majority is not associative in this nested sense; a counterexample (e.g. $a = b = 1, c = d = e = 0$ ) makes the two sides differ. False. - (C) $X (a, b, a) = a$ and $X (c, d, c) = c$ , so RHS $= a AND c = a c$ , which does not equal the LHS in general. False.
Question 25Digital Logicmsq1 mark
The number $- 6$ can be represented as $1010$ in 4-bit 2's complement representation. Which of the following is/are CORRECT 2's complement representation(s) of $- 6$ ?
- A.
  1000 1010 in 8-bits
- B.
  1111 1010 in 8-bits
  ✓
- C.
  1000 0000 0000 1010 in 16-bits
- D.
  1111 1111 1111 1010 in 16-bits
  ✓
Answer: B, D
Solution
Answer: (B) and (D) To widen a 2's complement number, perform sign extension: copy the sign bit (here $1$ , since the number is negative) into all the new high-order bits. $- 6 = 101 0_{(4)}$ → - 8-bit: $11111010$ → (B). - 16-bit: $1111111111111010$ → (D). Options (A) and (C) pad with $0$ s (or a stray $1$ ), which changes the value and is incorrect.
Question 26Programming & Data Structuresmsq1 mark
Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?
- A.
  The maximum length of a path from the root node to any other node is $(n - 1)$ .
  ✓
- B.
  An inorder traversal will always produce a sorted sequence of elements.
  ✓
- C.
  Finding an element takes $O (lo g_{2} n)$ time in the worst case.
- D.
  Every BST is also a Min-Heap.
Answer: A, B
Solution
Answer: (A) and (B) - (A) A completely skewed BST (each node has one child) forms a chain of $n$ nodes → longest root-to-node path has $n - 1$ edges. True (this is the maximum). - (B) Inorder traversal of a BST always visits keys in increasing order. True. - (C) Search is $O (h)$ ; in the worst case (skewed tree) $h = n - 1$ , so worst case is $O (n)$ , not $O (lo g n)$ . False. - (D) A BST orders left $<$ root $<$ right; a Min-Heap requires parent $\leq$ children with no left/right ordering. A BST is generally not a min-heap. False.
Question 27Computer Organization & Architecturemsq1 mark
A partial data path of a processor is given in the figure, where RA, RB, and RZ are 32-bit registers. Which option(s) is/are CORRECT related to arithmetic operations using the data path as shown?
- A.
  The data path can implement arithmetic operations involving two registers.
  ✓
- B.
  The data path can implement arithmetic operations involving one register and one immediate value.
  ✓
- C.
  The data path can implement arithmetic operations involving two immediate values.
  ✓
- D.
  The data path can only implement arithmetic operations involving one register and one immediate value.
Answer: A, B, C
Solution
Answer: (A), (B) and (C) Each ALU operand is driven by its own multiplexer: - Mux_A selects between register RA and a 32-bit immediate. - Mux_B selects between register RB and a 32-bit immediate. Because the two muxes are independent, the ALU inputs can be any combination: - (A) RA and RB → two registers. ✓ - (B) one register + one immediate (e.g. RA and immediate). ✓ - (C) immediate on Mux_A and immediate on Mux_B → two immediates. ✓ - (D) says it can only do register+immediate, which is false since (A) and (C) are also possible.
Question 28Theory of Computationmsq1 mark
A regular language $L$ is accepted by a non-deterministic finite automaton (NFA) with $n$ states. Which of the following statement(s) is/are FALSE?
- A.
  $L$ may have an accepting NFA with $< n$ states.
- B.
  $L$ may have an accepting DFA with $< n$ states.
- C.
  There exists a DFA with $\leq 2^{n}$ states that accepts $L$ .
- D.
  Every DFA that accepts $L$ has $> 2^{n}$ states.
  ✓
Answer: D
Solution
Answer: (D) — this is the FALSE statement. By the subset construction, an $n$ -state NFA has an equivalent DFA with at most $2^{n}$ states. So (C) is true, and (D) ("every DFA has more than $2^{n}$ states") is false — in fact the minimal DFA often has far fewer. (A) and (B) are true possibilities: the given NFA/DFA need not be minimal, so $L$ may have an accepting NFA or DFA with fewer than $n$ states.
Question 29Operating Systemsnat1 mark
Suppose in a multiprogramming environment, the following C program segment is executed. A process goes into I/O queue whenever an I/O related operation is performed. Assume that there will always be a context switch whenever a process requests for an I/O, and also whenever the process returns from an I/O. The number of times the process will enter the ready queue during its lifetime (not counting the time the process enters the ready queue when it is run initially) is _______. (Answer in integer)
```
int main()
{
    int x=0,i=0;
    scanf("%d",&x);
    for(i=0; i<20; i++)
    {
        x = x+20;
        printf("%d\n",x);
    }
    return 0;
}
```
Answer: 21
Solution
Answer: 21 Each I/O operation causes the process to move to the I/O queue; when the I/O completes, the process returns to the ready queue. So the process re-enters the ready queue once per I/O operation (the initial entry is excluded by the question). I/O operations here: - scanf → 1 I/O. - printf inside the loop, executed 20 times → 20 I/O. Total re-entries $= 1 + 20 = 21$ .
Question 30Discrete Mathematicsnat1 mark
Let $S$ be the set of all ternary strings defined over the alphabet ${a, b, c}$ . Consider all strings in $S$ that contain at least one occurrence of two consecutive symbols, that is, "aa", "bb" or "cc". The number of such strings of length 5 that are possible is _______. (Answer in integer)
Answer: 195
Solution
Answer: 195 Use complementary counting. - Total strings of length 5: $3^{5} = 243$ . - Strings with no two consecutive equal symbols: the first symbol has $3$ choices, each later symbol has $2$ choices (anything except the previous one): $3 \cdot 2^{4} = 48$ . Strings with at least one "aa"/"bb"/"cc" $= 243 - 48 = 195 .$
Question 31Engineering Mathematicsnat1 mark
Consider the given function $f (x)$ :
$f (x) = {a x + b x^{3} + x^{2} + 1 for x < 1 for x \geq 1$
If the function is differentiable everywhere, the value of $b$ must be ________. (rounded off to one decimal place)
Answer: -2.1 to -1.9
Solution
Answer: $- 2.0$ For differentiability at $x = 1$ , both the value and the derivative must match. Derivative of the right piece: $3 x^{2} + 2 x$ ; at $x = 1$ it is $3 + 2 = 5$ . The left piece has slope $a$ , so $a = 5$ . Continuity at $x = 1$ : left value $= a (1) + b = 5 + b$ ; right value $= 1 + 1 + 1 = 3$ . Setting them equal:
$5 + b = 3 \Rightarrow b = - 2.$
Question 32Engineering Mathematicsnat1 mark
A box contains 5 coins: 4 regular coins and 1 fake coin. When a regular coin is tossed, $P (head) = 0.5$ and for a fake coin $P (head) = 1$ . You pick a coin at random and toss it twice, and get two heads. The probability that the coin you have chosen is the fake coin is _______. (rounded off to two decimal places)
Answer: 0.49 to 0.51
Solution
Answer: $0.50$ Let $F$ = fake, $R$ = regular. $P (F) = \frac{1}{5}$ , $P (R) = \frac{4}{5}$ .
$P (H H ∣ F) = 1, P (H H ∣ R) = 0. 5^{2} = 0.25.$
By total probability:
$P (H H) = \frac{1}{5} (1) + \frac{4}{5} (0.25) = 0.2 + 0.2 = 0.4.$
By Bayes' theorem:
$P (F ∣ H H) = \frac{P ( H H ∣ F ) P ( F )}{P ( H H )} = \frac{0.2}{0.4} = 0.50.$
Question 33Algorithmsnat1 mark
The pseudocode of a function fun() is given below:
```
fun(int A[0..n-1]){
    for i=0 to n-2
        for j=0 to n-i-2
            if (A[j] > A[j+1])
                then swap A[j] and A[j+1]
}
```
Let $A [0 \dots 29]$ be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if fun() is called with $A [0 \dots 29]$ , is __________. (Answer in integer)
Answer: 435
Solution
Answer: 435 fun is bubble sort. For an array sorted in strictly descending order (the worst case), every compared adjacent pair is out of order, so each comparison causes a swap. The number of comparisons (and hence swaps) is
$(2 n) = \frac{n ( n - 1 )}{2} = \frac{30 \cdot 29}{2} = 435 .$
Question 34Programming & Data Structuresnat1 mark
Consider the C program:
```
#include <stdio.h>
void foo(int *p, int x){
    *p = x;
}
int main(){
    int *z;
    int a = 20, b = 25;
    z = &a;
    foo(z, b);
    printf("%d", a);
    return 0;
}
```
The output of the given C program is __________. (Answer in integer)
Answer: 25
Solution
Answer: 25 z points to a. The call foo(z, b) passes this pointer and the value b = 25. Inside foo, *p = x writes 25 through the pointer, i.e. into a. So a becomes 25, and printf("%d", a) prints $25$ .
Question 35Programming & Data Structuresnat1 mark
The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node. Suppose a Min-Heap $T$ stores 32 keys. The height of $T$ is _____________. (Answer in integer)
Answer: 5
Solution
Answer: 5 A heap is a complete binary tree, whose height (in edges) for $n$ nodes is $⌊ lo g_{2} n ⌋$ .
$⌊ lo g_{2} 32 ⌋ = ⌊ 5 ⌋ = 5.$
(Levels $0$ – $4$ hold $1 + 2 + 4 + 8 + 16 = 31$ nodes; the 32nd node sits on level $5$ , so the longest root-to-leaf path has 5 edges.)
Question 36Computer Organization & Architecturemcq2 marks
Consider a memory system with 1M bytes of main memory and 16K bytes of cache memory. Assume that the processor generates 20-bit memory address, and the cache block size is 16 bytes. If the cache uses direct mapping, how many bits will be required to store all the tag values? [Assume memory is byte addressable, $1 K = 2^{10}$ , $1 M = 2^{20}$ .]
- A.
  $6 \times 2^{10}$
  ✓
- B.
  $8 \times 2^{10}$
- C.
  $2^{12}$
- D.
  $2^{14}$
Answer: A
Solution
Answer: (A) $6 \times 2^{10}$ Address $= 20$ bits. Block size $= 16 = 2^{4}$ → offset $= 4$ bits. Number of cache lines $= \frac{16 K}{16} = 1 K = 2^{10}$ → index (line) $= 10$ bits. Tag $= 20 - 10 - 4 = 6$ bits per line. Total tag storage $= (tag bits) \times (number of lines) = 6 \times 2^{10}$ bits.
Question 37Computer Organization & Architecturemcq2 marks
A processor has 64 general-purpose registers and 50 distinct instruction types. An instruction is encoded in 32-bits. What is the maximum number of bits that can be used to store the immediate operand for the given instruction?
```
    ADD R1, #25     // R1 = R1 + 25
```
- A.
  16
- B.
  20
  ✓
- C.
  22
- D.
  24
Answer: B
Solution
Answer: (B) 20 Field sizes: - Opcode: 50 instruction types need $⌈ lo g_{2} 50 ⌉ = 6$ bits. - Register: 64 registers need $lo g_{2} 64 = 6$ bits (one register operand, R1). The instruction ADD R1, #imm uses one opcode + one register + the immediate. In 32 bits:
$immediate = 32 - 6 - 6 = 20 bits .$
Question 38Operating Systemsmcq2 marks
A computer has two processors, $M_{1}$ and $M_{2}$ . Four processes $P_{1}, P_{2}, P_{3}, P_{4}$ with CPU bursts of 20, 16, 25, and 10 ms, respectively, arrive at the same time and are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities: - $M_{1}$ : $P_{1} > P_{3} > P_{2} > P_{4}$ (so $P_{1}$ highest, $P_{4}$ lowest). - $M_{2}$ : $P_{2} > P_{3} > P_{4} > P_{1}$ (so $P_{2}$ highest, $P_{1}$ lowest). A process $P_{i}$ is scheduled on a free processor $M_{k}$ if no higher-priority process is waiting. A process can go to any free processor without violating priority rules. Ignore context-switch time. What is the average waiting time (ms)?
- A.
  9.00
  ✓
- B.
  8.75
- C.
  6.50
- D.
  7.50
Answer: A
Solution
Answer: (A) 9.00 At $t = 0$ both processors are free: - $M_{1}$ picks its highest-priority process $P_{1}$ (burst 20) → runs $[0, 20]$ . - $M_{2}$ picks its highest-priority process $P_{2}$ (burst 16) → runs $[0, 16]$ . At $t = 16$ , $M_{2}$ frees. Remaining $P_{3}, P_{4}$ ; by $M_{2}$ 's order $P_{3} > P_{4}$ , so $P_{3}$ (burst 25) → runs $[16, 41]$ . At $t = 20$ , $M_{1}$ frees. Only $P_{4}$ left → $P_{4}$ (burst 10) → runs $[20, 30]$ . Waiting times (start $-$ arrival): $P_{1} = 0, P_{2} = 0, P_{3} = 16, P_{4} = 20$ .
$Avg = \frac{0 + 0 + 16 + 20}{4} = \frac{36}{4} = 9.00 ms .$
Question 39Databasesmcq2 marks
Consider two relations describing $t e am s$ and $pl a y er s$ : - $t e am s (t i d, t nam e)$ - $pl a y er s (p i d, p nam e, t i d)$ Which ONE of the following tuple relational calculus queries returns the name of the players who play for the team having $t nam e$ as 'MI'?
- A.
  ${p . p nam e ∣ p \in pl a y er s \land \exists t (t \in t e am s \land p . t i d = t . t i d \land t . t nam e =^{'} M I^{'})}$
  ✓
- B.
  ${p . p nam e ∣ p \in t e am s \land \exists t (t \in pl a y er s \land p . t i d = t . t i d \land t . t nam e =^{'} M I^{'})}$
- C.
  ${p . p nam e ∣ p \in pl a y er s \land \exists t (t \in t e am s \land t . t nam e =^{'} M I^{'})}$
- D.
  ${p . p nam e ∣ p \in t e am s \land \exists t (t \in pl a y er s \land t . t nam e =^{'} M I^{'})}$
Answer: A
Solution
Answer: (A) We want player names, so $p$ must range over $pl a y er s$ (eliminating (B),(D)). We must link the player's team to a $t e am s$ tuple named 'MI', which requires the join condition $p . t i d = t . t i d$ and $t . t nam e =^{'} M I^{'}$ . Option (C) drops the join $p . t i d = t . t i d$ , so it would return every player's name as long as some 'MI' team exists — wrong. Only (A) correctly joins the player to the 'MI' team.
Question 40Computer Networksmcq2 marks
A packet with destination IP address 145.36.109.70 arrives at a router whose routing table is shown. Which interface will the packet be forwarded to?
```
Subnet Address | Subnet Mask (CIDR) | Interface
---------------+--------------------+----------
145.36.0.0     | /16                | E1
145.36.128.0   | /17                | E2
145.36.64.0    | /18                | E3
145.36.255.0   | /24                | E4
Default        | --                 | E5
```
- A.
  E3
  ✓
- B.
  E1
- C.
  E2
- D.
  E5
Answer: A
Solution
Answer: (A) E3 Routers use longest-prefix match. The third octet is $109 = 0110110 1_{2}$ . - /16 ( $145.36.0.0$ ): matches. - /17 ( $145.36.128.0$ ): needs third-octet top bit $= 1$ ( $\geq 128$ ); $109 < 128$ → no match. - /18 ( $145.36.64.0$ ): needs third-octet top two bits $= 01$ (range $64$ – $127$ ); $109$ is in $[64, 127]$ → match. - /24 ( $145.36.255.0$ ): third octet must be $255$ → no. The longest matching prefix is $/18$ → interface E3.
Question 41Engineering Mathematicsmcq2 marks
Let $A$ be the $2 \times 2$ matrix $A = [11 1 - 1]$ . What are the eigenvalues of the matrix $A^{13}$ ?
- A.
  $1, - 1$
- B.
  $22, - 22$
- C.
  $42, - 42$
- D.
  $642, - 642$
  ✓
Answer: D
Solution
Answer: (D) $642, - 642$ Eigenvalues of $A$ : $det (A - λ I) = (1 - λ) (- 1 - λ) - 1 = λ^{2} - 2 = 0 \Rightarrow λ = \pm 2$ . Eigenvalues of $A^{13}$ are $λ^{13}$ :
$(2)^{13} = 2^{6.5} = 2^{6} 2 = 642, (- 2)^{13} = - 642 .$
Question 42Digital Logicmcq2 marks
Consider the four-variable Boolean function in sum-of-products form
$F (b_{3}, b_{2}, b_{1}, b_{0}) = \sum (0, 2, 4, 8, 10, 11, 12),$
where $b_{3} b_{2} b_{1} b_{0}$ is read as a 4-bit binary number ( $b_{3}$ MSB). There are no don't-care terms. Which ONE of the following is the CORRECT minimized Boolean expression for $F$ ?
- A.
  $b ˉ_{1} b ˉ_{0} + b ˉ_{2} b ˉ_{0} + b_{1} b ˉ_{2} b_{3}$
  ✓
- B.
  $b ˉ_{1} b ˉ_{0} + b ˉ_{2} b ˉ_{0}$
- C.
  $b ˉ_{2} b ˉ_{0} + b_{1} b_{2} b_{3}$
- D.
  $b ˉ_{0} b ˉ_{2} + b ˉ_{3}$
Answer: A
Solution
Answer: (A) $b ˉ_{1} b ˉ_{0} + b ˉ_{2} b ˉ_{0} + b_{1} b ˉ_{2} b_{3}$ Plot minterms $0, 2, 4, 8, 10, 11, 12$ on a K-map: - $0, 2, 8, 10$ share $b_{1} = 0, b_{0} = 0$ → group $b ˉ_{1} b ˉ_{0}$ . - $0, 4, 8, 12$ share $b_{2} = 0, b_{0} = 0$ → group $b ˉ_{2} b ˉ_{0}$ . - Minterm $11 = 1011$ is covered only together with $10 = 1010$ : they share $b_{3} = 1, b_{2} = 0, b_{1} = 1$ → group $b_{1} b ˉ_{2} b_{3}$ . Covering all seven minterms minimally gives
$F = b ˉ_{1} b ˉ_{0} + b ˉ_{2} b ˉ_{0} + b_{1} b ˉ_{2} b_{3},$
which is option (A). The other options miss minterm $11$ or include extra minterms.
Question 43Algorithmsmcq2 marks
Let $G (V, E)$ be an undirected, unweighted graph with 100 vertices. Let $d (u, v)$ denote the number of edges in a shortest path between $u$ and $v$ . Suppose $max_{u \neq = v} d (u, v) = 30$ (the diameter). Let $T$ be any breadth-first-search tree of $G$ . Which ONE of the options is CORRECT for every such graph $G$ ?
- A.
  The height of $T$ is exactly 15.
- B.
  The height of $T$ is exactly 30.
- C.
  The height of $T$ is at least 15.
  ✓
- D.
  The height of $T$ is at least 30.
Answer: C
Solution
Answer: (C) The height of $T$ is at least 15. A BFS tree rooted at $r$ has height equal to the eccentricity of $r$ (the maximum distance from $r$ to any vertex). For any root $r$ and the diametral pair $u, v$ with $d (u, v) = 30$ :
$30 = d (u, v) \leq d (u, r) + d (r, v) \leq 2 \cdot ecc (r) .$
So $ecc (r) \geq 15$ , i.e. the BFS-tree height is at least 15 for every root. It can be exactly 15 (root at the center) or as large as 30 (root at a diametral endpoint), so "exactly 15/30" and "at least 30" are not guaranteed.
Question 44Theory of Computationmcq2 marks
Consider the following two languages over the alphabet ${a, b}$ :
$L_{1} = {α β α ∣ α \in {a, b}^{+} AND β \in {a, b}^{+}}$

$L_{2} = {α β α ∣ α \in {a}^{+} AND β \in {a, b}^{+}}$
Which ONE of the following statements is CORRECT?
- A.
  Both $L_{1}$ and $L_{2}$ are regular languages.
- B.
  $L_{1}$ is a regular language but $L_{2}$ is not a regular language.
- C.
  $L_{1}$ is not a regular language but $L_{2}$ is a regular language.
  ✓
- D.
  Neither $L_{1}$ nor $L_{2}$ is a regular language.
Answer: C
Solution
Answer: (C) $L_{1}$ is not regular but $L_{2}$ is regular. $L_{2}$ is regular. Since $α$ consists only of $a$ 's, we can always take $α = a$ (a single $a$ ) and let $β$ be the middle. So $L_{2}$ is exactly the set of strings that start with $a$ , end with $a$ , and have length $\geq 3$ — described by the regular expression $a (a + b)^{+} a$ . $L_{1}$ is not regular. Here $α$ may be any non-empty string, and the same $α$ must appear as both a prefix and a suffix. When the first and last symbols differ (e.g. $α = ab$ ), a single-symbol border no longer works, and the automaton would have to match an arbitrarily long prefix against the suffix — which a finite automaton cannot do (provable by the pumping lemma). Hence $L_{1}$ is not regular.
Question 45Theory of Computationmcq2 marks
Consider the following two languages over ${a, b, c}$ , where $m, n$ are natural numbers:
$L_{1} = {a^{m} b^{m} c^{m + n} ∣ m, n \geq 1}, L_{2} = {a^{m} b^{n} c^{m + n} ∣ m, n \geq 1} .$
Which ONE of the following statements is CORRECT?
- A.
  Both $L_{1}$ and $L_{2}$ are context-free languages.
- B.
  $L_{1}$ is a context-free language but $L_{2}$ is not a context-free language.
- C.
  $L_{1}$ is not a context-free language but $L_{2}$ is a context-free language.
  ✓
- D.
  Neither $L_{1}$ nor $L_{2}$ are context-free languages.
Answer: C
Solution
Answer: (C) $L_{1}$ is not context-free but $L_{2}$ is context-free. $L_{2}$ is context-free. We need $# c = # a + # b$ . A PDA (or grammar) pushes one symbol for each $a$ and each $b$ , then pops one for each $c$ :
```
S -> a S c | B
B -> b B c | b c
```
This generates $a^{m} b^{n} c^{m + n}$ . $L_{1}$ is not context-free. It requires $# a = # b = m$ and $# c = m + n > m$ , i.e. two independent comparisons tied to $m$ . A single stack can match $a$ 's with $b$ 's, but after that the count $m$ is lost and cannot be compared again with the $c$ 's. By the pumping lemma for CFLs (pump $a^{p} b^{p} c^{p + 1}$ ), $L_{1}$ fails to be context-free.
Question 46Compiler Designmsq2 marks
Which of the following statement(s) is/are TRUE while computing First and Follow during top-down parsing by a compiler?
- A.
  For a production $A \to ϵ$ , $ϵ$ will be added to $F i r s t (A)$ .
  ✓
- B.
  If there is any input right end marker, it will be added to $F i r s t (S)$ , where $S$ is the start symbol.
- C.
  For a production $A \to ϵ$ , $ϵ$ will be added to $F o l l o w (A)$ .
- D.
  If there is any input right end marker, it will be added to $F o l l o w (S)$ , where $S$ is the start symbol.
  ✓
Answer: A, D
Solution
Answer: (A) and (D) - (A) By definition, if $A \to ϵ$ then $ϵ \in F i r s t (A)$ . True. - (D) The end-of-input marker is always placed in $F o l l o w$ of the start symbol $S$ . True. - (B) The end-of-input marker goes into $F o l l o w (S)$ , never into any $F i r s t$ set. False. - (C) $ϵ$ is never added to any $F o l l o w$ set; $F o l l o w$ sets contain only terminals and the end-of-input marker. False.
Question 47Databasesmsq2 marks
Consider a relational schema $t e am (nam e, c i t y, o w n er)$ with functional dependencies ${nam e \to c i t y, nam e \to o w n er}$ . The relation $t e am$ is decomposed into $t_{1} (nam e, c i t y)$ and $t_{2} (nam e, o w n er)$ . Which of the following statement(s) is/are TRUE?
- A.
  The relation $t e am$ is NOT in BCNF.
- B.
  The relations $t_{1}$ and $t_{2}$ are in BCNF.
  ✓
- C.
  The decomposition constitutes a lossless join.
  ✓
- D.
  The relation $t e am$ is NOT in 3NF.
Answer: B, C
Solution
Answer: (B) and (C) The only determinant is $nam e$ , and $nam e$ is the (candidate) key of $t e am$ . Every FD has a superkey on its left, so $t e am$ is in BCNF (hence also in 3NF). Therefore (A) and (D) are false. - (B) Each decomposed relation has $nam e$ as its key with FDs $nam e \to c i t y$ and $nam e \to o w n er$ respectively — both in BCNF. True. - (C) The common attribute $nam e$ is a key of both $t_{1}$ and $t_{2}$ , so the decomposition is lossless. True.
Question 48Discrete Mathematicsmsq2 marks
Which of the following predicate logic formulae is/are CORRECT representation(s) of: "Everyone has exactly one mother"? Predicates: $m o t h er (y, x)$ means " $y$ is the mother of $x$ "; $n o t e q (x, y)$ means " $x$ and $y$ are not equal".
- A.
  $\forall x \exists y \exists z (m o t h er (y, x) \land \neg m o t h er (z, x))$
- B.
  $\forall x \exists y [m o t h er (y, x) \land \forall z (n o t e q (z, y) \to \neg m o t h er (z, x))]$
  ✓
- C.
  $\forall x \forall y [m o t h er (y, x) \to \exists z (m o t h er (z, x) \land \neg n o t e q (z, y))]$
- D.
  $\forall x \exists y [m o t h er (y, x) \land \neg\exists z (n o t e q (z, y) \land m o t h er (z, x))]$
  ✓
Answer: B, D
Solution
Answer: (B) and (D) "Exactly one mother" = there exists a mother, and no other individual is also a mother. - (B) $\exists y$ a mother $y$ , and every $z \neq = y$ is not a mother → existence + uniqueness. True. - (D) $\exists y$ a mother $y$ , and there is no $z \neq = y$ that is a mother → same meaning. True. - (A) merely says some $y$ is a mother and some $z$ is not a mother — does not enforce uniqueness. False. - (C) $z$ can be taken equal to $y$ (since $\neg n o t e q (z, y)$ means $z = y$ ), making it trivially true; it enforces neither existence nor uniqueness. False.
Question 49Discrete Mathematicsmsq2 marks
$A = {0, 1, 2, 3, \dots}$ is the set of non-negative integers. Let $F$ be the set of functions from $A$ to itself. For $f_{1}, f_{2} \in F$ , define $(f_{1} ⊙ f_{2}) (n) = f_{1} (n) + f_{2} (n)$ for every $n \in A$ . Which of the following is/are CORRECT about the structure $(F, ⊙)$ ?
- A.
  $(F, ⊙)$ is an Abelian group.
- B.
  $(F, ⊙)$ is an Abelian monoid.
  ✓
- C.
  $(F, ⊙)$ is a non-Abelian group.
- D.
  $(F, ⊙)$ is a non-Abelian monoid.
Answer: B
Solution
Answer: (B) an Abelian monoid The operation is pointwise addition of functions. - Closure & associativity: inherited from integer addition. ✓ - Identity: the zero function $z (n) = 0$ satisfies $f ⊙ z = f$ , and $z \in F$ . ✓ → it is a monoid. - Commutative: $f_{1} (n) + f_{2} (n) = f_{2} (n) + f_{1} (n)$ → Abelian. ✓ - Inverses: an inverse of $f$ would need $g (n) = - f (n)$ , but negative values are not in $A$ (non-negative integers). So only $f = 0$ has an inverse → not a group. Hence $(F, ⊙)$ is an Abelian monoid, but not a group.
Question 50Theory of Computationmsq2 marks
Consider the deterministic finite automaton (DFA) shown, over $Σ = {a, b}$ . Identify which of the following language(s) is/are accepted by the given DFA.
- A.
  The set of all strings containing an even number of $b$ 's.
- B.
  The set of all strings containing the pattern $bab$ .
- C.
  The set of all strings ending with the pattern $bab$ .
  ✓
- D.
  The set of all strings not containing the pattern $aba$ .
Answer: C
Solution
Answer: (C) The set of all strings ending with the pattern $bab$ . The DFA is the standard 4-state minimal automaton that tracks the longest suffix matching a prefix of $bab$ : $q_{0}$ (nothing) $b q_{1}$ ( $b$ ) $a q_{2}$ ( $ba$ ) $b q_{3}$ ( $bab$ , accepting); with $q_{2} a q_{0}$ , $q_{3} a q_{2}$ , $q_{3} b q_{1}$ , and the self-loops shown. The only accepting state $q_{3}$ is reached exactly after reading a suffix $bab$ . If another $b$ follows, $q_{3} b q_{1}$ leaves the accepting state — so e.g. " $babb$ " contains $bab$ but is rejected, ruling out (B). The DFA accepts precisely strings ending in $bab$ . (A) and (D) are easily refuted by the same automaton.
Question 51Operating Systemsnat2 marks
A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored using linked allocation. Each data block reserves 4 bytes to store the pointer to the next block; the last block's link is a NULL pointer (also 4 bytes). A file of 1M bytes is stored. Assume $1 K = 2^{10}$ , $1 M = 2^{20}$ . The amount of space in bytes wasted due to internal fragmentation is ______. (Answer in integer)
Answer: 65468
Solution
Answer: 65468 Each $64 K = 65536$ -byte block reserves $4$ bytes for the pointer, leaving $65536 - 4 = 65532$ bytes of data per block. File size $= 1 M = 1048576$ bytes. Blocks needed $= ⌈ 1048576/65532 ⌉ = ⌈ 16.0009 ⌉ = 17$ blocks. - First 16 blocks hold $16 \times 65532 = 1048512$ bytes. - Remaining file data $= 1048576 - 1048512 = 64$ bytes, placed in the 17th block. Internal fragmentation is the unused data area of the last block:
$65532 - 64 = 65468 bytes .$
Question 52Compiler Designnat2 marks
Refer to the given 3-address code sequence, split into basic blocks. The number of basic blocks is ________. (Answer in integer)
```
1001: i = 1
1002: j = 1
1003: t1 = 10*i
1004: t2 = t1+j
1005: t3 = 8*t2
1006: t4 = t3-88
1007: a[t4] = 0.0
1008: j = j+1
1009: if j <= 10 goto 1003
1010: i = i+1
1011: if i <= 10 goto 1002
1012: i = 1
1013: t5 = i-1
1014: t6 = 88*t5
1015: a[t6] = 1.0
1016: i = i+1
1017: if i <= 10 goto 1013
```
Answer: 6
Solution
Answer: 6 Leaders are: the first statement, any jump target, and any statement following a conditional/unconditional jump. - First statement: 1001. - Jump targets: 1003, 1002, 1013. - Statements right after a jump: 1010 (after 1009), 1012 (after 1011). Leaders $= {1001, 1002, 1003, 1010, 1012, 1013}$ . Each leader begins a basic block:
```
B1: 1001
B2: 1002
B3: 1003–1009
B4: 1010–1011
B5: 1012
B6: 1013–1017
```
That is 6 basic blocks.
Question 53Computer Organization & Architecturenat2 marks
A computer has a two-level cache (L1, L2) and main memory. On an access the processor checks L1, then L2, then main memory (data is always found there). From the figure: L1 hit rate $= 95%$ , access time $= 10$ ns; L2 hit rate $= 85%$ , access time (including L1 miss penalty) $= 20$ ns; main memory access time (including L1 and L2 miss penalty) $= 200$ ns. The average memory access time (ns) is ________. (rounded off to two decimal places)
Answer: 11.83 to 11.87
Solution
Answer: 11.85 Interpret each stated time as the total time to obtain data at that level (penalties already included):
$AMAT = 0.95 (10) + 0.05 [0.85 (20) + 0.15 (200)] .$

$= 9.5 + 0.05 [17 + 30] = 9.5 + 0.05 (47) = 9.5 + 2.35 = 11.85 ns .$

Question 54Operating Systemsnat2 marks

In optimal page replacement, all future references are known. A modification: the OS correctly predicts only the next 4 page references (including the current one) at the time of allocating a frame. A process accesses pages in order:

1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4.

With three frames initially empty, the number of page faults during execution is ________. (Answer in integer)

Answer: 6

Solution

Answer: 6 Three frames, evict the page whose next use within the 4-reference window is farthest (or not used in the window):

ref | frames after | fault? (eviction)
 1  | 1            | fault
 3  | 1 3          | fault
 2  | 1 3 2        | fault
 4  | 3 2 4        | fault  (window 4,2,3,1: 1 used farthest -> evict 1)
 2  | 3 2 4        | hit
 3  | 3 2 4        | hit
 1  | 2 4 1        | fault  (window 1,2,4,3: 3 farthest -> evict 3)
 2  | 2 4 1        | hit
 4  | 2 4 1        | hit
 3  | 4 1 3        | fault  (window 3,1,4: 2 not used -> evict 2)
 1  | 4 1 3        | hit
 4  | 4 1 3        | hit

Total page faults

= 6

Question 55Databasesnat2 marks

Consider the database tables (instances shown) and the SQL query. The value returned by the query is ______. (Answer in integer)

player                 coach            team                      members
pid pname    age       cid  cname       tid tname city    cid     pid tid
1   Jasprit  31        101  Ricky        10  MI    Mumbai 102       1  10
2   Atharva  24        102  Mark         20  DC    Delhi  101       2  30
3   Ishan    26        103  Trevor       30  PK    Mohali 103       3  10
4   Axar     30                                                     4  20

SELECT MIN(P.age)
FROM player P
WHERE P.pid IN (
    SELECT M.pid
    FROM team T, coach C, members M
    WHERE C.cname = 'Mark'
          AND T.cid = C.cid
          AND M.tid = T.tid
    )

Answer: 26

Solution

Answer: 26 - Coach 'Mark' has

c i d = 102

. - Team with

c i d = 102

is MI (

t i d = 10

). - Members of team

t i d = 10

p i d = 1

(Jasprit) and

p i d = 3

(Ishan). - Their ages: Jasprit

= 31

, Ishan

= 26

MIN(age) = min (31, 26) = 26 .

Question 56Computer Networksnat2 marks
A 5-bit message is transmitted through a noisy channel. The probability that a bit gets flipped is 0.01, independently for each bit. The probability that the message is delivered error-free is ______. (rounded off to three decimal places)
Answer: 0.949 to 0.952
Solution
Answer: 0.951 Error-free means all 5 bits are received correctly. Each bit is correct with probability $1 - 0.01 = 0.99$ , independently:
$P (error-free) = (0.99)^{5} = 0.95099 \dots \approx 0.951 .$
Question 57Computer Networksnat2 marks
A message of size 15000 bytes is transmitted from source to destination using IPv4 via two routers: Source → Router-1 (MTU $= 5000$ bytes) → Router-2 (MTU $= 3000$ bytes) → Destination. Each MTU includes the 20-byte IP header. The number of fragments delivered to the destination is ________. (Answer in integer)
Answer: 7
Solution
Answer: 7 IP header $= 20$ bytes; fragment data must be a multiple of 8. At Router-1 (MTU 5000): max data per fragment $= 5000 - 20 = 4980 \to$ round down to $4976$ (multiple of 8). $15000$ data bytes $\Rightarrow$ fragments of $4976, 4976, 4976, 72$ → 4 fragments. At Router-2 (MTU 3000): max data per fragment $= 3000 - 20 = 2980 \to 2976$ . - Each $4976$ -byte fragment is refragmented into $2976 + 2000$ → 2 fragments. Three of them give $3 \times 2 = 6$ . - The $72$ -byte fragment fits as is → 1 fragment. Total delivered $= 6 + 1 = 7$ fragments.
Question 58Engineering Mathematicsnat2 marks
Consider a probability distribution with density
$P (x) = {C x^{2} 0 1 \leq x \leq 4 otherwise$
The probability that $x$ lies between 2 and 3, i.e. $P (2 \leq x \leq 3)$ , is __________. (rounded off to three decimal places)
Answer: 0.3 to 0.302
Solution
Answer: 0.302 Normalize to find $C$ :
$\int_{1}^{4} C x^{2} d x = C \cdot \frac{x ^{3}}{3}_{1}^{4} = C \cdot \frac{64 - 1}{3} = 21 C = 1 \Rightarrow C = \frac{1}{21} .$
Then
$P (2 \leq x \leq 3) = \int_{2}^{3} \frac{x ^{2}}{21} d x = \frac{1}{21} \cdot \frac{27 - 8}{3} = \frac{19}{63} = 0.3016 \approx 0.302 .$

Question 59Digital Logicnat2 marks

Consider a finite state machine (FSM) with one input

X

and one output

f

, given by the state transition table. The minimum number of states required to realize this FSM is ________. (Answer in integer)

Present | Next (X=0) | Next (X=1) | f(X=0) | f(X=1)
--------+------------+------------+--------+-------
  A     |     F      |     B      |   0    |   0
  B     |     D      |     C      |   0    |   0
  C     |     F      |     E      |   0    |   0
  D     |     G      |     A      |   1    |   0
  E     |     D      |     C      |   0    |   0
  F     |     F      |     B      |   1    |   1
  G     |     G      |     H      |   0    |   1
  H     |     G      |     A      |   1    |   0

Answer: 5

Solution

Answer: 5 Minimize by partition refinement (group states that are indistinguishable). Initial grouping by output

(f_{0}, f_{1})

{A, B, C, E}

(0,0),

{D, H}

(1,0),

{F}

(1,1),

{G}

(0,1). Refine

{A, B, C, E}

by where their transitions lead:

A, C

go to

({F}, {A, B, C, E})

while

B, E

go to

({D, H}, {A, B, C, E})

→ split into

{A, C}

and

{B, E}

{D, H}

stay together (both:

0 \to G

1 \to A

). Final partition:

{A, C}, {B, E}, {D, H}, {F}, {G}

— and it is stable. So the minimized machine has

5

states.

Question 60Digital Logicnat2 marks
Consider the given sequential circuit designed using D flip-flops. The circuit is initialized with some value (initial state). The number of distinct states the circuit will go through before returning back to the initial state is _________. (Answer in integer)
Answer: 7 to 8
Solution
Answer: 8 The outputs are connected as a shift register $Q_{0} \to D_{1}, Q_{1} \to D_{2}, Q_{2} \to D_{3}$ , and the complemented last output feeds back to the first: $Q_{3} \to D_{0}$ . This is a 4-bit Johnson (twisted-ring) counter. Starting from $0000$ the state sequence is:
```
0000 -> 1000 -> 1100 -> 1110 -> 1111 -> 0111 -> 0011 -> 0001 -> (0000)
```
which visits $8$ distinct states ( $2 n$ for $n = 4$ flip-flops) before repeating.
Question 61Programming & Data Structuresnat2 marks
Consider the C program:
```
#include <stdio.h>
int foo(int S[], int size){
    if(size == 0) return 0;
    if(size == 1) return 1;
    if(S[0] != S[1]) return 1 + foo(S+1, size-1);
    return foo(S+1, size-1);
}
int main(){
    int A[] = {0,1,2,2,2,0,0,1,1};
    printf("%d", foo(A,9));
    return 0;
}
```
The value printed by the given C program is _______. (Answer in integer)
Answer: 5
Solution
Answer: 5 foo scans adjacent pairs, adding 1 whenever S[0] != S[1], and adds a final 1 at the size==1 base case. This counts the number of maximal runs of equal consecutive elements (i.e. $1 + # {i : A [i] \neq = A [i + 1]}$ ). For $A = {0, 1, 2, 2, 2, 0, 0, 1, 1}$ the runs are:
$0 ∣ 1 ∣ 2, 2, 2 ∣ 0, 0 ∣ 1, 1$
There are $4$ adjacent-difference positions, plus the base $1$ : $4 + 1 = 5$ .

Question 62Programming & Data Structuresnat2 marks

Two linked lists are given (contents shown). L1 has 9 nodes, L2 has 7 nodes:

L1: 1 -> 7 -> 12 -> 3 -> 9 -> 5 -> 11 -> 15 -> 8 -> NULL
L2: 1 -> 11 -> 6 -> 9 -> 15 -> 12 -> 4 -> NULL

The code below modifies L1. The number of nodes in L1 after execution is ________. (Answer in integer)

int find (int query, LIST *list) {
    while (list != NULL){
        if(list->data == query) return 1;
        list = list->next;
    }
    return 0;
}
int main () {
    ptr1 = L1; ptr2 = L2;
    while (ptr1->next != NULL){
        query = ptr1->next->data;
        if (find (query, L2))
            ptr1->next = ptr1->next->next;   // unlink
        else ptr1 = ptr1->next;
    }
    return 0;
}

Answer: 5

Solution

Answer: 5 The loop walks L1 and deletes every node (after the head) whose value also appears in L2. The head node (value 1) is never examined for deletion (the loop looks at ptr1->next). L2 as a set

= {1, 11, 6, 9, 15, 12, 4}

. Checking L1's non-head nodes:

7  -> keep     12 -> remove   3  -> keep
9  -> remove   5  -> keep     11 -> remove
15 -> remove   8  -> keep

Removed:

12, 9, 11, 15

→ 4 nodes deleted. Remaining L1

= 1, 7, 3, 5, 8

9 - 4 = 5 nodes .

Question 63Programming & Data Structuresnat2 marks

Consider the C program:

#include <stdio.h>
int gate (int n) {
    int d, t, newnum, turn;
    newnum = turn = 0; t = 1;
    while (n >= t) t *= 10;
    t /= 10;
    while (t > 0) {
        d = n/t;
        n = n%t;
        t /= 10;
        if (turn) newnum = 10*newnum + d;
        turn = (turn + 1) % 2;
    }
    return newnum;
}
int main () { printf ("%d", gate(14362)); return 0; }

The value printed by the given C program is _______. (Answer in integer)

Answer: 46

Solution

Answer: 46 The function reads digits of

n

from most significant to least, and keeps a digit only on alternate turns, starting by skipping the first (

t u r n

begins at 0, so digit 1 is skipped, digit 2 kept, ...). Digits of

14362

1, 4, 3, 6, 2

turn=0: d=1  skipped          turn->1
turn=1: d=4  newnum = 4       turn->0
turn=0: d=3  skipped          turn->1
turn=1: d=6  newnum = 46      turn->0
turn=0: d=2  skipped

So it keeps the 2nd and 4th digits →

46

Question 64Algorithmsnat2 marks
The maximum value of $x$ such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is _________. (answer in integer)
Answer: 5
Solution
Answer: 5 Edge weights: $A B = 7, A D = 6, D C = 8, B C = x$ , and the diagonals $A C$ and $B D$ are $1$ and $3$ . An edge $e$ is in every MST iff, in every cycle containing $e$ , some other edge is strictly heavier than $e$ (cut/cycle property). The binding cycle through $B C$ is $B - C - A - D - B$ , whose other edges are $C A, A D = 6, D B$ with maximum weight $A D = 6$ . For $B C$ to be forced into every MST we need $x < 6$ , i.e. $x \leq 5$ . Check $x = 5$ : after adding the two light diagonals ( $1$ and $3$ ) the two components ${A, C}$ and ${B, D}$ must be joined by the cheapest crossing edge; the crossing edges are $A B = 7, A D = 6, B C = 5, D C = 8$ , and $B C = 5$ is the unique minimum → $B C$ is in every MST. At $x = 6$ , $B C$ ties with $A D$ and is no longer forced. Hence $x_{m a x} = 5$ .
Question 65Programming & Data Structuresnat2 marks
In a double hashing scheme, $h_{1} (k) = k mod 11$ and $h_{2} (k) = 1 + (k mod 7)$ are the auxiliary hash functions. The table size $m = 11$ . The $i$ -th probe uses $[h_{1} (k) + i h_{2} (k)] mod m$ . The keys are inserted in order: $63, 50, 25, 79, 67, 24$ . The slot at which key 24 gets stored is ___________. (Answer in integer)
Answer: 10 to 11
Solution
Answer: 10 Insert each key (slots $0$ – $10$ ):
```
63: h1 = 63 mod 11 = 8        -> slot 8
50: h1 = 50 mod 11 = 6        -> slot 6
25: h1 = 25 mod 11 = 3        -> slot 3
79: h1 = 79 mod 11 = 2        -> slot 2
67: h1 = 67 mod 11 = 1        -> slot 1
```
For key 24: $h_{1} = 24 mod 11 = 2$ (occupied by 79), $h_{2} = 1 + (24 mod 7) = 1 + 3 = 4$ . - $i = 1 : (2 + 4) mod 11 = 6$ (occupied by 50). - $i = 2 : (2 + 8) mod 11 = 10$ (empty) → slot 10. Key 24 is stored at slot $10$ .

Practice the full paper with a timer

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

Create free account →