GATE 2026 CSE & IT

The size of the physical address space of a processor is $2^{32}$ bytes. The capacity of a cache memory unit is $2^{23}$ bytes. The cache block size is 128 bytes. The cache memory...

The antonym of the word protagonist is $\_\_\_\_$ .

For $n>1$, the maximum multiplicity of any eigenvalue of an $n \times n$ matrix with elements from $\mathbb{R}$ is

Match each addressing mode in List I with a data element or an element of a data structure (in a high-level language) in List II: List-I List-II P. Immediate 1. Element of an array...

Let $P, Q, R$ and $S$ be the attributes of a relation in a relational schema. Let $X \rightarrow Y$ indicate functional dependency in the context of a relational database, where $X...

Let $G(V, E)$ be a simple, undirected graph. A vertex cover of $G$ is a subset $V^{\prime} \subseteq V$ such that for every $(u, v) \in E, u \in V^{\prime \prime}$ or $v \in V^{\pr...

Consider the following recurrence relations: For all $n>1$, $$ \begin{aligned} & T_1(n)=4 T_1\left(\frac{n}{2}\right)+T_2(n) \\ & T_2(n)=5 T_2\left(\frac{n}{4}\right)+\theta\left(\...

Let $G(V, E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the numb...

Let $G(V, E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G$ is/are true?

Consider a knock-out women's badminton singles tournament where there are no ties. The loser in each game is eliminated from the tournament. Every player plays until she is defeate...

A student needs to enroll for a minimum of 60 credits. A student cannot enroll for more than 70 credits. The credits are divided amongst project and three distinct sets of courses...

'When the teacher is in the room, all students stand silently.' If the above statement is true, which one of the following statements is not necessarily true?

Combinatorics deals with problems involving counting. For example, "How many distinct arrangements of N distinct objects in M spaces on a circle are possible?" is a typical problem...

In Panel I of the figure below, the front view and top view of a structure are shown. Which one of the 3D structures shown in Panel II possesses the views shown in Panel I?

In the 2020 summer Olympics' Javelin throw finals, Neeraj Chopra exhibited a spectacular performance to win the gold medal. The silver medal was won by Jakub Vadlejch and the bronz...

An unbiased six-faced dice whose faces are marked with numbers $1,2,3,4,5$, and 6 is rolled twice in succession and the number on the top face is recorded each time. The probabilit...

Consider $4 \times 4$ matrices with their elements from $\{0,1\}$. The number of such matrices with even number of 1 s in every row and every column is

Consider a processor P whose instruction set architecture is the load-store architecture. The instruction format is such that the first operand of any instruction is the destinatio...

Which one of the following dependencies among the register operands of different instructions can cause a data hazard in a pipelined processor?

With respect to a TCP connection between a client and a server, which one of the following statements is true?

$$ \text { Consider the following two syntax-directed definitions SDD1 and SDD2 for type declarations. } $$ SDD1 Grammar(G1) $$ \text { Semantic Rules } $$ $$ \mathrm{D} \rightarro...

Which of the following statements is/are true with respect to the interaction of a web browser with a web server using HTTP 1.1?

Let $n>1$. Consider an $n \times n$ matrix $M$ with its elements from $\mathbb{R}$. Let the vector ( 0,1 , $0,0, \ldots, 0) \in \mathbb{R}^n$ be in the null space of $M$. Which of...

Consider the following Boolean expression of a function $F$ : $$ F(P, Q)=(\bar{P}+Q) \oplus(\bar{P} Q) $$ Which of the following expressions is/are equivalent to $F$ ?

Consider the 8-bit signed integers $X, Y$ and $Z$ represented using the sign-magnitude form. The binary representations of $X$ and $Y$ are as follows: $$ X: 10110100 \quad Y: 01001...

Consider the following C statements: char str1 = "Hello; / Statement S1 */ char str2 = "Hello;"; / Statement S2 */ int str3 = "Hello"; / Statement S3 */ Which of the following opti...

Which of the following statements is/are true?

With respect to deadlocks in an operating system, which of the following statements is/are FALSE?

In the context of relational database normalization, which of the following statements is/ are true?

Consider the function $f: \mathbb{R} \rightarrow \mathbb{R}$ defined as follows: $$ f(x)=\left\{\begin{array}{cc} c_1 e^x-c_2 \log _e\left(\frac{1}{x}\right), & \text { if } x>0 \\...

Consider a system consisting of $k$ instances of a resource $R$, being shared by 5 processes. Assume that each process requires a maximum of two instances of resource $R$ and a pro...

Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head. struct node{ int elt;...

Consider the implementation of sliding window protocol over a lossless link, with a window size of $W$ frames, where each frame is of size 1000 bits (including header). The bandwid...

Consider a system that has a cache memory unit and a memory management unit (MMU). The address input to the cache memory is a physical address. The MMU has a translation lookaside...

An undirected, unweighted, simple graph $G(V, E)$ is said to be 2 -colorable if there exists a function $c: V \rightarrow\{0,1\}$ such that for every $(u, v) \in E, c(u) \neq c(v)$...

An ISP having an address block 202.16.0.0/15 assigns a block of 6000 IP addresses to a client, using the classless internet domain routing (CIDR) super-netting approach. Which of t...

Let $G$ be an undirected graph, which is a path on 8 vertices. The number of matchings in $G$ is $\_\_\_\_$ (answer in integer)

Let $X$ be a random variable which takes values in the set $\{1,2,3,4,5,6,7,8\}$. Further, $\operatorname{Pr}(X=1)=\operatorname{Pr}(X=2)=\operatorname{Pr}(X=5)=\operatorname{Pr}(X...

The EX stage of a pipelined processor performs the memory read operations for LOAD instructions, and the operations for the arithmetic and logic instructions. Let $t_{E X}$ denote...

Consider the recursive functions represented by the following code segment: int bar(int n){ if (n == 1) return 0; else return 1 + bar(n/2); } int foo(int n){ if (n == 1) return 1;...

Consider the following program snippet. Assume that the program compiles and runs successfully. Further, assume that the fork( ) system call is always successful in creating a proc...

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is $\_\_...

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be defined as follows: $$ f(x)=\left(\frac{|x|}{2}-x\right)\left(x-\frac{|x|}{2}\right) $$ Which of the following statements is/are true?

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G(V, E)$ as input, where $d[v]$ and $f[v]$ are the discovery time and finishi...

Consider a hard disk with a rotational speed of 15000 rpm . The time to move the read/ write head from a track to its adjacent track is 1 millisecond. Initially, the head is on tra...

Consider a hash table $P[0,1, \ldots, 10]$ that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is $h(x)=(x+7) \b...

Let $n$ be an odd number greater than 100 . Consider a binary minheap with $n$ elements stored in an array $P$ whose index starts from 1. Which of the following indices of $P$ do/d...

Consider a relational database schema with two relations $R(P, Q)$ and $S(X, Y)$. Let $E=\{\langle u\rangle \mid \exists v \exists w\langle u, v\rangle \in R \wedge\langle v, w\ran...

Consider a Boolean function $F$ with the following minterm expression: $$ F(P, Q, R, S)=\Sigma m(1,2,3,4,5,7,10,12,13,14) $$ Which of the following options is/are the minimal sum-o...

Consider the following program in C: #include <stdio.h> void func(int i, int j) { if(i < j) { int i = 0; while (i < 10) { j += 2; i++; } } printf("%d", i); } int main() { int i = 9...

An urn contains one red ball and one blue ball. At each step, a ball is picked uniformly at random from the urn, and this ball together with another ball of the same color is put b...

Consider a 2-bit saturating up/down counter that performs the saturating up count when the input $P$ is 0 , and the saturating down count when $P$ is 1 . The Next State table of th...

The following sequence corresponds to the preorder traversal of a binary search tree: $$ 50,25,13,40,30,47,75,60,70,80,77 $$ The position of the element 60 in the postorder travers...

Consider a CPU that has to execute two types of processes. The first type, Actuators (A), requires a CPU burst of 6 seconds. The second type, Controllers (C), requires a CPU burst...

Consider a relational database schema with a relation $R(A, B, C, D)$. If $\{A, B\}$ and $\{A, C\}$ are the only two candidate keys of the relation $R$, then the number of superkey...

A TCP sender successfully establishes a connection with a TCP receiver and starts the transmission of segments. The TCP congestion control mechanism's slow-start threshold is set t...

Consider the real valued variables $X, Y$ and $Z$ represented using the IEEE 754 singleprecision floating-point format. The binary representations of $X$ and $Y$ in hexadecimal not...

Consider the following context-free grammar $G$ : $$ \begin{aligned} & S \rightarrow a b a A B A b b a \\ & A \rightarrow a a B B A b \mid b B a b a a \\ & B \rightarrow a B b \mid...

Let $L_1$ and $L_2$ be two languages over a finite alphabet, such that $L_1 \cap L_2$ and $L_2$ are regular languages. Which of the following statements is/are always true?

Let $M$ be a non-deterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be the number of states in the minimal determinist...

Consider the following grammar where $S$ is the start symbol, and $a$ and $b$ are terminal symbols. $$ S \rightarrow a S b S|b S| \in $$ Which of the following statements is/are tr...

Consider the following ANSI-C function. int func(int start, int end){ int length = end + 1 - start; if((length<1)| (start < 0)||(end<0)){ return(0); } if(length%3 == 0){ return(fun...

Consider a system with 1 MB physical memory and a word length of 1 byte. The system uses a direct mapped cache, with block numbers starting from 0 . The word with physical address...

Consider a system with a processor and a 4 KB direct mapped cache with block size of 16 bytes. The system has a 16 MB physical memory. Four words $\mathrm{P}, \mathrm{Q}, \mathrm{R...

Consider a function $f:(0,1) \rightarrow\{0,1\}$ defined as follows. For a real number $r \in(0,1), f(r)=1$ if the second digit after the decimal point in $r$ is one of the four di...

Consider the following two statements about interrupt handling mechanisms in a CPU. S1: In non-vectored interrupt mechanism, it usually takes more time to start the Interrupt Servi...

Consider the following functions, where $n$ is a positive integer. $$ n^{1 / 3}, \log (n), \log (n!), 2^{\log (n)} $$ Which one of the following options lists the functions in incr...

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $\Theta(n)$ ?

Consider an array $A$ of integers of size $n$. The indices of $A$ run from 1 to $n$. An algorithm is to be designed to check whether $A$ satisfies the condition given below. $\fora...

Consider an array $A=[10,7,8,19,41,35,25,31]$. Suppose the merge sort algorithm is executed on array $A$ to sort it in increasing order. The merge sort algorithm will carry out a t...

Consider three processes P1, P2, and P3 running identical code, as shown in the pseudocode below. A and B are two binary semaphores initialized to 1 and 0 , respectively. $X$ is a...

Water: P:: Food: Q Choose the P and Q combination from the options below to form a meaningful analogy.

Expedite, Hasten, Hurry, $\_\_\_\_$ . Fill the blank by choosing a word with a meaning similar to that of the words given above.

A day can only be cloudy or sunny. The probability of a day being cloudy is 0.5 , independent of the condition on other days. What is the probability that in any given four days, t...

The values of Stock A and Stock B on a particular day are Rs. 50 and Rs. 80, respectively. An investor invests Rs. 100 in Stock A and Rs. 80 in Stock B. He sells all the stocks the...

'When it is raining, peacocks dance.' Based only on this sentence, which one of the following options is necessarily true?

The figure in Panel I below is a grid of cells with four rows and four columns. The numbers on the top and on the left represent the number of cells that are to be shaded in that c...

An unbiased six-faced dice whose faces are marked with numbers $1,2,3,4,5$, and 6 is rolled twice in succession and the number on the top face is recorded each time. The probabilit...

For two different persons $x$ and $y$, the predicate $M(x, y)$ denotes that $x$ knows $y$. Consider the following statement. There is a person who does not know anyone else, but th...

The set T represents various traversals over binary tree. The set S represents the order of visiting nodes during a traversal. $$ \begin{array}{ll}\,\,\,\,\, \text { T } &\,\,\,\,\...

The probability density function $f(x)$ of a random variable $X$ which takes real values is $$ f(x)=\frac{1}{3 \sqrt{2 \pi}} \exp \left(-\frac{x^2}{18}\right), x \in(-\infty,+\inft...

$$ \text { In the context of DBMS, consider the two sets } \mathbf{T} \text { and } \mathbf{S} \text { given below. } $$ $$ \begin{array}{ll}\,\,\,\,\, \text { T } &\,\,\,\,\, \tex...

Which one of the following options is not a property of Boolean Algebra? Note: + is OR operation, • is AND operation, and ' is NOT operation

In C runtime environment, which one of the following is stored in heap?

Consider concurrent execution of two transactions $T 1$ and $T 2$ in a DBMS, both of which access a data object $A$. For these two transactions to not conflict on $A$, which one of...

Which one of the following protocols may need to broadcast some of its messages?

Which one of the following CPU scheduling algorithms cannot be preemptive?

Suppose an unbiased coin is tossed 6 times. Each coin toss is independent of all previous coin tosses. Let $E_1$ be the event that among the second, fourth, and sixth coin tosses,...

Let $R$ be a binary relation on the set $\{1,2, \ldots, 10\}$, where $(x, y) \in, R$ if the product of $x$ and $y$ is square of an integer. Which of the following properties is/are...

For a real number $a$, let $I(a)=\int\limits_{-1}^1\left(3 x^2-a x+1\right) d x$. Which of the following statements is/are true?

In a system, numbers are represented using 4-bit two's complement form. Consider four numbers $N 1=1011, N 2=1101, N 3=1010$ and $N 4=1001$ in the system. Which of the following op...

To keep track of free blocks in a file system, one of the two approaches is generally used - using bitmaps (bit vectors) or using linked lists. Consider that the linked list approa...

Consider the system of linear equations given below. $$ \begin{aligned} a x+y & =b \\ 16 x+a y & =24 \end{aligned} $$ Suppose the values of a and b are chosen such that the system...

If an IP network uses a subnet mask of 255.255 .240 .0 , the maximum number of IP addresses that can be assigned to network interfaces is $\_\_\_\_$ . (answer in integer)

Consider a complete graph $K_n$ with $n$ vertices ( $n>4$ ). Note that multiple spanning trees can be constructed over $K_n$. Each of these spanning trees is represented as a set o...

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$, which one of the following options gives the worst case time...

In the context of schema normalization in relational DBMS, consider a set $F$ of functional dependencies. The set of all functional dependencies implied by $F$ is called the closur...

An index in a DBMS is said to be dense if an index entry appears for every searchkey value in the indexed file. Otherwise it is called a sparse index. Consider the following two st...

Consider a binary search tree (BST) with $n$ leaf nodes ( $n>0$ ). Given any node $V$, the key present in the node is denoted as $\operatorname{Val}(V)$. All the keys present in th...

A system has a Translation Lookaside Buffer (TLB) that has a reach of 1 MB . TLB reach is defined as the total amount of physical memory that can be accessed through the TLB entrie...

A non-pipelined instruction execution unit that operates at 1.6 GHz clock takes an average of 5 clock cycles to complete the execution of an instruction. To improve the performance...

Consider a new TCP connection between a sender and a receiver. The receiver advertised window is constant at 48 KB , the maximum segment size (MSS) is 2 KB , and the slow start thr...

It is necessary to design a link-layer protocol between two hosts that are directly connected over a lossless link of length 3000 kilometers. Assume that the link bandwidth is $10^...

Consider the following 4-variable Boolean function $$ F(A, B, C, D)=\Sigma m(0,1,2,3,8,9,10,11) $$ Consider $A$ as MSB, $D$ as LSB. Which one of the following options represents th...

Consider a processor that has 16 general purpose registers and it uses 2-byte instruction format for all its instructions. Variable-sized opcodes are permitted. There are three dif...

Consider a stack $S$ and a queue $Q$. Both of them are initially empty and have the capacity to store ten elements each. The elements $1,2,3,4$, and 5 arrive one by one, in that or...

Consider contiguous allocation of physical memory to processes using variable partitioning scheme. Suppose there are 8 holes in the memory of sizes $20 \mathrm{~KB}, 4 \mathrm{~KB}...

Consider the transmission of data bits 110001011 over a link that uses Cyclic Redundancy Check (CRC) code for error detection. If the generator bit pattern is given to be 1001, whi...

Consider the canonical $L R(0)$ parsing of the grammar below using terminals $\{a, b, c\}$ and non-terminals $\{A, B, C, S\}$ with $S$ as the start symbol. $$ \begin{aligned} & S \...

The keys $5,28,19,15,26,33,12,17,10$ are inserted into a hash table using the hash function $h(k)=k \bmod 9$. The collisions are resolved by chaining. After all the keys are insert...

The 32-bit IEEE 754 single precision representation of a number is 0xC2710000. The number in decimal representation is $\_\_\_\_$ . (rounded off to two decimal places)

Consider a file of size 4 million bytes being transferred between two hosts connected via a path consisting of three consecutive links of bandwidth $2 \mathrm{Mbps}, 500 \mathrm{kb...

A lexical analyzer uses the following token definitions letter → [A - Za - z] digit → [0-9] id → letter (letter $\mid$ digit)* number → digit $^{+}$ ws → (blank | tab | newline) ${...

Consider the following ANSI-C program. #include <stdio.h> int main( ) { int *ptr, a, b, c; a=5; b=11; c=20; ptr=&a; *ptr=c; ptr=&c; a=*(&b); c=*ptr-a; printf("%d",c); return(0); }...

The determinant of a $4 \times 4$ matrix $A$ is 3 . The value of the determinant of $2 A$ is $\_\_\_\_$ . (answer in integer)

Which one of the following statements is equivalent to the following assertion? Turing machine $M$ decides the language $L \subseteq\{0,1\}$.

Let $\Sigma=\{a, b, c, d\}$ and let $L=\left\{a^i b^j c^k d^l \mid i, j, k, l \geq 0\right\}$. Which of the following constraints ensure(s) that the language $L$ is context-free?

Which of the following grammars is/are ambiguous?