GATE CS 2021 Set 1 mock test

Question 1 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

The ratio of boys to girls in a class is 7 to 3.

Among the options below, an acceptable value for the total number of students in the class is:

A

21

B

37

C

50

D

73

Question 2 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

A polygon is convex if, for every pair of points, $P$ and $Q$ belonging to the polygon, the line segment $PQ$ lies completely inside or on the polygon.

Which one of the following is NOT a convex polygon?

A

Concave chevron arrow-shaped polygon with an indented left vertex.

B

C

D

Question 3 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

Consider the following sentences:

(i) Everybody in the class is prepared for the exam.
(ii) Babu invited Danish to his home because he enjoys playing chess.

Which of the following is the CORRECT observation about the above two sentences?

A

(i) is grammatically correct and (ii) is unambiguous

B

(i) is grammatically incorrect and (ii) is unambiguous

C

(i) is grammatically correct and (ii) is ambiguous

D

(i) is grammatically incorrect and (ii) is ambiguous

Question 4 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

A circular sheet of paper is folded along the lines in the directions shown. The paper, after being punched in the final folded state as shown and unfolded in the reverse order of folding, will look like

Diagram showing a circular sheet of paper folded vertically, then horizontally, and cut with three punch holes.

A

Unfolded circular sheet with a central circular hole, long horizontal slots at top and bottom, and short vertical slots at left and right.

B

Unfolded circular sheet with a central circular hole, long horizontal slots at top and bottom, and short horizontal slots at left and right.

C

Unfolded circular sheet with a central circular hole, short horizontal slots at top and bottom, and long vertical slots at left and right.

D

Unfolded circular sheet with a central circular hole, short vertical slots at top and bottom, and long vertical slots at left and right.

Question 5 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

__________ is to surgery as writer is to __________

Which one of the following options maintains a similar logical relation in the above sentence?

A

Plan, outline

B

Hospital, library

C

Doctor, book

D

Medicine, grammar

Question 6 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

We have 2 rectangular sheets of paper, $M$ and $N$ , of dimensions $6\text{ cm} \times 1\text{ cm}$ each. Sheet $M$ is rolled to form an open cylinder by bringing the short edges of the sheet together. Sheet $N$ is cut into equal square patches and assembled to form the largest possible closed cube. Assuming the ends of the cylinder are closed, the ratio of the volume of the cylinder to that of the cube is

A

$\frac{\pi}{2}$

B

$\frac{3}{\pi}$

C

$\frac{9}{\pi}$

D

$3\pi$

Question 7 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Prices and profit details of items P and Q
Items	Cost (₹)	Profit %	Marked Price (₹)
P	5,400	---	5,860
Q	---	25	10,000

Details of prices of two items P and Q are presented in the above table. The ratio of cost of item P to cost of item Q is $3:4$ . Discount is calculated as the difference between the marked price and the selling price. The profit percentage is calculated as the ratio of the difference between selling price and cost, to the cost $\left(\text{Profit}\% = \frac{\text{Selling price} - \text{Cost}}{\text{Cost}} \times 100\right)$ .

The discount on item Q, as a percentage of its marked price, is

A

25

B

12.5

C

10

D

5

Question 8 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

There are five bags each containing identical sets of ten distinct chocolates. One chocolate is picked from each bag.

The probability that at least two chocolates are identical is

A

0.3024

B

0.4235

C

0.6976

D

0.8125

Question 9 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Given below are two statements 1 and 2, and two conclusions I and II.

Statement 1: All bacteria are microorganisms.
Statement 2: All pathogens are microorganisms.

Conclusion I: Some pathogens are bacteria.
Conclusion II: All pathogens are not bacteria.

Based on the above statements and conclusions, which one of the following options is logically CORRECT?

A

Only conclusion I is correct

B

Only conclusion II is correct

C

Either conclusion I or II is correct.

D

Neither conclusion I nor II is correct.

Question 10 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Some people suggest anti-obesity measures (AOM) such as displaying calorie information in restaurant menus. Such measures sidestep addressing the core problems that cause obesity: poverty and income inequality.

Which one of the following statements summarizes the passage?

A

