GATE CS 2024 Set 1

65 questions · Previous year paper

The GATE 2024 Computer Science and Information Technology paper, Set 1: 65 questions for 100 marks in 180 minutes, with General Aptitude (15 marks) and the technical section (85 marks). Answers follow the official final answer key; every question has a short explanation.

Take it as a timed test: ₹99

Computer Science and Information Technology

Question 61

NAT · 2 marks

Consider the following two regular expressions over the alphabet \(\{0,1\}\):

\[r = 0^{*} + 1^{*}\]

\[s = 01^{*} + 10^{*}\]

The total number of strings of length less than or equal to 5, which are neither in \(r\) nor in \(s\), is _________

Explanation

Answer: 44

There are \(1 + 2 + 4 + 8 + 16 + 32 = 63\) binary strings of length 0 to 5, counting the empty string.

  • \(r = 0^{*} + 1^{*}\): the empty string, plus the all-0 and the all-1 string of each length 1 to 5: \(1 + 5 \times 2 = 11\) strings.
  • \(s = 01^{*} + 10^{*}\): one string \(01\cdots1\) and one string \(10\cdots0\) of each length 1 to 5: 10 strings.
  • The strings 0 and 1 belong to both languages.

So \(11 + 10 - 2 = 19\) strings are in \(r\) or \(s\), and \(63 - 19 = 44\) are in neither. Forgetting to remove the two shared strings gives 42.

Answer: 44

Question 62

NAT · 2 marks

Consider a memory management system that uses a page size of 2 KB. Assume that both the physical and virtual addresses start from 0. Assume that the pages 0, 1, 2, and 3 are stored in the page frames 1, 3, 2, and 0, respectively. The physical address (in decimal format) corresponding to the virtual address 2500 (in decimal format) is _________

Explanation

Answer: 6596

A page holds \(2\ \text{KB} = 2048\) bytes, so split the virtual address into a page number and an offset:

  • page number \(= \lfloor 2500 / 2048 \rfloor = 1\);
  • offset \(= 2500 - 2048 = 452\).

Page 1 is stored in frame 3 (the second pair in the list), and the offset carries over unchanged:

\[3 \times 2048 + 452 = 6144 + 452 = 6596\]

Answer: 6596

Question 63

NAT · 2 marks

A bag contains 10 red balls and 15 blue balls. Two balls are drawn randomly without replacement. Given that the first ball drawn is red, the probability (rounded off to 3 decimal places) that both balls drawn are red is _________

Explanation

Answer: 0.37 to 0.38

Let \(R_{1}\) and \(R_{2}\) be the events that the first and the second ball are red. Then

\[P(R_{1} \cap R_{2} \mid R_{1}) = \frac{P(R_{1} \cap R_{2})}{P(R_{1})} = \frac{\frac{10}{25} \times \frac{9}{24}}{\frac{10}{25}} = \frac{9}{24} = 0.375\]

In words: once a red ball is out, the bag holds 9 red and 15 blue balls, so the second ball is red with probability \(9/24\). The unconditional probability of two reds, \(\frac{10}{25} \times \frac{9}{24} = 0.15\), answers a different question.

Answer: 0.375

Question 64

NAT · 2 marks

Consider a digital logic circuit consisting of three 2-to-1 multiplexers M1, M2, and M3 as shown below. X1 and X2 are inputs of M1. X3 and X4 are inputs of M2. A, B, and C are select lines of M1, M2, and M3, respectively.

Three 2-to-1 multiplexers. M1 takes X1 on input 0 and X2 on input 1, with select S1 driven by A and output Q1; M2 takes X3 on input 0 and X4 on input 1, with select S2 driven by B and output Q2; Q1 feeds input 0 and Q2 feeds input 1 of M3, whose select S3 is driven by C and whose output is Y.

For an instance of inputs X1=1, X2=1, X3=0, and X4=0, the number of combinations of A, B, C that give the output Y=1 is _________

Explanation

Answer: 4

A 2-to-1 multiplexer passes its input 0 when the select line is 0 and its input 1 when the select line is 1.

  • M1 chooses between X1 = 1 and X2 = 1, so Q1 = 1 whatever A is.
  • M2 chooses between X3 = 0 and X4 = 0, so Q2 = 0 whatever B is.
  • M3 passes Q1 when C = 0 and Q2 when C = 1, so \(Y = \overline{C}\).

Y = 1 exactly when C = 0, while A and B can take any values: \(2 \times 2 = 4\) of the 8 combinations.

Answer: 4

Question 65

NAT · 2 marks

Consider sending an IP datagram of size 1420 bytes (including 20 bytes of IP header) from a sender to a receiver over a path of two links with a router between them. The first link (sender to router) has an MTU (Maximum Transmission Unit) size of 542 bytes, while the second link (router to receiver) has an MTU size of 360 bytes. The number of fragments that would be delivered at the receiver is ________

Explanation

Answer: 6

The datagram carries \(1420 - 20 = 1400\) bytes of data. Every fragment has its own 20-byte header, and every fragment except the last must carry a multiple of 8 data bytes.

  • First link (MTU 542): at most \(542 - 20 = 522\) data bytes, rounded down to 520. The data splits as \(520 + 520 + 360\), giving fragments of 540, 540 and 380 bytes.
  • Second link (MTU 360): at most \(360 - 20 = 340\) data bytes, rounded down to 336. Each 520-byte piece splits into \(336 + 184\), and the 360-byte piece into \(336 + 24\).

Routers do not reassemble fragments, so the receiver gets \(2 + 2 + 2 = 6\) fragments.

Answer: 6

Questions 61 to 65 of 65