Free GATE CSE mock test — 65 questions, GATE marking 🇮🇳

8 original practice questions written by Myndaq in the GATE CS style. They are not taken from this mock paper or from official past papers. Try each one, then open the answer.

1. Question 1General AptitudeOne correct answer

   An empty tank is filled by inlet pipe P alone in 9 hours and is emptied by drain Q alone in 12 hours. Starting with the tank empty, P and Q are opened together. After t hours Q is closed, and the tank becomes exactly full 3 hours after Q is closed. What is t?

   1. A. 18 hours
   2. B. 21 hours
   3. C. 24 hours
   4. D. 27 hours
   Show answer and explanation

   Answer: C

   Work with fractions of the tank per hour. P fills 1/9 per hour and Q empties 1/12 per hour, so with both open the net rate is 1/9 - 1/12 = (4 - 3)/36 = 1/36 per hour. In the first phase the tank gains t/36. In the second phase P runs alone for 3 hours and adds 3 x 1/9 = 1/3 = 12/36. The tank is then exactly full, so t/36 + 12/36 = 1, giving t = 24 hours.

   Check: in 24 hours the net inflow is 24/36 = 2/3 of the tank, and the last 3 hours of P alone add the remaining 1/3. The distractors come from common slips: 27 is the total elapsed time t + 3 rather than t itself; 21 subtracts the three-hour second phase from t a second time; 18 is simply short, leaving the tank at 18/36 + 12/36 = 5/6 full when P is closed.

2. Question 2Engineering MathematicsType a numeric answer

   Let A be the 2 x 2 real matrix with first row (4, -2) and second row (1, 1). The larger eigenvalue of the matrix A³ - 6A² + 13A is ______.

   Show answer and explanation

   Answer: 12

   First find the eigenvalues of A. Trace(A) = 4 + 1 = 5 and det(A) = (4)(1) - (-2)(1) = 4 + 2 = 6, so the characteristic equation is λ² - 5λ + 6 = 0, i.e. (λ - 2)(λ - 3) = 0. Hence the eigenvalues of A are 2 and 3, and A is diagonalisable since the eigenvalues are distinct.

   For any polynomial f, the eigenvalues of f(A) are f(λ) evaluated at the eigenvalues of A (spectral mapping). Here f(λ) = λ³ - 6λ² + 13λ. f(2) = 8 - 24 + 26 = 10. f(3) = 27 - 54 + 39 = 12. So the eigenvalues of A³ - 6A² + 13A are 10 and 12, and the larger one is 12.

   A frequent error is to apply the polynomial to the trace or determinant rather than to each eigenvalue separately, which would give an unrelated number.

3. Question 3Digital LogicOne correct answer

   A Boolean function f of four variables A, B, C, D (A is the most significant variable) is given by the sum of minterms f = Σm(1, 3, 5, 7, 9, 13). Which of the following is a minimal sum-of-products expression for f?

   1. A. A'D + C'D
   2. B. A'D + AC'D
   3. C. A'B'D + BC'D
   4. D. A'D + C'D'
   Show answer and explanation

   Answer: A

   Write the minterms in ABCD order: 1 = 0001, 3 = 0011, 5 = 0101, 7 = 0111, 9 = 1001, 13 = 1101. Every minterm has D = 1, so D is a factor of every product term.

   The four minterms 1, 3, 5, 7 are exactly the cells with A = 0 and D = 1 (B and C free), giving the four-cell group A'D. The four minterms 1, 5, 9, 13 are exactly the cells with C = 0 and D = 1 (A and B free), giving the four-cell group C'D. Their union is {1, 3, 5, 7} ∪ {1, 5, 9, 13} = {1, 3, 5, 7, 9, 13}, which is f, so A'D + C'D covers f and adds nothing extra. Both groups are prime implicants and each is essential (7 is covered only by A'D, 9 only by C'D), so no single-term or smaller cover exists and A'D + C'D with 4 literals is minimal.

   Option B denotes the same function but uses AC'D in place of C'D, so it has 5 literals and is not minimal. Option C covers only {1, 3} ∪ {5, 13} = {1, 3, 5, 13}, missing minterms 7 and 9, so it is a different function. Option D contains C'D', which is 1 only when D = 0, so it wrongly covers minterms 0, 4, 8, 12 and is also a different function.