The proposed AOM addresses the core problems that cause obesity.

B

If obesity reduces, poverty will naturally reduce, since obesity causes poverty.

C

AOM are addressing the core problems and are likely to succeed.

D

AOM are addressing the problem superficially.

Question 11 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is NOT necessarily context-free?

A

$L_1 \cap L_2$

B

$L_2 - L_1$

C

$L_1 - L_2$

D

$L_1 \cup L_2$

Question 12 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

Let $P$ be an array containing $n$ integers. Let $t$ be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of $n$ elements. Which one of the following choices is correct?

A

$t > 2n - 2$

B

$t > 3\lceil \frac{n}{2} \rceil$ and $t \le 2n - 2$

C

$t > n$ and $t \le 3\lceil \frac{n}{2} \rceil$

D

$t > \lceil \log_2(n) \rceil$ and $t \le n$

Question 13 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

Consider the following three functions.

f_1 = 10^n, \quad f_2 = n^{\log n}, \quad f_3 = n^{\sqrt{n}}

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

A

$f_3, f_2, f_1$

B

$f_2, f_1, f_3$

C

$f_1, f_2, f_3$

D

$f_2, f_3, f_1$

Question 14 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

Consider the following statements.

$S_1$ : The sequence of procedure calls corresponds to a preorder traversal of the activation tree.

$S_2$ : The sequence of procedure returns corresponds to a postorder traversal of the activation tree.

Which one of the following options is correct?

A

$S_1$ is true and $S_2$ is false

B

$S_1$ is false and $S_2$ is true

C

$S_1$ is true and $S_2$ is true

D

$S_1$ is false and $S_2$ is false

Question 15 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

Consider the following statements.

$S_1$ : Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).

$S_2$ : For any context-free grammar, there is a parser that takes at most $\mathcal{O}(n^3)$ time to parse a string of length $n$ .

Which one of the following options is correct?

A

$S_1$ is true and $S_2$ is false

B

$S_1$ is false and $S_2$ is true

C

$S_1$ is true and $S_2$ is true

D

$S_1$ is false and $S_2$ is false

Question 16 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

Let the representation of a number in base 3 be 210. What is the hexadecimal representation of the number?

A

15

B

21

C

D2

D

528

Question 17 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

Let $p$ and $q$ be two propositions. Consider the following two formulae in propositional logic.

S_1: (\neg p \land (p \lor q)) \rightarrow q

S_2: q \rightarrow (\neg p \land (p \lor q))

Which one of the following choices is correct?

A

Both $S_1$ and $S_2$ are tautologies.

B

$S_1$ is a tautology but $S_2$ is not a tautology.

C

$S_1$ is not a tautology but $S_2$ is a tautology.

D

Neither $S_1$ nor $S_2$ is a tautology.

Question 18 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

Consider the following two statements.

$S_1$ : Destination MAC address of an ARP reply is a broadcast address.

$S_2$ : Destination MAC address of an ARP request is a broadcast address.

Which one of the following choices is correct?

A

Both $S_1$ and $S_2$ are true.

B

$S_1$ is true and $S_2$ is false.

C

$S_1$ is false and $S_2$ is true.

D

Both $S_1$ and $S_2$ are false.

Question 19 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

Consider the following array.

23	32	45	69	72	73	89	97

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

A

Selection sort

B

Mergesort

C

Insertion sort

D

Quicksort using the last element as pivot

Question 20 of 65

MCQMultiple choice: one correct option1 markWrong answer: −1/3

A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$ ?

A

$\Theta(n \log n)$

B

$\Theta(n)$

C

$\Theta(\log n)$

D

$\Theta(1)$

Question 21 of 65

MSQMultiple select: one or more correct options1 markNo negative marking

In the context of operating systems, which of the following statements is/are correct with respect to paging?

A

Paging helps solve the issue of external fragmentation.

B

Page size has no impact on internal fragmentation.

C

Paging incurs memory overheads.

D

Multi-level paging is necessary to support pages of different sizes.

Question 22 of 65

MSQMultiple select: one or more correct options1 markNo negative marking

