GATE 2021 CSE & IT

________ is to surgery as writer is to ________ Which one of the following options maintains a similar logical relation in the above sentence?

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, the...

Let p and q be two propositions. Consider the following two formulae in propositional logic. S 1 : (¬p ∧ (p ∨ q)) → q S 2 : q → (¬p ∧ (p ∨ q)) Which one of the following choices is...

Consider a linear list based 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 li...

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 tou...

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. A...

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 give...

Consider the relation R(P, Q, S, T, X, Y, Z, W) with the following functional dependencies. PQ → X; P → YX; Q → Y; Y → ZW Consider the decomposition of the relation R into the cons...

Consider the two statements. S 1 : There exist random variables X and Y such that (E[X - E(X)) (Y - E(Y))]) 2 > Var[X] Var[Y] S 2 : For all random variables X and Y, Cov[X, Y] = E...

Consider the following ANSI C program. #include <stdio.h> int main( ) { int i, j, count; count = 0; i = 0; for (j = -3; j = 0) && (i++)) count = count + j; } count = count + i; pri...

A relation R is said to be circular if a R b and b R c together imply c R a. Which of the following options is/are correct?

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

Consider the following instruction sequence where register R1, R2 and R3 are general purpose and MEMORY[X] denotes the content at the memory location X. Instruction Semantics Instr...

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

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 a...

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 KB (1 KB = 2 10 bytes), and ea...

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...

A TCP server application is programmed to listen on port number P on host S. A TCP client connected to the TCP server over the network. Consider that while the TCP connection was a...

Consider the following pseudocode, where S is a semaphore intialized to 5 in line#2 an counter is a shared variable intialized to 0 in line#1. Assume that the increment operation i...

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 corresp...

Consider the following matrix. $$\left( {\begin{array}{*{20}{c}} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{array}} \right)$$ The largest eigenvalue of the above matrix is ______

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

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?

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

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....

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...

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...

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 se...

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 to...

