GATE CSE 2025 PYQ

Consider the following recurrence relation: Which ONE of the following options is CORRECT?

Let be any undirected graph with positive edge weights, and be a minimum spanning tree of . For any two vertices, and , let and be the shortest distances between and in and , respectively. Which ONE o

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph is/are TRUE?

Let be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum s

The maximum value of such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is _________. (Answer in integer)

Consider the following algorithm someAlgo that takes an undirected graph as input. 1. Let be any vertex in . Run BFS on starting at . Let be a vertex in at maximum distance from as given by the BFS. 2

Let be an undirected and unweighted graph with 100 vertices. Let denote the number of edges in a shortest path between vertices and in . Let the maximum value of , such that , be 30. Let be any breadt

Which ONE of the following techniques used in compiler code optimization uses live variable analysis?

Given the following syntax-directed translation rules: Which ONE is the CORRECT option among the following?

Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is _________. (Answer in integer) 1001: i = 1 1002: j = 1 1003: t1 = 10*i 1004: t2

Which ONE of the following statements is FALSE regarding the symbol table?

Consider the following statements about the use of backpatching in a compiler for intermediate code generation: (I) Backpatching can be used to generate code for Boolean expression in one pass. (II) B

Which of the following statement(s) is/are TRUE while computing and during top-down parsing by a compiler?

Consider the 3-way handshaking protocol for TCP connection establishment. Let the three packets exchanged during the connection establishment be denoted as P1, P2, and P3, in order. Which of the follo