Let $\langle M \rangle$ denote an encoding of an automaton $M$ . Suppose that $\Sigma = \{0,1\}$ . Which of the following languages is/are NOT recursive?

A

$L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \emptyset\}$

B

$L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \Sigma^*\}$

C

$L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \emptyset\}$

D

$L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \Sigma^*\}$

Question 23 of 65

MSQMultiple select: one or more correct options1 markNo negative marking

Suppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the database either during the transactions or during recovery.

Which of the following statements is/are correct?

A

The same undo and redo list will be used while recovering again.

B

The system cannot recover any further.

C

All the transactions that are already undone and redone will not be recovered again.

D

The database will become inconsistent.

Question 24 of 65

MSQMultiple select: one or more correct options1 markNo negative marking

Which of the following standard C library functions will always invoke a system call when executed from a single-threaded process in a UNIX/Linux operating system?

A

exit

B

malloc

C

sleep

D

strlen

Question 25 of 65

MSQMultiple select: one or more correct options1 markNo negative marking

Consider a linear list based directory implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file metadata, such as the list of pointers to the data blocks. Consider a given directory foo.

Which of the following operations will necessarily require a full scan of foo for successful completion?

A

Creation of a new file in foo

B

Deletion of an existing file from foo

C

Renaming of an existing file in foo

D

Opening of an existing file in foo

Question 26 of 65

NATNumerical answer1 markNo negative marking

In an undirected connected planar graph $G$ , there are eight vertices and five faces. The number of edges in $G$ is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 27 of 65

NATNumerical answer1 markNo negative marking

Consider the following undirected graph with edge weights as shown:

A 3 by 3 grid graph with 9 vertices and labeled edge weights of 0.1 and 0.9.

The number of minimum-weight spanning trees of the graph is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 28 of 65

NATNumerical answer1 markNo negative marking

The lifetime of a component of a certain type is a random variable whose probability density function is exponentially distributed with parameter $\lambda$ . For a randomly picked component of this type, the probability that its lifetime exceeds the expected lifetime (rounded to 2 decimal places) is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 29 of 65

NATNumerical answer1 markNo negative marking

There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that:

The fastest computer gets the toughest job and the slowest computer gets the easiest job.
Every computer gets at least one job.

The number of ways in which this can be done is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 30 of 65

NATNumerical answer1 markNo negative marking

Consider the following expression.

\lim_{x \to -3} \frac{\sqrt{2x + 22} - 4}{x + 3}

The value of the above expression (rounded to 2 decimal places) is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 31 of 65

NATNumerical answer1 markNo negative marking

Consider the following sequence of operations on an empty stack.

push(54); push(52); pop(); push(55); push(62); s = pop();

Consider the following sequence of operations on an empty queue.

enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue();

The value of $s + q$ is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 32 of 65

NATNumerical answer1 markNo negative marking

Consider a computer system with a byte-addressable primary memory of size $2^{32}$ bytes. Assume the computer system has a direct-mapped cache of size $32\text{ KB}$ ( $1\text{ KB} = 2^{10}\text{ bytes}$ ), and each cache block is of size $64\text{ bytes}$ .

The size of the tag field is ___________ bits.

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 33 of 65

NATNumerical answer1 markNo negative marking

A relation $r(A, B)$ in a relational database has 1200 tuples. The attribute $A$ has integer values ranging from 6 to 20, and the attribute $B$ has integer values ranging from 1 to 20. Assume that the attributes $A$ and $B$ are independently distributed.

The estimated number of tuples in the output of $\sigma_{(A > 10) \lor (B = 18)}(r)$ is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 34 of 65

NATNumerical answer1 markNo negative marking

Consider the following representation of a number in IEEE 754 single-precision floating point format with a bias of 127.

S: 1 E: 10000001 F: 11110000000000000000000

Here S, E and F denote the sign, exponent and fraction components of the floating point representation.

The decimal value corresponding to the above representation (rounded to 2 decimal places) is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 35 of 65

NATNumerical answer1 markNo negative marking

Three processes arrive at time zero with CPU bursts of 16, 20 and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is __________ milliseconds.

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 36 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code:

P \rightarrow D^* E

D \rightarrow \text{int } ID \quad \{\text{record that } ID.\text{lexeme is of type int}\}

