GATE CSE 2026 PYQ

Consider an array . Suppose the merge sort algorithm is executed on array to sort it in increasing order. The merge sort algorithm will carry out a total of merge operations. A merge operation on sort

Consider the following functions, where is a positive integer. Which one of the following options lists the functions in increasing order of asymptotic growth rate? Note: Assume the base of log to be

Consider a table , where the elements , represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive form

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

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

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph as input, where and are the discovery time and finishing time, respectively, of the vertex . Suppo

Consider the following recurrence relations: For all , Assume that for all and . Which one of the following options is correct?

Let 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 number of edges in that path. Let

Consider an array of integers of size . The indices of run from to . An algorithm is to be designed to check whether satisfies the condition given below. such that Which one of the following gives the

Consider a complete graph with vertices ( ). Note that multiple spanning trees can be constructed over . Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between

Let be a weighted directed acyclic graph with edges and vertices. Given and a source vertex in , which one of the following options gives the worst case time complexity of the fastest algorithm to fin

Consider the canonical parsing of the grammar below using terminals and non-terminals with as the start symbol. Which one of the following options gives the number of shift-reduce conflicts that will

A lexical analyzer uses the following token definitions For the string given below, the number of tokens (excluding ws) that will be produced by the lexical analyzer is ________. (answer in integer)

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

Consider the following three ANSI-C programs, and . Which one of the following statements is true?

Consider the control flow graph given below. Which one of the following options is the set of live variables at the exit point of each basic block?

Consider the following C statements: char *str1 = "Hello; /* Statement S1 */ char *str2 = "Hello;"; /* Statement S2 */ int *str3 = "Hello"; /* Statement S3 */ Which of the following options is/are cor

Consider the following two syntax-directed definitions and for type declarations. is the start symbol, and int, float and id are the three terminals. The non-terminal is the same as and the non-termin

Consider the control flow graph shown in the figure. Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B and B ? Note: All

Which of the following statements is/are true?

Which of the following grammars is/are ambiguous?

It is necessary to design a link-layer protocol between two hosts that are directly connected over a lossless link of length kilometers. Assume that the link bandwidth is bits per second and that the

If an IP network uses a subnet mask of , the maximum number of IP addresses that can be assigned to network interfaces is ________. (answer in integer)

Consider the transmission of data bits over a link that uses Cyclic Redundancy Check (CRC) code for error detection. If the generator bit pattern is given to be , which one of the following options sh

Consider a new TCP connection between a sender and a receiver. The receiver advertised window is constant at KB, the maximum segment size (MSS) is KB, and the slow start threshold for TCP congestion c

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

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

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

An ISP having an address block assigns a block of IP addresses to a client, using the classless internet domain routing (CIDR) super-netting approach. Which of the following address blocks can be assi

Consider the implementation of sliding window protocol over a lossless link, with a window size of frames, where each frame is of size bits (including header). The bandwidth of the link is and the one

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 to segments. Assume t

Consider a file of size million bytes being transferred between two hosts connected via a path consisting of three consecutive links of bandwidth Mbps , kbps , and Mbps , respectively. All processing

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 approach is used to keep t

Consider a processor whose instruction set architecture is the load-store architecture. The instruction format is such that the first operand of any instruction is the destination operand. Which one o

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

Match each addressing mode in with a data element or an element of a data structure (in a high-level language) in :

Consider the following two statements about interrupt handling mechanisms in a CPU. : In non-vectored interrupt mechanism, it usually takes more time to start the Interrupt Service Routine (ISR) when

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 denote the time taken by the EX stage

Consider a system with a processor and a KB direct mapped cache with block size of bytes. The system has a MB physical memory. Four words , and S are accessed by the processor in the same order times.

Consider a processor that has general purpose registers and it uses -byte instruction format for all its instructions. Variable-sized opcodes are permitted. There are three different types of instruct

The size of the physical address space of a processor is bytes. The capacity of a cache memory unit is bytes. The cache block size is bytes. The cache memory unit can be built as a direct mapped cache

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

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

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

Consider a relational database schema with two relations and . Let be a tuple relational calculus expression. Which one of the following relational algebraic expressions is equivalent to ?

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

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

In the context of DBMS, consider the two sets and given below. Which one of the following is the correct match from to ?

Let and be the attributes of a relation in a relational schema. Let indicate functional dependency in the context of a relational database, where . Which of the following options is/are always true?

An index in a DBMS is said to be dense if an index entry appears for every search-key value in the indexed file. Otherwise it is called a sparse index. Consider the following two statements. : A hash

Consider a relational database schema with a relation . If and are the only two candidate keys of the relation , then the number of superkeys of relation is ________. (answer in integer)

Consider concurrent execution of two transactions and in a DBMS, both of which access a data object . For these two transactions to not conflict on , which one of the following statements must be true

Consider a Boolean function with the following minterm expression: Which of the following options is/are the minimal sum-of-products expression(s) of ?

Consider the -bit signed integers and represented using the sign-magnitude form. The binary representations of and are as follows: Which of the following operations to compute result(s) in an arithmet