Suppose a message of size 15000 bytes is transmitted from a source to a destination using IPv4 protocol via two routers as shown in the figure. Each router has a defined maximum transmission unit (MTU

Consider the routing protocols given in List I and the names given in List II: For matching of items in List I with those in List II, which ONE of the following options is CORRECT?

Identify the ONE CORRECT matching between the OSI layers and their corresponding functionalities as shown.

A packet with the destination IP address 145.36.109.70 arrives at a router whose routing table is shown. Which interface will the packet be forwarded to?

Suppose we are transmitting frames between two nodes using the Stop-and-Wait protocol. The frame size is 3000 bits. The transmission rate of the channel is 2000 bps (bits/second) and the propagation d

A machine receives an IPv4 datagram. The protocol field of the IPv4 header has the protocol number of a protocol X. Which ONE of the following is NOT a possible candidate for X?

Consider a network that uses Ethernet and IPv4. Assume that IPv4 headers do not use any options field. Each Ethernet frame can carry a maximum of 1500 bytes in its data field. A UDP segment is transmi

Consider the following statements: (i) Address Resolution Protocol (ARP) provides a mapping from an IP address to the corresponding hardware (link-layer) address. (ii) A single TCP segment from a send

Given a computing system with two levels of cache (L1 and L2) and a main memory. The first level (L1) cache access time is 1 nanosecond (ns) and the "hit rate" for L1 cache is 90% while the processor

Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. The processor needs t

A 5-stage instruction pipeline has stage delays of 180, 250, 150, 170, and 250, respectively, in nanoseconds. The delay of an inter-stage latch is 10 nanoseconds. Assume that there are no pipeline sta

An application executes number of instructions in 6.3 seconds. There are four types of instructions, the details of which are given in the table. The duration of a clock cycle in nanoseconds is ______

For a direct-mapped cache, 4 bits are used for the tag field and 12 bits are used to index into a cache block. The size of each cache block is one byte. Assume that there is no other information store

A partial data path of a processor is given in the figure, where , , and are 32-bit registers. Which option(s) is/are CORRECT related to arithmetic operations using the data path as shown?

Consider a memory system with 1M bytes of main memory and 16K bytes of cache memory. Assume that the processor generates 20-bit memory address, and the cache block size is 16 bytes. If the cache uses

A computer has a memory hierarchy consisting of two-level cache (L1 and L2) and a main memory. If the processor needs to access data from memory, it first looks into L1 cache. If the data is not found

Which of the following is/are part of an Instruction Set Architecture of a processor?

A processor has 64 general-purpose registers and 50 distinct instruction types. An instruction is encoded in 32-bits. What is the maximum number of bits that can be used to store the immediate operand

Consider the following relational schema: Which of the following options is/are correct SQL query/queries to retrieve the names of the students enrolled in course number (i.e. courseno) 1470?

An audit of a banking transactions system has found that on an earlier occasion, two joint holders of account attempted simultaneous transfers of Rs. 10000 each from account to account . Both transact

Consider the database transactions and , and data items and . Which of the schedule(s) is/are conflict serializable?

Consider two relations describing teams and players in a sports league: are team-id and team-name, respectively denote player-id, player-name and the team-id of the player, respectively Which ONE of t

Consider the following relational schema along with all the functional dependencies that hold on them. Which of the following statement(s) is/are TRUE?

Consider the following database tables of a sports league. player(pid,pname,age) coach(cid,cname) team(tid,tname,city,cid) members(pid,tid) An instance of the table and an SQL query are given. The val

A schedule of three database transactions , , and is shown. and denote read and write of data item by transaction , . The transaction aborts at the end. Which other transaction(s) will be required to

Consider a relational schema , with functional dependencies , . The relation is decomposed into two relations, and . Which of the following statement(s) is/are TRUE?

Consider the following logic circuit diagram. Which is/are the CORRECT option(s) for the output function ?

In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ________. (Answer in integer)

The following two signed 2's complement numbers (multiplicand and multiplier ) are being multiplied using Booth's algorithm: The total number of addition and subtraction operations to be performed is

Consider the following four-variable Boolean function in sum-of-product form . Where the value of the function is computed by considering as a 4-bit binary number, where denotes the most significant b

Three floating point numbers are stored in three registers , respectively in IEEE 754 single precision format as given below in hexadecimal: Which of the following option(s) is/are CORRECT?

The number can be represented as 1010 in 4-bit 2's complement representation. Which of the following is/are CORRECT 2's complement representation(s) of ?

Given the following Karnaugh Map for a Boolean function : Which one or more of the following Boolean expression(s) represent(s) ?

Consider the given sequential circuit designed using D-Flip-flops. The circuit is initialized with some value (initial state). The number of distinct states the circuit will go through before returnin

Which of the following Boolean algebraic equation(s) is/are CORRECT?

Let be a 3-variable Boolean function that produces output as '1' when at least two of the input variables are '1'. Which of the following statement(s) is/are CORRECT, where are Boolean variables?

Consider a probability distribution given by the density function . The probability that lies between 2 and 3, i.e., is _________. (rounded off to three decimal places)

Let , , and be non-singular matrices of order 3 satisfying the equations Which ONE of the following is the value of the determinant of ?

Let be a 2x2 matrix as given: What are the eigenvalues of the matrix ?

Suppose a 5-bit message is transmitted from a source to a destination through a noisy channel. The probability that a bit of the message gets flipped during transmission is 0.01. Flipping of each bit

The value of such that , satisfying the equation is

is the set of non-negative integers. Let be the set of functions from to itself. For any two functions, , we define for every number in . Which of the following is/are CORRECT about the mathematical s

Let be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?

A quadratic polynomial over complex numbers is said to be square invariant if . Suppose from the set of all square invariant quadratic polynomials we choose one at random. The probability that the roo

Consider the given function . If the function is differentiable everywhere, the value of must be ________. (rounded off to one decimal place)

then which ONE of the following is ?

A box contains 5 coins: 4 regular coins and 1 fake coin. When a regular coin is tossed, the probability and for a fake coin, . You pick a coin at random and toss it twice, and get two heads. The proba

is a function from to , is a function from to , and their composition defined as is a mapping from to . If and are onto (surjective) functions, which ONE of the following is TRUE about the function ?

Consider a system of linear equations where and . Suppose has an decomposition, , where Which of the following statement(s) is/are TRUE?

Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: "Everyone has exactly one mother"? The meanings of the predicates used are: is the mother of

Consider the given system of linear equations for variables and , where is a real-valued constant. Which of the following option(s) is/are CORRECT?

Let be the set of all ternary strings defined over the alphabet . Consider all strings in that contain at least one occurrence of two consecutive symbols, that is, "aa", "bb" or "cc". The number of su

The unit interval is divided at a point chosen uniformly distributed over in into two disjoint subintervals. The expected length of the subinterval that contains 0.4 is ___________. (rounded off to tw

A computer system supports a logical address space of bytes. It uses two-level hierarchical paging with a page size of 4096 bytes. A logical address is divided into a -bit index to the outer page tabl

A disk of size bytes is divided into blocks of bytes. A file is stored in the disk using linked allocation. Each data block reserves 4 bytes to store the pointer to the next data block. The link part

Consider a demand paging system with three frames, and the following page reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2. The contents of the frames are as follows initially and after each reference (fro

Processes arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm

Suppose in a multiprogramming environment, the following C program segment is executed. A process goes into I/O queue whenever an I/O related operation is performed. Assume that there will always be a

Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum n

A computer has two processors, and . Four processes with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The schedu

consists of all active processes in an operating system. consists of single instances of distinct types of resources in the system. The resource allocation graph has the following assignment and claim

In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows: T

In a -tree where each node can hold at most four key values, a root to leaf path consists of the following nodes: The *-marked keys signify that these are data entries in a leaf. Assume that a pointer

An array of length with distinct elements is said to be bitonic if there is an index such that is sorted in the non-decreasing order and is sorted in the non-increasing order. Which ONE of the followi

Consider the following tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the tree. Which of the following options(s) is/are CORRECT?

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures: P: Unsorted doubly linked list with poi

The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node. Suppose a Min-Heap stores 32 keys. The height of is _____________. (Answer in i

int x=126,y=105; do { if(x>y) x=x-y; else y=y-x; } while(x!=y); printf("%d",x); The output of the given C code segment is ________. (Answer in integer)

In a double hashing scheme, and are the auxiliary hash functions. The size of the hash table is 11. The hash function for the -th probe in the open address table is The following keys are inserted in

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having distinct integers?

The pseudocode of a function fun() is given below: fun(int A[0,...,n-1]) { for i=0 to n-2 for j=0 to n-i-2 if (A[j] > A[j+1]) then swap A[j] and A[j+1]} } Let be an array storing 30 distinct integers

Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct. We wish to augment the st

Let LIST be a datatype for an implementation of linked list defined as follows: typedef struct list { int data; struct list *next; } LIST; Suppose the program has created two linked lists, L1 and L2,

Consider the following C program: #include int gate(int n) { int d, t, newnum, turn; newnum = turn = 0; t=1; while(n >= t) t *= 10; t /= 10; while(t > 0) { d = n / t; n = n % t; t /= 10; if(turn) newn

Consider an unordered list of distinct integers. What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

Consider the following C program: #include void stringcopy(char *, char *); int main(){ char a[30] = "@#Hello World!"; stringcopy(a, a + 2); printf("%s ", a); return 0; } void stringcopy(char *s, char

#include int foo(int S[],int size){ if(size == 0) return 0; if(size == 1) return 1; if(S[0] != S[1]) return 1+foo(S+1,size-1); return foo(S+1,size-1); } int main(){ int A[]={0,1,2,2,2,0,0,1,1}; printf

Consider the following C program: #include int main(){ int a; int arr[5] = {30,50,10}; int *ptr; ptr = &arr[0] + 1; a = *ptr; (*ptr)++; ptr++; printf("%d", a + (*ptr) + arr[1]); return 0; } The output

Suppose the values 10, -4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let be the resulting binary search tree. The number of edges in the path from th

Consider a binary tree in which every node has either zero or two children. Let be the number of nodes in . Which ONE of the following is the number of nodes in that have exactly two children?

#include void foo(int *p, int x) { *p = x; } int main() { int *z; int a = 20, b = 25; z = &a; foo(z, b); printf("%d", a); return 0; } The output of the given C program is __________. (Answer in intege

Consider the following C program: #include int g(int n) { return (n+10); } int f(int n) { return g(n*2); } int main() { int sum, n; sum=0; for (n=1; n<3; n++) sum += g(f(n)); printf ("%d", sum); retur

Consider a finite state machine (FSM) with one input and one output , represented by the given state transition table. The minimum number of states required to realize this FSM is _________. (Answer i

Consider two grammars and with the production rules given below: where are the terminals. Which of the following option(s) is/are CORRECT?

Given a Context-Free Grammar as follows: Which ONE of the following statements is TRUE?

Let . For , let be the product of symbols in modulo 7. We take , where is the null string. For example, . Define The number of states in a minimum state DFA for is ___________. (Answer in integer)

Consider the two lists List I and List II given below: For matching of items in List I with those in List II, which of the following option(s) is/are CORRECT?

Consider the following deterministic finite automaton (DFA) defined over the alphabet, . Identify which of the following language(s) is/are accepted by the given DFA.

Consider the following context-free grammar , where , , and are the variables (non-terminals), and are the terminal symbols, is the start variable, and the rules of are described as: Which ONE of the

A regular language is accepted by a non-deterministic finite automaton (NFA) with states. Which of the following statement(s) is/are FALSE?

Consider the following two languages over the alphabet , where and are natural numbers: Which ONE of the following statements is CORRECT?

Let be Context-Free Grammars (CFGs) and be a regular expression. For a grammar , let denote the language generated by . Which ONE among the following questions is decidable?

Consider the following two languages over the alphabet : Which ONE of the following statements is CORRECT?

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

Let . For , and , let denote the number of occurrences of in . Which one or more of the following option(s) define(s) regular language(s)?