D \rightarrow \text{bool } ID \quad \{\text{record that } ID.\text{lexeme is of type bool}\}

E \rightarrow E_1 + E_2 \quad \{\text{check that } E_1.\text{type} = E_2.\text{type} = \text{int}; \text{ set } E.\text{type} := \text{int}\}

E \rightarrow !E_1 \quad \{\text{check that } E_1.\text{type} = \text{bool}; \text{ set } E.\text{type} := \text{bool}\}

E \rightarrow ID \quad \{\text{set } E.\text{type} := \text{int}\}

With respect to the above grammar, which one of the following choices is correct?

A

The actions can be used to correctly type-check any syntactically correct program.

B

The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.

C

The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.

D

The actions will lead to an infinite loop.

Question 37 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

The following relation records the age of 500 employees of a company, where empNo (indicating the employee number) is the key:

\text{empAge}(\text{empNo}, \text{age})

Consider the following relational algebra expression:

\Pi_{\text{empNo}}(\text{empAge} \bowtie_{(\text{age} > \text{age1})} \rho_{\text{empNo1}, \text{age1}}(\text{empAge}))

What does the above expression generate?

A

Employee numbers of only those employees whose age is the maximum.

B

Employee numbers of only those employees whose age is more than the age of exactly one other employee.

C

Employee numbers of all employees whose age is not the minimum.

D

Employee numbers of all employees whose age is the minimum.

Question 38 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Consider a 3-bit counter, designed using T flip-flops, as shown below:

Synchronous 3-bit counter circuit designed using three T flip-flops with inputs Tp=R, Tq=P', and Tr=Q'.

Assuming the initial state of the counter given by PQR as 000, what are the next three states?

A

011, 101, 000

B

001, 010, 111

C

011, 101, 111

D

001, 010, 000

Question 39 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Assume that a 12-bit Hamming codeword consisting of 8-bit data and 4 check bits is $d_8 d_7 d_6 d_5 c_8 d_4 d_3 d_2 c_4 d_1 c_2 c_1$ , where the data bits and the check bits are given in the following tables:

Data bits
d8	d7	d6	d5	d4	d3	d2	d1
1	1	0	x	0	1	0	1

Check bits
c8	c4	c2	c1
y	0	1	0

Which one of the following choices gives the correct values of $x$ and $y$ ?

A

$x$ is 0 and $y$ is 0.

B

$x$ is 0 and $y$ is 1.

C

$x$ is 1 and $y$ is 0.

D

$x$ is 1 and $y$ is 1.

Question 40 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Consider the following recurrence relation.

T(n) = \begin{cases} T(n/2) + T(2n/5) + 7n & \text{if } n > 0 \\ 1 & \text{if } n = 0 \end{cases}

Which one of the following options is correct?

A

$T(n) = \Omega(n^{5/2})$

B

$T(n) = \mathcal{O}(n \log n)$

C

$T(n) = \Theta(n)$

D

$T(n) = \Theta((\log n)^{5/2})$

Question 41 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Consider the following context-free grammar where the set of terminals is $\{a, b, c, d, f\}$ .

S \rightarrow daT \mid Rf

T \rightarrow aS \mid baT \mid \epsilon

R \rightarrow caTR \mid \epsilon

The following is a partially-filled LL(1) parsing table.

LL(1) parsing table with numbered target cells
	a	b	c	d	f	$
S			(1)	S -> daT	(2)
T	T -> aS	T -> baT	(3)		T -> eps	(4)
R			R -> caTR		R -> eps

Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)?

A

(1) $S \rightarrow Rf$ $\quad$ (2) $S \rightarrow Rf$ $\quad$ (3) $T \rightarrow \epsilon$ $\quad$ (4) $T \rightarrow \epsilon$

B

(1) blank $\quad$ (2) $S \rightarrow Rf$ $\quad$ (3) $T \rightarrow \epsilon$ $\quad$ (4) $T \rightarrow \epsilon$

C

(1) $S \rightarrow Rf$ $\quad$ (2) blank $\quad$ (3) blank $\quad$ (4) $T \rightarrow \epsilon$