The -bit single precision representation of a number is . The number in decimal representation is ________. (rounded off to two decimal places)

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

Consider the following Boolean expression of a function : Which of the following expressions is/are equivalent to ?

Consider a -bit saturating up/down counter that performs the saturating up count when the input is , and the saturating down count when is . The Next State table of the counter is as shown. The counte

Consider the following -variable Boolean function Consider as MSB, as LSB. Which one of the following options represents the minimal sum of products form for the above function? Note: is OR operation,

Consider the real valued variables and represented using the IEEE singleprecision floating-point format. The binary representations of and in hexadecimal notation are as follows: Let . Which one of th

Consider the digital circuit shown below with two input lines and , two select lines and , and an output line . The blocks and represent active high decoder and -to- multiplexer, respectively. Out of

In a system, numbers are represented using -bit two's complement form. Consider four numbers and in the system. Which of the following operations will result in arithmetic overflow?

The probability density function of a random variable which takes real values is Which one of the following statements is correct about the random variable ?

Suppose an unbiased coin is tossed times. Each coin toss is independent of all previous coin tosses. Let be the event that among the second, fourth, and sixth coin tosses, there are at least two heads

Let be an undirected graph, which is a path on vertices. The number of matchings in is ________. (answer in integer)

Let . Consider an matrix with its elements from . Let the vector be in the null space of . Which of the following options is/are always correct?

For two different persons and , the predicate denotes that knows . Consider the following statement. There is a person who does not know anyone else, but that person is known by everyone else. Which o

Let be a random variable which takes values in the set . Further, and . The expected value of , denoted by , is equal to ________. (rounded off to two decimal places)

Consider the function defined as follows: where . If is continuous at , then ________. (answer in integer)

An undirected, unweighted, simple graph is said to be -colorable if there exists a function such that for every . Which of the following statements about -colorable graphs is/are true?

Let be defined as follows: Which of the following statements is/are true?

Let be a simple, undirected graph. A vertex cover of is a subset such that for every or . Let the size of the smallest vertex cover in be . Let be any vertex cover of size . For a vertex , which of th

Let be a binary relation on the set , where if the product of and is square of an integer. Which of the following properties is/are satisfied by ?

For a real number , let . Which of the following statements is/are true?

Consider the system of linear equations given below. Suppose the values of and are chosen such that the system of linear equations produce multiple solutions. Then the product of and is ________. (ans

The determinant of a matrix is . The value of the determinant of is ________. (answer in integer)

Consider a function defined as follows. For a real number , if the second digit after the decimal point in is one of the four digits and . Otherwise, is equal to . The number of points in at which is

For , the maximum multiplicity of any eigenvalue of an matrix with elements from is

Consider matrices with their elements from . The number of such matrices with even number of s in every row and every column is

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 back in the urn. The

Consider contiguous allocation of physical memory to processes using variable partitioning scheme. Suppose there are holes in the memory of sizes , , and . Assume that no two holes are adjacent. Two p

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

Consider three processes , and running identical code, as shown in the pseudocode below. and are two binary semaphores initialized to and , respectively. is a shared variable initialized to . Each lin

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

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 buffer (TLB). Assume

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 process. int main () { in

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

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

Consider a system consisting of instances of a resource , being shared by processes. Assume that each process requires a maximum of two instances of resource and a process can request or release only

The set represents various traversals over binary tree. The set represents the order of visiting nodes during a traversal. Which one of the following is the correct match from to ?

The following sequence corresponds to the preorder traversal of a binary search tree : The position of the element in the postorder traversal of is ________ . (answer in integer) Note: The position be

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(func(start+1, end)); }else if(len

Consider a stack and a queue . Both of them are initially empty and have the capacity to store ten elements each. The elements , and arrive one by one, in that order. When an element arrives, it is as

Consider a hash table that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is . Consider the following sequence of insertions perform

Consider a binary search tree (BST) with leaf nodes . Given any node , the key present in the node is denoted as . All the keys present in the given BST are distinct. The keys belong to the set of rea

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; struct node *next;

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; else return 1 + fo

Let be an odd number greater than . Consider a binary minheap with elements stored in an array whose index starts from . Which of the following indices of do/does NOT correspond to any leaf node of th

The keys are inserted into a hash table using the hash function . The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is ________. (answer in inte

Consider the following ANSI-C program. #include 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 output of this program is __

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 nodes is ________.(answer in integer)

Let be the set of all integers from to . Consider any order of insertion of the elements of into a binary search tree that creates a complete binary tree. Which one of the following elements can NEVER

Consider the following program in C: #include 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, j = 10; func(i, j); return 0

Which one of the following statements is equivalent to the following assertion? Turing machine decides the language

Consider the following two finite automata and . Which of the following statements is/are true?

Consider the following context-free grammar . In the above grammar, is the start symbol, and are terminal symbols, and and are non-terminal symbols. Let be the language generated by the grammar . For

Let and let . Which of the following constraints ensure(s) that the language is context-free?

Consider the following grammar where is the start symbol, and and are terminal symbols. Which of the following statements is/are true?

Let be a nondeterministic finite automaton (NFA) with states over a finite alphabet. Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) t

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