4. Question 4Computer Organization and ArchitectureType a numeric answer

   A processor has a two-level cache hierarchy. The L1 cache has an access time of 1 ns and a miss rate of 8 percent. Every L1 miss goes to L2, which has an access time of 9 ns and a local miss rate of 25 percent. Every L2 miss goes to main memory, which takes 100 ns to supply the block. Access times are not overlapped: an L1 miss pays the L1 time plus the L2 time, and an L2 miss additionally pays the memory time. Each instruction performs exactly one instruction fetch, and 30 percent of instructions perform exactly one additional data access. The average total memory access time per instruction, in nanoseconds, is ______.

   Show answer and explanation

   Answer: 4.83 to 4.84

   Step 1: average memory access time for one reference. AMAT = L1 access + (L1 miss rate) x [L2 access + (L2 local miss rate) x (memory time)] AMAT = 1 + 0.08 x [9 + 0.25 x 100] AMAT = 1 + 0.08 x [9 + 25] = 1 + 0.08 x 34 = 1 + 2.72 = 3.72 ns.

   Step 2: references per instruction. Every instruction makes 1 fetch, and 0.30 of instructions make 1 data access, so the average is 1 + 0.30 = 1.3 memory references per instruction.

   Step 3: per-instruction memory time = 1.3 x 3.72 = 4.836 ns, which rounds to 4.84 ns.

   Two slips are common here. Using the L2 local miss rate as a global miss rate (0.25 of all references reaching memory instead of 0.25 of L1 misses) inflates the answer badly. Forgetting the 1.3 references per instruction and reporting 3.72 answers a different question, namely the time per reference rather than per instruction.

5. Question 5AlgorithmsOne correct answer

   Consider the weighted undirected graph on vertices P, Q, R, S, T with exactly the following seven edges and weights:

   P-Q: 4, P-R: 2, Q-R: 5, Q-S: 10, R-S: 3, R-T: 8, S-T: 6.

   Let x be the total weight of a minimum spanning tree of this graph and let y be the length of a shortest path from Q to T. The pair (x, y) is

   1. A. (15, 13)
   2. B. (15, 14)
   3. C. (16, 13)
   4. D. (16, 14)
   Show answer and explanation

   Answer: A

   Minimum spanning tree by Kruskal. Sort the edges: P-R 2, R-S 3, P-Q 4, Q-R 5, S-T 6, R-T 8, Q-S 10. Accept P-R (2). Accept R-S (3). Accept P-Q (4), which brings in Q. Reject Q-R (5) because Q and R are already connected. Accept S-T (6), which brings in T. Four edges now span all five vertices, so x = 2 + 3 + 4 + 6 = 15. All weights are distinct, so this tree is the unique minimum spanning tree. A tempting wrong choice is to take Q-R (5) instead of P-Q (4) to attach Q, which gives 16.

   Shortest path from Q by Dijkstra. Initially P = 4, R = 5, S = 10, T = infinity. Settle P at 4; relaxing P-R gives 4 + 2 = 6, which does not improve R = 5. Settle R at 5; relaxing R-S gives 5 + 3 = 8, improving S to 8, and relaxing R-T gives 5 + 8 = 13, setting T = 13. Settle S at 8; relaxing S-T gives 8 + 6 = 14, which does not improve T = 13. Settle T at 13, so y = 13. The value 14 is the length of the route Q-R-S-T, which looks attractive because those edges are light individually but is one unit worse than Q-R-T.

   Note also that the minimum spanning tree does not preserve shortest paths: the tree path from Q to T is Q-P-R-S-T of weight 4 + 2 + 3 + 6 = 15, which is longer than 13.

6. Question 6Theory of ComputationOne correct answer

   Let L be the language over the alphabet {a, b} consisting of exactly those strings in which the number of occurrences of a is divisible by 3 and whose last symbol is b. The number of states in the minimal deterministic finite automaton accepting L is

   1. A. 3
   2. B. 4
   3. C. 6
   4. D. 7
   Show answer and explanation

   Answer: B

   Construction of a 4-state DFA. Track the count of a modulo 3, and, only while that count is 0, whether the last symbol read was b. Name the states A (count 0, last symbol is not b, including the empty string), B (count 0, last symbol is b), C (count 1), D (count 2). Transitions: A on a goes to C and on b goes to B; B on a goes to C and on b stays at B; C on a goes to D and on b stays at C; D on a goes to A and on b stays at D. B is the only accepting state, and the start state is A. When the count is 1 or 2 the string cannot be accepted whatever the last symbol is, so no extra bookkeeping is needed there, which is why C and D are single states.

   Lower bound of 4. Take the four strings ε, b, a, aa and show they are pairwise inequivalent under Myhill-Nerode by exhibiting a distinguishing suffix for each pair. ε versus b: suffix ε. The string b has zero occurrences of a and ends in b, so b is in L, while ε does not end in b and is not in L. ε versus a, and ε versus aa: suffix b. Then b is in L, whereas ab has one a and aab has two a, so neither is in L. b versus a, and b versus aa: suffix ε. Then b is in L while a and aa are not. a versus aa: suffix aab. Then a followed by aab is aaab, which has three a and ends in b, so it is in L; aa followed by aab is aaaab, which has four a and is not in L. Four pairwise distinguishable strings force at least four Myhill-Nerode classes, hence at least four states. Since a 4-state DFA exists, 4 is exactly minimal.

   The distractors correspond to real mistakes: 3 counts a modulo 3 only and forgets the requirement that the last symbol is b; 7 is the size of the unminimised product automaton that pairs the residue 0, 1, 2 with last symbol none, a or b; 6 is that product after only the obvious merge of the start state with the count-0 state whose last symbol is a.

