GATE CSE 2021 PYQ

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

Consider the following undirected graph with edge weights as shown: The number of minimum-weight spanning trees of the graph is __________

Let G be a connected undirected weighted graph. Consider the following two statements. S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G. S2: If every ed

Consider the following array. 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?

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

Consider the following recurrence relation. Which one of the following options is correct?

Let be an undirected unweighted connected graph. The diameter of is defined as: Let be the adjacency matrix of . Define graph on the same set of vertices with adjacency matrix , where Which one of the

Define 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 , let denote the selling price of a rod whose length is meter

For constants and , consider the following recurrence defined on the non-negative integers: Which one of the following options is correct about the recurrence ?

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

Consider the following statements. S1: Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1). S2: For any context-free grammar, there is a parser that take

Consider the following statements. S1: The sequence of procedure calls corresponds to a preorder traversal of the activation tree. S2: The sequence of procedure returns corresponds to a postorder trav

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?

Consider the following ANSI C code segment: z=x + 3 + y-> f1 + y-> f2; for (i = 0; i i) { p = p + x + 3; q = q + y-> f1; } else { p = p + y-> f2; q = q + x + 3; } } Assume that the variable y points t

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

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 live at the entry of

Consider the following augmented grammar with as the set of terminals. Let . The number of items in the set is ___________

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 o

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 With respect to the ab

Consider the cyclic redundancy check (CRC) based error detecting scheme having the generator polynomial . Suppose the message is to be transmitted. Check bits are appended at the end of the message by

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 b

Consider a computer network using the distance vector routing algorithm in its network layer. The partial topology of the network is shown below. The objective is to find the shortest-cost path from t

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 (= bits per second). The aggregate number of t

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 th

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

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 P and Q respectively

Assume that a 12-bit Hamming codeword consisting of 8-bit data and 4 check bits is , where the data bits and the check bits are given in the following tables: Which one of the following choices gives

Consider the following two statements. S1: Destination MAC address of an ARP reply is a broadcast address. S2: Destination MAC address of an ARP request is a broadcast address. Which one of the follow

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

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, except the EX stage, ta

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

Consider the following instruction sequence where registers are general purpose and denotes the content at the memory location . Assume that the content of the memory location 5000 is 10, and the cont

Consider a set-associative cache of size 2KB ( bytes) with cache block size of 64 bytes. Assume that the cache is byte-addressable and a 32 -bit address is used for accessing the cache. If the width o

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 2 MHz p

Consider a computer system with a byte-addressable primary memory of size . Assume the computer system has a direct-mapped cache of size , and each cache block is of size 64 bytes. The size of the tag

Let and denote read and write operations respectively on a data item by a transaction . Consider the following two schedules. Which one of the following options is correct?

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 assigned. Each employ

Suppose the following functional dependencies hold on a relation U with attributes : Which of the following functional dependencies can be inferred from the above functional dependencies?

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 poin

The following relation records the age of 500 employees of a company, where empNo ( indicating the employee number) is the key: Consider the following relational algebra expression: What does the abov

Consider the relation with the following functional dependencies. Consider the decomposition of the relation R into the constituent relations according to the following two decomposition schemes. Whic

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 pointer for this disk

A relation in a relational database has 1200 tuples. The attribute has integer values ranging from 6 to 20, and the attribute has integer values ranging from 1 to 20. Assume that the attributes and ar

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 followi

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 be used to refer to

Let S be the following schedule of operations of three transactions in a relational database system: Consider the statements P and Q below: P: S is conflict-serializable. Q: If commits before finishes

Which one of the following circuits implements the Boolean function given below? where is the minterm.

Consider the following Boolean expression. Which of the following Boolean expressions is/are equivalent to (complement of )?

Consider a Boolean function such that The number of literals in the minimal sum-of-products expression of is ________

The format of the single-precision floating point representation of a real number as per the IEEE 754 standard is as follows: Which one of the following choices is correct with respect to the smallest

If and are two decimal digits and , the decimal value of is ___________

Consider a 3-bit counter, designed using T flip-flops, as shown below: Assuming the initial state of the counter given by PQR as 000, what are the next three states?

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, expon

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 unsigned integer on a li

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

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

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

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. If the first questio

For two n-dimensional real vectors and , the operation is defined as follows: Let be a set of 10-dimensional non-zero real vectors such that for every pair of distinct vectors . What is the maximum ca

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?

Consider the following directed graph: Which of the following is/are correct about the graph?

Suppose that P is a 4x5 matrix such that every solution of the equation Px=0 is a scalar multiple of . The rank of P is _______

Choose the correct choice(s) regarding the following proportional logic assertion S:

In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the

Consider the following sets, where : S1: Set of all nxn matrices with entries from the set S2: Set of all functions from the set to the set Which of the following choice(s) is/are correct?

A bag has red balls and 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 placed back into the bag a

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 times that head app

Consider the following expression. The value of the above expression (rounded to 2 decimal places) is ___________.

Consider the following matrix. The largest eigenvalue of the above matrix is __________.

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 slow

Consider the two statements. S1: There exist random variables and such that S2: For all random variables and , Which one of the following choices is correct?

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 of this type, the p

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

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

Suppose that is a continuous function on the interval [-3,3] and a differentiable function in the interval (-3,3) such that for every in the interval, . If , then is at most __________

Let p and q be two propositions. Consider the following two formulae in propositional logic. Which one of the following choices is correct?

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 is the probability of

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 resources are done

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

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

Consider the following multi-threaded code segment (in a mix of C and pseudo-code), invoked by two processes P1 and P2, and each of the processes spawns two threads T1 and T2: int x = 0; // global Loc

Consider the following pseudocode, where Sis 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

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

Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below: The page size is 4 KB = (1KB = bytes) and page table entry size at every level is 8 bytes.

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?

Consider the following ANSI C program. #include int main() { int i, j, count; count=0; i=0; for (j=-3; j = 0) && (i++)) count = count + j; } count = count +i; printf("%d", count); return 0; } Which on

Consider the following ANSI C program #include 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 foo(x-q, y, q); return foo(x

Consider a dynamic hashing approach for 4-bit integer keys: 1. There is a main hash table of size 4. 2. The 2 least significant bits of a key is used to index into the main hash table. 3. Initially, t

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 set of first 3 element

Consider the following ANSI C program. #include 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; } } printf("%d", *(arr[1]+9)); return 0;

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

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?

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

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

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); e

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

Consider the following ANSI C program: #include #include struct Node{ int value; struct Node *next;}; int main( ) { struct Node *boxE, *head, *boxN; int index=0; boxE=head= (struct Node *) malloc(size

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

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

Consider the following context-free grammar where the set of terminals is . The following is a partially-filled LL(1) parsing table. Which one of the following choices represents the correct combinati

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

Consider the following language: Which one of the following deterministic finite automata accepts ?

In a pushdown automaton , a transition of the form, where , represents Consider the following pushdown automaton over the input alphabet and stack alphabet . The number of strings of length 100 accept

Consider the following two statements about regular languages: S1: Every infinite regular language contains an undecidable language as a subset. S2: Every finite language is regular. Which one of the

Let denote an encoding of an automaton M. Suppose that . Which of the following languages is/are NOT recursive?

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

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

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 consecutive 1's by a 0

Consider the following deterministic finite automaton (DFA) The number of strings of length 8 accepted by the above automaton is _________

For a Turing machine M, denotes an encoding of M. Consider the following two languages. Which one of the following options is correct?