GATE CSE 2024 PYQ

Given an integer array of size , we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and compa

Let be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in has even weight. Which of the following statements is/are TRUE for every suc

The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is _________

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

The number of distinct minimum-weight spanning trees of the following graph is _______

Let be the recurrence relation defined as follows: Which one of the following statements is TRUE?

Consider the following expression: . The following sequence shows the list of triples representing the given expression, with entries missing for triples (1), (3), and (6). Which one of the following

Consider the following syntax-directed definition (SDD). Given "MMLK" as the input, which one of the following options is the CORRECT value computed by the SDD (in the attribute S.val)?

Which of the following is/are Bottom-Up Parser(s)?

Consider the following grammar , with as the start symbol. The grammar has three incomplete productions denoted by (1), (2), and (3). The set of terminals is . The FIRST and FOLLOW sets of the differe

Consider the following two sets: Which one of the following options is the CORRECT match from Set X to Set Y ?

Consider the following pseudo-code. Which of of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively?

Which of the following statements is/are FALSE?

Which of the following fields is/are modified in the IP header of a packet going out of a network address translation (NAT) device from an internal network to an external network?

Which of the following statements about IPv4 fragmentation is/are TRUE?

Node X has a TCP connection open to node Y. The packets from X to Y go through an intermediate IP router R. Ethernet switch S is the first switch on the network path between X and R. Consider a packet

Which of the following fields of an IP header is/are always modified by any router before it forwards the IP packet?

TCP client P successfully establishes a connection to TCP server . Let denote the sequence number in the SYN sent from to . Let denote the acknowledgement number in the SYN ACK from Q to P. Which of t

A user starts browsing a webpage hosted at a remote server. The browser opens a single TCP connection to fetch the entire webpage from the server. The webpage consists of a top-level index page with m

Which one of the following CIDR prefixes exactly represents the range of IP addresses 10.12.2.0 to 10.12.3.255?

Consider an Ethernet segment with a transmission speed of bits/sec and a maximum segment length of 500 meters. If the speed of propagation of the signal in the medium is meters/sec, then the minimum f

Consider a network path between nodes and via router . Node sends a file of size bytes to via this path by splitting the file into chunks of bytes each. Node sends these chunks one after the other wit

Consider the entries shown below in the forwarding table of an router. Each entry consists of an IP prefix and the corresponding next hop router for packets whose destination IP address matches the pr

Consider a TCP connection operating at a point of time with the congestion window of size 12 MSS (Maximum Segment Size), when a timeout occurs due to packet loss. Assuming that all the segments transm

Consider sending an IP datagram of size 1420 bytes (including 20 bytes of IP header) from a sender to a receiver over a path of two links with a router between them. The first link (sender to router)

Consider two set-associative cache memory architectures: WBC, which uses the write back policy, and WTC, which uses the write through policy. Both of them use the LRU (Least Recently Used) block repla

A processor uses a 32-bit instruction format and supports byte-addressable memory access. The ISA of the processor has 150 distinct instructions. The instructions are equally divided into two types, n

An instruction format has the following structure: Instruction Number: Consider the following sequence of instructions to be executed in a pipelined processor: I1: DIV R3, R1, R2 I2: SUB R5, R3, R4 I3

Consider a disk with the following specifications: rotation speed of 6000 RPM, average seek time of 5 milliseconds, 500 sectors/track, 512-byte sectors. A file has content stored in 3000 sectors locat

Which one of the following statements is FALSE?

Consider a computer with a 4 MHz processor. Its DMA controller can transfer 8 bytes in 1 cycle from a device to main memory through cycle stealing at regular intervals. Which one of the following is t

Consider a 5-stage pipelined processor with Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), and Register Writeback (WB) stages. Which of the following statements ab

A given program has 25% load/store instructions. Suppose the ideal CPI (cycles per instruction) without any memory stalls is 2. The program exhibits 2% miss rate on instruction cache and 8% miss rate

The baseline execution time of a program on a 2 GHz single core machine is 100 nanoseconds (ns). The code corresponding to 90% of the execution time can be fully parallelized. The overhead for using a

Consider a 512 GB hard disk with 32 storage surfaces. There are 4096 sectors per track and each sector holds 1024 bytes of data. The number of cylinders in the hard disk is ____

A processor with 16 general purpose registers uses a 32-bit instruction format. The instruction format consists of an opcode field, an addressing mode field, two register operand fields, and a 16-bit