7. Question 7Compiler DesignOne or more correct answers

   Consider the context-free grammar G over the terminal alphabet {p, q, r} with start symbol S and exactly the following productions:

   S → S p S S → q S → r

   Which of the following statements about G are TRUE?

   1. A. G is ambiguous.
   2. B. The language generated by G is regular.
   3. C. G is an LR(1) grammar.
   4. D. Every string in the language generated by G has an odd number of symbols.
   5. E. The language generated by G contains a string in which two occurrences of p are adjacent.
   Show answer and explanation

   Answer: A, B, D

   A is true. The string q p r p q has two distinct parse trees: one in which the upper S p S splits the string as (q) p (r p q), and one in which it splits as (q p r) p (q). Two parse trees for one string means G is ambiguous.

   B is true. Unfolding the productions shows that every sentential form eventually becomes an alternating sequence that starts and ends with q or r and has a single p between consecutive ones. So the language is exactly (q + r) (p (q + r))*, which is described by a regular expression and is therefore regular. Note that the grammar being ambiguous says nothing about the language being non-regular; ambiguity is a property of the grammar, not of the language.

   C is false. Every LR(k) grammar is unambiguous, because an LR parser constructs one rightmost derivation deterministically. Since G is ambiguous by statement A, G cannot be LR(1) for any lookahead. A parser generator would report shift-reduce conflicts on p here, arising from the unspecified associativity of p.

   D is true. Every string in the language has the shape x1 p x2 p ... p xn with each xi in {q, r} and n at least 1, so its length is n + (n - 1) = 2n - 1, which is odd.

   E is false. In the regular expression (q + r) (p (q + r))*, every p is immediately followed by a q or an r, so no two occurrences of p can ever be adjacent. The substring p p is not derivable.

8. Question 8Operating SystemOne correct answer

   Four processes arrive at a single-processor system with the following arrival times and CPU burst times, all in milliseconds:

   J1: arrival 0, burst 6 J2: arrival 1, burst 3 J3: arrival 3, burst 5 J4: arrival 7, burst 2

   The scheduler is preemptive shortest-remaining-time-first. A newly arrived process preempts the running process only if its burst is strictly smaller than the remaining time of the running process. Ties among ready processes are broken in favour of the earlier arrival. Context-switch overhead is zero.

   The average waiting time of the four processes is

   1. A. 3.25 ms
   2. B. 3.75 ms
   3. C. 4.50 ms
   4. D. 7.25 ms
   Show answer and explanation

   Answer: A

   Simulate the schedule. At time 0 only J1 is ready, so J1 runs. At time 1 J2 arrives with burst 3, while J1 has 5 ms remaining; 3 is strictly less than 5, so J2 preempts and runs. At time 3 J3 arrives with burst 5, but J2 has only 1 ms left, so J2 keeps the processor and finishes at time 4. At time 4 the ready set is J1 with 5 ms remaining and J3 with 5 ms remaining; the tie goes to the earlier arrival, so J1 runs. At time 7 J4 arrives with burst 2 and J1 has 6 - 1 - 3 = 2 ms remaining; 2 is not strictly less than 2, so there is no preemption and J1 runs to completion at time 9. At time 9 the ready set is J3 with 5 ms and J4 with 2 ms, so J4 runs from 9 to 11. Finally J3 runs from 11 to 16.

   Completion times: J1 = 9, J2 = 4, J3 = 16, J4 = 11. Turnaround = completion minus arrival: J1 = 9, J2 = 3, J3 = 13, J4 = 4. Waiting = turnaround minus burst: J1 = 9 - 6 = 3, J2 = 3 - 3 = 0, J3 = 13 - 5 = 8, J4 = 4 - 2 = 2. Average waiting time = (3 + 0 + 8 + 2) / 4 = 13 / 4 = 3.25 ms.

   The distractors are the answers to neighbouring questions. 3.75 ms is the average waiting time under non-preemptive shortest-job-first, where J1 runs uninterrupted from 0 to 6. 4.50 ms is the average waiting time under first-come-first-served. 7.25 ms is the average turnaround time of this same preemptive schedule, that is (9 + 3 + 13 + 4) / 4, obtained by forgetting to subtract the bursts.