D

(1) blank $\quad$ (2) $S \rightarrow Rf$ $\quad$ (3) blank $\quad$ (4) blank

Question 42 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Let $r_i(z)$ and $w_i(z)$ denote read and write operations respectively on a data item $z$ by a transaction $T_i$ . Consider the following two schedules.

S_1: r_1(x) \; r_1(y) \; r_2(x) \; r_2(y) \; w_2(y) \; w_1(x)

S_2: r_1(x) \; r_2(x) \; r_2(y) \; w_2(y) \; r_1(y) \; w_1(x)

Which one of the following options is correct?

A

$S_1$ is conflict serializable, and $S_2$ is not conflict serializable.

B

$S_1$ is not conflict serializable, and $S_2$ is conflict serializable.

C

Both $S_1$ and $S_2$ are conflict serializable.

D

Neither $S_1$ nor $S_2$ is conflict serializable.

Question 43 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Consider the relation $R(P, Q, S, T, X, Y, Z, W)$ with the following functional dependencies.

PQ \rightarrow X; \quad P \rightarrow YX; \quad Q \rightarrow Y; \quad Y \rightarrow ZW

Consider the decomposition of the relation $R$ into the constituent relations according to the following two decomposition schemes.

D_1: R = [(P, Q, S, T); (P, T, X); (Q, Y); (Y, Z, W)]

D_2: R = [(P, Q, S); (T, X); (Q, Y); (Y, Z, W)]

Which one of the following options is correct?

A

$D_1$ is a lossless decomposition, but $D_2$ is a lossy decomposition.

B

$D_1$ is a lossy decomposition, but $D_2$ is a lossless decomposition.

C

Both $D_1$ and $D_2$ are lossless decompositions.

D

Both $D_1$ and $D_2$ are lossy decompositions.

Question 44 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Let $G$ be a group of order 6, and $H$ be a subgroup of $G$ such that $1 < |H| < 6$ .

Which one of the following options is correct?

A

Both $G$ and $H$ are always cyclic.

B

$G$ may not be cyclic, but $H$ is always cyclic.

C

$G$ is always cyclic, but $H$ may not be cyclic.

D

Both $G$ and $H$ may not be cyclic.

Question 45 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Consider the two statements.