A non-pipelined instruction execution unit operating at 2 GHz takes an average of 6 cycles to execute an instruction of a program P. The unit is then redesigned to operate on a 5-stage pipeline at 2 G

A functional dependency is termed as a useful functional dependency if and only if it satisfies all the following three conditions: is not the empty set. is not the empty set. Intersection of and is t

Which of the following file organizations is/are I/O efficient for the scan operation in DBMS?

Which of the following statements about the Two Phase Locking (2PL) protocol is/are TRUE?

Consider the following read-write schedule over three transactions , and , where the subscripts in the schedule indicate transaction IDs: Which of the following transaction schedules is/are conflict e

Once the DBMS informs the user that a transaction has been successfully completed, its effect should persist even if the system crashes before all its changes are reflected on disk. This property is c

Consider the following two relations, and : The total number of tuples obtained by evaluating the following expression is ____

Let S be the specification: "Instructors teach courses. Students register for courses. Courses are allocated classrooms. Instructors guide students." Which one of the following ER diagrams CORRECTLY r

In the context of owner and weak entity sets in the ER (Entity-Relationship) data model, which one of the following statements is TRUE?

The relation schema, Person(pid,city), describes the city of residence for every person uniquely identified by pid. The following relational algebra operators are available: selection, projection, cro

The symbol indicates functional dependency in the context of a relational database. Which of the following options is/are TRUE?

Which of the following statements about a relation R in first normal form (1NF) is/are TRUE ?

Consider 4-variable functions expressed in sum-of-minterms form as given below. With respect to the circuit given above, which of the following options is/are CORRECT?

Consider a digital logic circuit consisting of three 2-to-1 multiplexers M1, M2, and M3 as shown below. and are inputs of . and are inputs of . , and are select lines of , and , respectively. For an i

Consider a Boolean expression given by . Which of the following statements is/are CORRECT?

Consider a system that uses 5 bits for representing signed integers in 2's complement format. In this system, two integers and are represented as and . Which one of the following operations will resul

Which of the following is/are EQUAL to 224 in radix-5 (i.e., base-5) notation?

Consider the circuit shown below where the gates may have propagation delays. Assume that all signal transitions occur instantaneously and that wires have no delays. Which of the following statements

The format of a single-precision floating-point number as per the IEEE 754 standard is: Choose the largest floating-point number among the following options.

For a Boolean variable , which of the following statements is/are FALSE?

Let and be random variables, not necessarily independent, that take real values in the interval . Let and let the mean values of be , respectively. Which one of the following statements is TRUE?

Let and be the following propositions: : Fail grade can be given. : Student scores more than marks. Consider the statement: "Fail grade cannot be given when student scores more than marks." Which one

Let be a function such that , where is the set of all real numbers. The set of all points where is NOT differentiable is

Let be an matrix over the set of all real numbers . Let be a matrix obtained from by swapping two rows. Which of the following statements is/are TRUE?

Consider the operators and defined by , for positive integers. Which of the following statements is/are TRUE?

The product of all eigenvalues of the matrix is

Let be the group of integers with addition modulo as the group operation. The number of elements in the group that are their own inverses is

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let be any graph with vertices and chromatic number . Which of the following statements is/are

Let and be two events in a probability space with , and . Which of the following statements is/are TRUE?

Consider a permutation sampled uniformly at random from the set of all permutations of for some . Let be the event that 1 occurs before 2 in the permutation, and the event that 3 occurs before 4 . Whi

A bag contains 10 red balls and 15 blue balls. Two balls are drawn randomly without replacement. Given that the first ball drawn is red, the probability (rounded off to 3 decimal places) that both bal

The number of edges present in the forest generated by the DFS traversal of an undirected graph with 100 vertices is 40 . The number of connected components in is ____

Let be a directed graph and a depth first search (DFS) spanning tree in that is rooted at a vertex . Suppose is also a breadth first search (BFS) tree in , rooted at . Which of the following statement

Let and be non-empty finite sets such that there exist one-to-one and onto functions (i) from to and (ii) from to . The number of possible values of is ___

Let be a continuous function from to such that Which one of the following options is the CORRECT value of ?

When six unbiased dice are rolled simultaneously, the probability of getting all distinct numbers (i.e., 1, 2, 3, 4, 5, and 6) is

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is _______

Let be any matrix, where . Which of the following statements is/are TRUE about the system of linear equations ?

Let be the partial order defined on the set as follows The number of total orders on that contain is ______