The lifetime of a component of a certain type is a random variable whose probability density function is exponentially distributed with parameter 2. For a randomly picked component...

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 correct?

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$$ (co...

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...

Consider the following expression $$\mathop {\lim }\limits_{x \to -3} \frac{{\sqrt {2x + 22} - 4}}{{x + 3}}$$ The value of the above expression (rounded to 2 decimal places) is ___...

Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as: diam(G) = $$\displaystyle\max_{u, x\in V}$$ {the length of shortest path between u and...

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....

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...

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 *...

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...

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 :

Items Cost Profit% Marked price P 5400 - 5860 Q - 25 10000 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...

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:...

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 open cylinder by bringing the short edges of the sheet togethe...

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...

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 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 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?

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] denotes the selling p...

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 above arr...

Given below are two statements I and II and two conclusions I and II : Statement : I. All bacteria are microorganisms. II. All pathogens are microorganisms. Conclusions : I. Some p...

For a Turing machine M, {M} denotes an encoding of M. Consider the following two languages. L 1 = {(M) | M takes more than 2021 steps on all inputs} L 2 = {(M) | M takes more than...

Consider the following language. L = { w ∈ {0, 1}* | w ends with the substring 011} Which one of the following deterministic finite automata accepts L?

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

Suppose that L 1 is a regular and L 2 is a context-free language, Which one of the following languages is NOT necessarily context-free?

Consider the following three functions. f 1 = 10 n , f 2 = n logn , f 3 = n √n Which one of the following options arranges the functions in the increasing order of asymptotic growt...

Consider the following recurrence relation. $$T(n) = \left\{ {\begin{array}{*{20}{c}} {T(n/2) + T(2n/5) + 7n \ \ \ if\ n > 0}\\ {1\ \ \ \ \ \ \ if\ n = 0} \end{array}} \right.$$ Wh...

For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers : $$T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)$$...

Pen : Write :: Knife : ______ Which one of the following options maintains a similar logical relation in the above?

Consider the following ANSI C program: int main() { Integer x; return 0; } Which one of the following phases in a seven-phase C compiler will throw an error?

Which one of the following circuits implements the Boolean function given below? f(x, y, z) = m 0 + m 1 + m 3 + m 4 + m 5 + m 6 , where m i is the i th minterm.

Consider the following sets, where n > 2: S 1 : Set of all n x n matrices with entries from the set {a, b, c} S 2 : Set of all functions from the set {0,1, 2, ..., n 2 — 1} to the...

Suppose that f : R → R is a continuous function on the interval [-3, 3] and a differentiable function in the interval (-3, 3) such that for every x in the interval, f'(x) ≤ 2. If f...

Assume a two-level inclusive cache hierarchy, L1 and L2, where L2 is the larger of the two. Consider the following statements. S 1 : Read misses in a write through L1 cache do not...

In an examination, a student can choose the order in which two questions (QuesA and QuesB) must be attempted. - If the first question is answered wrong, the student gets zero marks...

The relation scheme given below is used to store information about the employees of a company, where empId is the key and deptId indicates the department to which the employee is a...

A bag has r red balls and b black balls. All balls are identical except for their colours. In a trial, a ball is randomly drawn from the bag, its colour is noted and the ball is pl...

For two n-dimensional real vectors P and Q, the operation s(P, Q) is defined as follows: $$s\left( {P,\;Q} \right) = \mathop \sum \limits_{i = 1}^n \left( {p\left[ i \right].Q\left...

Consider the following ANSI C program #include <stdio.h> int foo(int x, int y, int q) { if ((x <= 0 && (y <= 0)) return q; if (x <= 0) return foo(x, y - q, q); if (y <= 0) return f...

Consider a pipelined processor with 5 stages, Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), and Write Back (WB). Each stage of the pipeline, e...

Consider the following ANSI C program. #include<stdio.h> int main(){ int arr[4][5]; int i, j; for(i =0; i<4; i++){ for (j =0; j<5; j++){ arr [i][j] = 10*i + j; } } print("%d", *(ar...

Which of the following statement(s) is/are correct in the context of CPU scheduling?

For a given biased coin, the probability that the outcome of a toss is a head is 0.4. This coin is tossed 1,000 times. Let X denote the random variable whose value is the number of...

Consider the following ANSI C code segment: z = x + 3 + y -> f1 + y -> f2; for (i = 0; i < 200; i = i + 2){ if (z > i) { P = p + x + 3; q = q + y -> f2; } else { p = p + y -> f2; q...

Suppose we want to design a synchronous circuit that processes a string of 0’s and 1’s. Given a string, it produces another string by replacing the first 1 in any subsequence of co...

Let S be the following schedule of operations of three transactions T 1 , T 2 and T 3 in a relational database system: R 2 (Y), R 1 (X), R 3 (Z), R 1 (Y), W 1 (X), R 2 (Z), W 2 (Y)...

If the numerical value of a 2-byte unsigned integer on a little endian computer is 255 more than that on a big endian computer, which of the following choices represent(s) the unsi...

Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the se...

Consider the three-way handshake mechanism followed during TCP connection establishment between hosts P and Q. Let X and Y be two random 32-bit starting sequence numbers chosen by...

In the context of compilers, which of the following is/are NOT an intermediate representation of the source program?

Choose the correct choice(s) regarding the following propositional logic assertion S: S : ((P ∧ Q)→ R)→ ((P ∧ Q)→ (Q → R))

Consider a set-associative cache of size 2 KB (1 KB = 2 10 bytes) with cache block size of 64 bytes. Assume that the cache is byte-addressable and a 32-bit address is used for acce...

A data file consisting of 1,50,000 student-records is stored on a hard disk with block size of 4096 bytes. The data file is sorted on the primary key RollNo. The size of a record p...

Consider the following ANSI C function: int SomeFunction (int x, int y) { if ( (x == 1) I I (y == 1)) return 1; if (x == y) return x; if (x > y) return SomeFunction(x - y, y); if (...

Consider the following ANSI C program: #include <stdio.h> #include <stdlib.h> struct Node{ int value; struct Node ⋆next;}; int main(){ struct Node ⋆boxE, ⋆head, ⋆boxN; int index =...

Consider a computer system with multiple shared resource types, with one instance per resource type. Each instance can be owned by only one process at a time. Owning and freeing of...

Consider the following augmented grammar with {#, @, <, >, a, b, c} as the set of terminals. S' → S S → S # cS S → SS S → S @ S → < S > S → a S → b S → c Let I 0 = CLOSURE({S' → ∙...

Consider the following statements S1 and S2 about the relational data model: S1: A relation scheme can have at most one foreign key. S2: A foreign key in a relation scheme R cannot...

If x and y are two decimal digits and (0.1101) 2 = (0.8xy5) 10 , the decimal value of x + y is ______

Consider the cyclic redundancy check (CRC) based error detecting scheme having the generator polynomial X 3 + X + 1. Suppose the message m 4 m 3 m 2 m 1 m 0 = 11000 is to be transm...

For a statement S in a program, in the context of liveness analysis, the following sets are defined: USE(S): the set of variables used in S IN(S): the set of variables that are liv...

Consider the following multi-threaded code segment (in a mix of C and pseudocode), invoked by two processes P1 and P2, and each of the processes spawns two threads T1 and T2: int x...

Let S be a set consisting of 10 elements. The number of tuples of the form (A, B) such that A and B are subsets of S, and A ⊆ B is _______

The format of the single-precision floating-point representation of a real number as per the IEEE 754 standard is as follows: sign exponent mantissa Which one of the following choi...

Consider a computer system with DMA support. The DMA module is transferring one 8-bit character in one CPU cycle from a device to memory through cycle stealing at regular intervals...

Consider a Boolean function f(w, x, y, z) such that f(w, 0, 0, z) = 1 f(1, x, 1, z) = x + z f(w, 1, y, z) = wz + y The number of literals in the minimal sum-of-products expression...

Suppose that P is a 4 × 5 matrix such that every solution of the equation P x = 0 is a scalar multiple of [2 5 4 3 1] T ​. The rank of P is _________

Suppose the following functional dependencies hold on a relation U with attributes P, Q, R, S, and T : P → QR RS → T Which of the following functional dependencies can be inferred...

If $${\left( {x - {1 \over 2}} \right)^2} - {\left( {x - {3 \over 2}} \right)^2} = x + 2$$, then the value of x is :

Gauri said that she can play keyboard _______ her sister.

Listening to music during exercise improves exercise performance and reduces discomfort. Scientists researched whether listening to music while studying can help students learn bet...

Six students P, Q, R, S, T and U, with distinct heights, compare their heights and make the following observations: Observation I : S is taller than R. Observation II : Q is the sh...

Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?

Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties: 1. For any two letters, the code assigned to one lette...

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?

Let G be a connected undirected weighted graph. Consider the following two statements. S 1 : There exists a minimum weight edge in G which is present in every minimum spanning tree...

If $$\theta$$ is the angle, in degrees, between the longest diagonal of the cube and any one of the edges of the cube, then cos $$\theta$$ = _______

The number of student in three classes is in the ratio 3 : 13 : 6. If 18 students are added to each class, the ratio changes to 15 : 35 : 21. The total number of students in all th...

For a string w, we define w R to be the reverse of w. For example, if w = 01101 then w R = 10110. Which of the following languages is/are context-free?

Let L 1 be a regular language and L 2 be a context-free language. Which of the following languages is/are context-free?

Consider the following two statements about regular languages: S 1 : Every infinite regular language contains an undecidable language as a subset. S 2 : Every finite language is re...

Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string ∈ divisible by three.

Let L ⊆ {0,1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k s...

Consider a network using the pure ALOHA medium access control protocol, where each frame is of length 1,000 bits. The channel transmission rate is 1 Mbps (= 10 6 bits per second)....