GATE CSE 2021 Set 1
Paper was held on
Sat, Feb 13, 2021 4:00 AM
GATE CSE
Consider the following three functions.
f1 = 10n, f2 = nlogn, f3 = n√n
Which one of the following options arranges the
View Question
Consider the following array.
23
32
45
69
72
73
View Question
Consider the following undirected graph with edge weights as shown:
The number of minimumweight spanning trees of t
View Question
Consider the following recurrence relation.
$$T(n) = \left\{ {\begin{array}{*{20}{c}} {T(n/2) + T(2n/5) + 7n \ \ \ if\
View Question
Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as:
diam(G) = $$\displays
View Question
Consider the following statements.
S1 : Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars
View Question
Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax
View Question
Consider the following C code segment:
a = b + c;
e = a + 1;
d = b + c;
f = d + 1;
g = e + f;
In a
View Question
Consider two hosts P and Q connected through a router R. The maximum transfer unit (MTU) value of the link between P and
View Question
Consider the sliding window flowcontrol protocol operating between a sender and a receiver over a fullduplex errorfre
View Question
A TCP server application is programmed to listen on port number P on host S. A TCP client connected to the TCP server ov
View Question
Consider the following two statements.
S1 : Destination MAC address of an ARP reply is a broadcast address.
S2 : Desti
View Question
A fivestage pipeline has stage delays of 150, 120, 150, 160 and 140 nanoseconds. The registers that are used between th
View Question
Consider the following instruction sequence where register R1, R2 and R3 are general purpose and MEMORY[X] denotes the c
View Question
Consider a computer system with a byteaddressable primary memory of size 232 bytes. Assume the computer system has
View Question
Consider the following sequence of operations on an empty stack.
push(54); push(52); pop(); push(55); push(62); s = pop
View Question
Consider a dynamic hashing approach for 4bit integer keys:
1. There is a main hash table of size 4.
2. The 2 least si
View Question
Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array eleme
View Question
A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smal
View Question
Consider the following statements.
S1 : The sequence of procedure calls corresponds to a preorder traversal of the acti
View Question
Define Rn to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length
View Question
Suppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the
View Question
Consider a linear list based implementation in a file system. Each directory is a list of nodes, where each node contain
View Question
A relation r(A, B) in a relational database has 1200 tuples. The attribute A has integer values ranging from 6 to 20, an
View Question
The following relation records the age of 500 employees of a company, where empNo (Indicating the employee number) is th
View Question
Consider the relation R(P, Q, S, T, X, Y, Z, W) with the following functional dependencies.
PQ → X; P → YX; Q
View Question
Let ri(z) and wi(z) denote read and write operations respectively on a data item z by a transaction Ti. Consider the fol
View Question
Assume that a 12bit Hamming codeword consisting of 8bit data and 4 check bits is d8d7d6d5c8d4d3d2c4d1c2c1, where the d
View Question
Let the representation of a number in base 3 be 210. What is the hexadecimal representation of the number?
View Question
Consider the following Boolean expression.
$$F = (X + Y + Z)(\overline X + Y)(\overline Y + Z)$$
Which of the followin
View Question
Consider a 3bit counter, designed using T flipflop, as shown below:
Assuming the initial state of the counter gi
View Question
Consider the following representation of a number in IEEE 754 singleprecision floating point format with a bias of 127.
View Question
Let p and q be two propositions. Consider the following two formulae in propositional logic.
S1 : (¬p ∧ (p&nb
View Question
There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned
View Question
Consider the two statements.
S1 : There exist random variables X and Y such that
(E[X  E(X)) (Y  E(Y))])2 >
View Question
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects
View Question
A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?
View Question
The lifetime of a component of a certain type is a random variable whose probability density function is exponentially d
View Question
Let G be a group order 6, and H be a subgroup of G such that 1 < H < 6. Which one of the following options is co
View Question
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,
View Question
Consider the following expression
$$\mathop {\lim }\limits_{x \to 3} \frac{{\sqrt {2x + 22}  4}}{{x + 3}}$$
The valu
View Question
Consider the following matrix.
$$\left( {\begin{array}{*{20}{c}} 0&1&1&1\\ 1&0&1&1\\ 1&1&am
View Question
In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is ______
View Question
In the context operating systems, which of the following statements is/are correct with respect to paging?
View Question
Three processes arrive at time zero with CPU bursts of 16, 20, and 10 milliseconds. If the scheduler has prior knowledge
View Question
Which of the following standard C library functions will always invoke a system call when executed from a singlethreade
View Question
Consider the following pseudocode, where S is a semaphore intialized to 5 in line#2 an counter is a shared variable inti
View Question
Consider the following ANSI C program.
#include <stdio.h>
int main( ) {
int i, j, count;
count = 0;
i = 0;
f
View Question
Consider the following ANSI C function:
int SimpleFunction (int y[], int n, int x)
{
int total = y[0], loopIndex;
fo
View Question
Suppose that L1 is a regular and L2 is a contextfree language, Which one of the following languages is NOT necessarily
View Question
Consider the following contextfree grammar where the set of terminals is {a, b, c, d, f}.
S → d a T  R f
T 
View Question
For a Turing machine M, {M} denotes an encoding of M. Consider the following two languages.
L1 = {(M)  M takes more th
View Question
In a pushdown automaton P = (Q, ∑, Γ, δ, q0, F), a transition of the form,
where p, q ∈ Q, a&nb
View Question
Consider the following language.
L = { w ∈ {0, 1}*  w ends with the substring 011}
Which one of the following de
View Question
Let $$\left\langle M \right\rangle $$ denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Whi
View Question
General Aptitude
Given below are two statements I and II and two conclusions I and II :Statement :I. All bacteria are microorganisms.II.
View Question
There are five bags each containing identical sets of ten distinct chocolates. One chocolate is picked from each bag.The
View Question
A circular sheet of paper is folded along the lines in the directions shown. The paper, after being punched in the fili
View Question
We have 2 rectangular sheets of paper, M and N, of dimensions 6 cm $$\times$$ 1 cm each. Sheet M is rolled to form an op
View Question
Consider the following sentences :(i) Everybody in the class is prepared for the exam.(ii) Babu invited Danish to his ho
View Question
Some people suggest antiobesity measures (AOM) such as displaying calorie information in restaurant menus. Such measure
View Question
________ is to surgery as writer is to ________Which one of the following options maintains a similar logical relation i
View Question
A polygon is convex if, for every pair of points. P and Q belonging to the polygon, the line segment PQ lies completely
View Question
Items
Cost
Profit%
Marked price
P
5400

5860
Q

25
View Question
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 st
View Question