Let be the adjacency matrix of a simple undirected graph . Suppose is its own inverse. Which one of the following statements is always TRUE?

Which of the following statements about threads is/are TRUE?

Consider a 32-bit system with page size and page table entries of size 4 bytes each. Assume bytes. The OS uses a 2-level page table for memory management, with the page table containing an outer page

Consider a process P running on a CPU. Which one or more of the following events will always trigger a context switch by the OS that results in process P moving to a non-running state (e.g., ready, bl

Consider the following two threads and that update two shared variables and . Assume that initially . Though context switching between threads can happen at any time, each statement of or is executed

Which of the following tasks is/are the responsibility/responsibilities of the memory management unit (MMU) in a system with paging-based memory management?

Consider a memory management system that uses a page size of . Assume that both the physical and virtual addresses start from 0. Assume that the pages , and are stored in the page frames , and , respe

Which of the following process state transitions is/are NOT possible?

Consider the following code snippet using the fork() and wait() system calls. Assume that the code compiles and runs correctly, and that the system calls run successfully without any errors. int x = 3

Consider a multi-threaded program with two threads T1 and T2. The threads share two semaphores: s1 (initialized to 1) and s2 (initialized to 0). The threads also share a global variable x (initialized

Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, and the second value is its CPU burst tim

An array is heapified. Which one of the following options represents the first three elements in the heapified array?

Consider the operator precedence and associativity rules for the integer arithmetic operators given in the table below. The value of the expression as per the above rules is _____

Consider the following C program: #include int main(){ int a = 6; int b = 0; while(a < 10) { a = a / 12 + 1; a += b;} printf("%d", a); return 0;} Which one of the following statements is CORRECT?

Consider the following C program: #include void fX(); int main(){ fX(); return 0;} void fX(){ char a; if((a=getchar()) != ' ') fX(); if(a != ' ') putchar(a);} Assume that the input to the program from

Consider the following C program. Assume parameters to a function are evaluated from right to left. #include int g(int p) { printf("%d", p); return p; } int h(int q) { printf("%d", q); return q; } voi

Consider an array X that contains n positive integers. A subarray of X is defined to be a sequence of array locations with consecutive indices. The C code snippet given below has been written to compu

What is the output of the following C program? #include int main() { double a[2]={20.0, 25.0}, *p, *q; p = a; q = p + 1; printf("%d,%d", (int)(q - p), (int)(*q - *p)); return 0;}

Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of 2 elements. S1 already has 4 elements: 100, 200, 300, and 400, whereas S2 is empty, as shown below. Stack S1 Stack S2 Onl

Consider the following C function definition. int f(int x, int y) { for (int i=0; i < y; i++) { x=x+x+y; } return x; } Which of the following statements is/are TRUE about the above function?

You are given a set of distinct integers. A binary search tree is created by inserting all elements of one by one, starting with an empty tree. The tree follows the convention that, at each node, all

Consider the following C function definition. int fX(char *a){ char *b = a; while(*b) b++; return b - a;} Which of the following statements is/are TRUE?

Let be an array containing integer values. The distance of is defined as the minimum number of elements in that must be replaced with another integer so that the resulting array is sorted in non-decre

In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the following cases?

Consider a binary min-heap containing 105 distinct elements. Let be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of is

Let M be the 5-state NFA with -transitions shown in the diagram below: Which one of the following regular expressions represents the language accepted by M ?

Let be the language represented by the regular expression and , where denotes the length of string . The number of strings in which are also in is ___

Let be two regular languages and a language which is not regular. Which of the following statements is/are always TRUE?

Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?

Consider the following two regular expressions over the alphabet : The total number of strings of length less than or equal to 5 , which are neither in nor in , is ____

Let be a context-free grammar in Chomsky Normal Form with and containing 10 variable symbols including the start symbol . The string is derivable from . The number of steps (application of rules) in t

Consider the 5 -state DFA accepting the language shown below. For any string let be the number of in and be the number of 1 's in . Which of the following statements is/are FALSE?

Consider the following context-free grammar where the start symbol is and the set of terminals is . The following is a partially-filled LL(1) parsing table. \\ S & S A a A b & S B b B a & (1) & (2) &

Consider the following augmented grammar, which is to be parsed with a SLR parser. The set of terminals is Let . The number of items in the set is ____

Consider a context-free grammar with the following 3 rules. Let . Let denote the number of times occur in , respectively. Which of the following statements is/are TRUE?