S_1: \text{There exist random variables } X \text{ and } Y \text{ such that } \left(E[(X - E[X])(Y - E[Y])\right)^2 > \text{Var}[X]\text{Var}[Y]

S_2: \text{For all random variables } X \text{ and } Y, \quad \text{Cov}[X, Y] = E[|X - E[X]||Y - E[Y]|]

Which one of the following choices is correct?

A

Both $S_1$ and $S_2$ are true.

B

$S_1$ is true, but $S_2$ is false.

C

$S_1$ is false, but $S_2$ is true.

D

Both $S_1$ and $S_2$ are false.

Question 46 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Let $G = (V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as:

\text{diam}(G) = \max_{u, v} \{\text{the length of shortest path between } u \text{ and } v\}

Let $M$ be the adjacency matrix of $G$ .
Define graph $G_2$ on the same set of vertices with adjacency matrix $N$ , where

N_{ij} = \begin{cases} 1 & \text{if } M_{ij} > 0 \text{ or } P_{ij} > 0, \text{ where } P = M^2 \\ 0 & \text{otherwise} \end{cases}

Which one of the following statements is true?

A

$\text{diam}(G_2) \le \lceil \text{diam}(G)/2 \rceil$

B

$\lceil \text{diam}(G)/2 \rceil < \text{diam}(G_2) < \text{diam}(G)$

C

$\text{diam}(G_2) = \text{diam}(G)$

D

$\text{diam}(G) < \text{diam}(G_2) < 2\,\text{diam}(G)$

Question 47 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Consider the following ANSI C program.

#include <stdio.h>
int main()
{
    int i, j, count;
    count = 0;
    i = 0;
    for (j = -3; j <= 3; j++)
    {
        if ((j >= 0) && (i++))
            count = count + j;
    }
    count = count + i;
    printf("%d", count);
    return 0;
}

Which one of the following options is correct?

A

The program will not compile successfully.

B

The program will compile successfully and output 10 when executed.

C

The program will compile successfully and output 8 when executed.

D

The program will compile successfully and output 13 when executed.

Question 48 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

Consider the following language.

L = \{w \in \{0,1\}^* \mid w \text{ ends with the substring } 011\}

Which one of the following deterministic finite automata accepts $L$ ?

A

Deterministic finite automaton option A with four states where the final state has a self-loop on 1 and transition on 0 to the second state.

B

Option B DFA: start state (self-loop on 1) goes to the second state on 0; the second state has a self-loop on 0 and goes to the third state on 1; the third state returns to the second state on 0 and goes to the accepting state on 1; the accepting state has a self-loop on 0,1.

C

Deterministic finite automaton option C with four states where the final state transitions on 1 back to the third state.

D

Deterministic finite automaton option D with four states where the final state transitions on 1 back to the initial state and on 0 to the second state.

Question 49 of 65

MCQMultiple choice: one correct option2 marksWrong answer: −2/3

For a Turing machine $M$ , $\langle M \rangle$ denotes an encoding of $M$ . Consider the following two languages.

L_1 = \{\langle M \rangle \mid M \text{ takes more than 2021 steps on all inputs}\}

L_2 = \{\langle M \rangle \mid M \text{ takes more than 2021 steps on some input}\}

Which one of the following options is correct?

A

Both $L_1$ and $L_2$ are decidable.

B

$L_1$ is decidable and $L_2$ is undecidable.

C

$L_1$ is undecidable and $L_2$ is decidable.

D

Both $L_1$ and $L_2$ are undecidable.

Question 50 of 65

MSQMultiple select: one or more correct options2 marksNo negative marking

Define $R_n$ to be the maximum amount earned by cutting a rod of length $n$ meters into one or more pieces of integer length and selling them. For $i > 0$ , let $p[i]$ denote the selling price of a rod whose length is $i$ meters. Consider the array of prices:

p[1] = 1, \quad p[2] = 5, \quad p[3] = 8, \quad p[4] = 9, \quad p[5] = 10, \quad p[6] = 17, \quad p[7] = 18

Which of the following statements is/are correct about $R_7$ ?

A

$R_7 = 18$

B

$R_7 = 19$

C

$R_7$ is achieved by three different solutions.

D

$R_7$ cannot be achieved by a solution consisting of three pieces.

Question 51 of 65

MSQMultiple select: one or more correct options2 marksNo negative marking

An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.

Let $T$ be a DFS tree obtained by doing DFS in a connected undirected graph $G$ .
Which of the following options is/are correct?

A

Root of $T$ can never be an articulation point in $G$ .

B

Root of $T$ is an articulation point in $G$ if and only if it has 2 or more children.

C

A leaf of $T$ can be an articulation point in $G$ .

D

If $u$ is an articulation point in $G$ such that $x$ is an ancestor of $u$ in $T$ and $y$ is a descendent of $u$ in $T$ , then all paths from $x$ to $y$ in $G$ must pass through $u$ .

Question 52 of 65

MSQMultiple select: one or more correct options2 marksNo negative marking

Consider the following Boolean expression.

F = (X + Y + Z)(\overline{X} + Y)(\overline{Y} + Z)

Which of the following Boolean expressions is/are equivalent to $\overline{F}$ (complement of $F$ )?

A

$(\overline{X} + \overline{Y} + \overline{Z})(X + \overline{Y})(Y + \overline{Z})$

B

$X\overline{Y} + \overline{Z}$

C

$(X + \overline{Z})(\overline{Y} + \overline{Z})$

D

$X\overline{Y} + Y\overline{Z} + \overline{X}\overline{Y}\overline{Z}$

Question 53 of 65

MSQMultiple select: one or more correct options2 marksNo negative marking

A relation $R$ is said to be circular if $aRb$ and $bRc$ together imply $cRa$ .

Which of the following options is/are correct?

A

If a relation $S$ is reflexive and symmetric, then $S$ is an equivalence relation.

B

If a relation $S$ is circular and symmetric, then $S$ is an equivalence relation.

C

If a relation $S$ is reflexive and circular, then $S$ is an equivalence relation.

D

If a relation $S$ is transitive and circular, then $S$ is an equivalence relation.

Question 54 of 65

MSQMultiple select: one or more correct options2 marksNo negative marking

A TCP server application is programmed to listen on port number $P$ on host $S$ . A TCP client is connected to the TCP server over the network.

Consider that while the TCP connection was active, the server machine $S$ crashed and rebooted. Assume that the client does not use the TCP keepalive timer.
Which of the following behaviors is/are possible?

A

If the client was waiting to receive a packet, it may wait indefinitely.

B

The TCP server application on $S$ can listen on $P$ after reboot.

C

If the client sends a packet after the server reboot, it will receive a RST segment.

D

If the client sends a packet after the server reboot, it will receive a FIN segment.

Question 55 of 65

MSQMultiple select: one or more correct options2 marksNo negative marking

Consider two hosts $P$ and $Q$ connected through a router $R$ . The maximum transfer unit (MTU) value of the link between $P$ and $R$ is 1500 bytes, and between $R$ and $Q$ is 820 bytes.

A TCP segment of size 1400 bytes was transferred from $P$ to $Q$ through $R$ , with IP identification value as 0x1234. Assume that the IP header size is 20 bytes. Further, the packet is allowed to be fragmented, i.e., Don't Fragment (DF) flag in the IP header is not set by $P$ .

Which of the following statements is/are correct?

A

Two fragments are created at $R$ and the IP datagram size carrying the second fragment is 620 bytes.

B

If the second fragment is lost, $R$ will resend the fragment with the IP identification value 0x1234.

C

If the second fragment is lost, $P$ is required to resend the whole TCP segment.

D

TCP destination port can be determined by analysing only the second fragment.

Question 56 of 65

MSQMultiple select: one or more correct options2 marksNo negative marking

Consider the following pseudocode, where $S$ is a semaphore initialized to 5 in line#2 and counter is a shared variable initialized to 0 in line#1. Assume that the increment operation in line#7 is not atomic.

1. int counter = 0;
2. Semaphore S = init(5);
3. void parop(void)
4. {
5.     wait(S);
6.     wait(S);
7.     counter++;
8.     signal(S);
9.     signal(S);
10. }

If five threads execute the function parop concurrently, which of the following program behavior(s) is/are possible?

A

The value of counter is 5 after all the threads successfully complete the execution of parop.

B

The value of counter is 1 after all the threads successfully complete the execution of parop.

C

The value of counter is 0 after all the threads successfully complete the execution of parop.

D

There is a deadlock involving all the threads.

Question 57 of 65

MSQMultiple select: one or more correct options2 marksNo negative marking

Consider a dynamic hashing approach for 4-bit integer keys:

There is a main hash table of size 4.
The 2 least significant bits of a key is used to index into the main hash table.
Initially, the main hash table entries are empty.
Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.
First, the 3rd least significant bit is used to divide the keys into left and right subtrees.
To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit.
A split is done only if it is needed, i.e., only when there is a collision.

Consider the following state of the hash table.

State of a 4-slot hash table where slot 00 is empty, slot 01 points to a binary tree with three keys, slot 10 points to a binary tree with two keys, and slot 11 points to a single key.

Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?

A

5, 9, 4, 13, 10, 7

B

9, 5, 10, 6, 7, 1

C

10, 9, 6, 7, 5, 13

D

9, 5, 13, 6, 10, 14

Question 58 of 65

NATNumerical answer2 marksNo negative marking

Consider the following ANSI C function:

int SimpleFunction(int Y[], int n, int x)
{
    int total = Y[0], loopIndex;
    for (loopIndex = 1; loopIndex <= n - 1; loopIndex++)
        total = x * total + Y[loopIndex];
    return total;
}

Let $Z$ be an array of 10 elements with $Z[i]=1$ , for all $i$ such that $0 \le i \le 9$ . The value returned by SimpleFunction(Z, 10, 2) is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 59 of 65

NATNumerical answer2 marksNo negative marking

Consider the sliding window flow-control protocol operating between a sender and a receiver over a full-duplex error-free link. Assume the following:

The time taken for processing the data frame by the receiver is negligible.
The time taken for processing the acknowledgement frame by the sender is negligible.
The sender has infinite number of frames available for transmission.
The size of the data frame is 2,000 bits and the size of the acknowledgement frame is 10 bits.
The link data rate in each direction is 1 Mbps ( $= 10^6$ bits per second).
One way propagation delay of the link is 100 milliseconds.

The minimum value of the sender's window size in terms of the number of frames, (rounded to the nearest integer) needed to achieve a link utilization of 50% is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 60 of 65

NATNumerical answer2 marksNo negative marking

Consider the following C code segment:

a = b + c;
e = a + 1;
d = b + c;
f = d + 1;
g = e + f;

In a compiler, this code segment is represented internally as a directed acyclic graph (DAG). The number of nodes in the DAG is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 61 of 65

NATNumerical answer2 marksNo negative marking

In a pushdown automaton $P = (Q, \Sigma, \Gamma, \delta, q_0, F)$ , a transition of the form,

(q, Y) \in \delta(p, a, X)

where $p, q \in Q$ , $a \in \Sigma \cup \{\epsilon\}$ , and $X, Y \in \Gamma \cup \{\epsilon\}$ , represents transitioning from state $p$ to $q$ on input $a$ by popping $X$ and pushing $Y$ .

Consider the following pushdown automaton over the input alphabet $\Sigma = \{a, b\}$ and stack alphabet $\Gamma = \{\#, A\}$ .

Pushdown automaton with states q0, q1, q2, q3 where q0 pushes #, q1 pushes A on input a, q2 pops A on input b, and q3 accepts if A remains on stack.

The number of strings of length 100 accepted by the above pushdown automaton is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 62 of 65

NATNumerical answer2 marksNo negative marking

Consider the following matrix.

\begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}

The largest eigenvalue of the above matrix is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 63 of 65

NATNumerical answer2 marksNo negative marking

A five-stage pipeline has stage delays of 150, 120, 150, 160 and 140 nanoseconds. The registers that are used between the pipeline stages have a delay of 5 nanoseconds each.

The total time to execute 100 independent instructions on this pipeline, assuming there are no pipeline stalls, is _____________ nanoseconds.

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 64 of 65

NATNumerical answer2 marksNo negative marking

A sender (S) transmits a signal, which can be one of the two kinds: H and L with probabilities 0.1 and 0.9 respectively, to a receiver (R).
In the graph below, the weight of edge $(u, v)$ is the probability of receiving $v$ when $u$ is transmitted, where $u,v \in \{H, L\}$ . For example, the probability that the received signal is L given the transmitted signal was H, is 0.7.

Binary asymmetric communication channel diagram showing transition probabilities from sender states H and L to receiver states H and L.

If the received signal is H, the probability that the transmitted signal was H (rounded to 2 decimal places) is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Question 65 of 65

NATNumerical answer2 marksNo negative marking

Consider the following instruction sequence where registers R1, R2 and R3 are general purpose and $\text{MEMORY}[X]$ denotes the content at the memory location $X$ .

Instruction sequence specification
Instruction	Semantics	Instruction Size (bytes)
MOV R1, (5000)	R1 <- MEMORY[5000]	4
MOV R2, (R3)	R2 <- MEMORY[R3]	4
ADD R2, R1	R2 <- R1 + R2	2
MOV (R3), R2	MEMORY[R3] <- R2	4
INC R3	R3 <- R3 + 1	2
DEC R1	R1 <- R1 - 1	2
BNZ 1004	Branch if not zero to the given absolute address	2
HALT	Stop	1

Assume that the content of the memory location 5000 is 10, and the content of the register R3 is 3000. The content of each of the memory locations from 3000 to 3010 is 50. The instruction sequence starts from the memory location 1000. All the numbers are in decimal format. Assume that the memory is byte addressable.

After the execution of the program, the content of memory location 3010 is __________

Your answer

A number: digits, one decimal point and an optional minus sign at the start.

Not visited	0
Not answered	0
Answered	0
Marked for review	0
Answered and marked for review	0

GATE CS 2021 Set 1 mock test

Submitting your test