GATE 2024 CSE & IT

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 fol...

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?

Consider a Boolean expression given by $F(X, Y, Z) = \Sigma(3,5,6,7)$. Which of the following statements is/are CORRECT?

Let $A$ and $B$ be non-empty finite sets such that there exist one-to-one and onto functions (i) from $A$ to $B$ and (ii) from $A \times A$ to $A \cup B$. The number of possible va...

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

Consider the following two relations, R(A, B) and S(A, C) : R A B 10 20 20 30 30 40 30 50 50 95 S A C 10 90 30 45 40 80 The total number of tuples obtained by evaluating the follow...

Consider a network path P—Q—R between nodes P and R via router Q. Node P sends a file of size $10^6$ bytes to R via this path by splitting the file into chunks of $10^3$ bytes each...

Consider the following syntax-directed definition (SDD). S → DHTU { S.val = D.val + H.val + T.val + U.val; } D → “M” D 1 { D.val = 5 + D 1 .val; } D → ε { D.val = –5; } H → “L” H 1...

Consider the following pseudo-code. L1: t1 = -1 L2: t2 = 0 L3: t3 = 0 L4: t4 = 4 * t3 L5: t5 = 4 * t2 L6: t6 = t5 * M L7: t7 = t4 + t6 L8: t8 = a[t7] L9: if t8 L10: t1 = t8 L11: t3...

Consider the following two threads T1 and T2 that update two shared variables a and b. Assume that initially $a = 1$ and $b = 1$. Though context switching between threads can happe...

An array $[82, 101, 90, 11, 111, 75, 33, 131, 44, 93]$ is heapified. Which one of the following options represents the first three elements in the heapified array?

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 f...

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

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

Let G be a directed graph and T a depth first search (DFS) spanning tree in G that is rooted at a vertex v. Suppose T is also a breadth first search (BFS) tree in G, rooted at v. W...

Consider the following read-write schedule $S$ over three transactions $T_{1}$, $T_{2}$, and $T_{3}$, where the subscripts in the schedule indicate transaction IDs: $S: r_{1}(z); w...

Let A be any n x m matrix, where m > n . Which of the following statements is/are TRUE about the system of linear equations Ax = 0 ?

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$. Which of...

Consider the operators $\diamond$ and $\square$ defined by $a \diamond b=a+2 b, a \square b=a b$, for positive integers. Which of the following statements is/are TRUE?

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 Rec...

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 ______

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. Th...

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 cac...

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 a...

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

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

Consider a memory management system that uses a page size of 2 KB. Assume that both the physical and virtual addresses start from 0. Assume that the pages 0, 1, 2, and 3 are stored...

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 p...

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

Given an integer array of size $N$, 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 thro...

Consider the following recurrence relation: $$T(n) = \begin{cases} \sqrt{n} T(\sqrt{n}) + n & \text{for } n \ge 1, \\ 1 & \text{for } n = 1. \end{cases}$$ Which one of the followin...

TCP client P successfully establishes a connection to TCP server Q. Let $N_P$ denote the sequence number in the SYN sent from P to Q. Let $N_Q$ denote the acknowledgement number in...

Consider the following grammar $G$, with $S$ as the start symbol. The grammar $G$ has three incomplete productions denoted by (1), (2), and (3). $$S \rightarrow d a T \mid \underli...

Let A and B be two events in a probability space with $P(A) = 0.3$, $P(B) = 0.5$, and $P(A \cap B) = 0.1$. Which of the following statements is/are TRUE?

Let G = (V, Σ, S, P) be a context-free grammar in Chomsky Normal Form with Σ = { a, b, c } and V containing 10 variable symbols including the start symbol S . The string w = a 30 b...

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

Consider the following two regular expressions over the alphabet {0,1} : $$r = 0^* + 1^*$$ $$s = 01^* + 10^*$$ The total number of strings of length less than or equal to 5, which...

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

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

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

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

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

Consider the following C program: #include <stdio.h> void fX(); int main() { fX(); return 0;} void fX() { char a; if ((a = getchar()) != '\n') fX(); if (a != '\n') putchar(a);} Ass...

Consider the following C program: #include &ltstdio.h> int main() { int a = 6; int b = 0; while(a Which one of the following statements is CORRECT?

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-lev...

Which one of the following statements is FALSE?

Consider a permutation sampled uniformly at random from the set of all permutations of {1, 2, 3, ..., n } for some n ≥ 4. Let X be the event that 1 occurs before 2 in the permutati...

Consider a system that uses 5 bits for representing signed integers in 2’s complement format. In this system, two integers A and B are represented as A =01010 and B =11010. Which o...

The product of all eigenvalues of the matrix $\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}$ is

Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be a function such that $f(x) = \max \{x, x^3\}, x \in \mathbb{R}$, where $\mathbb{R}$ is the set of all real numbers. The set of all po...

A rectangular paper sheet of dimensions 54 cm &times; 4 cm is taken. The two longer edges of the sheet are joined together to create a cylindrical tube. A cube whose surface area i...

In the given text, the blanks are numbered (i)–(iv). Select the best match for all the blanks. Steve was advised to keep his head _____ (i) _____ before heading _____ (ii) _____ to...

For positive non-zero real variables $p$ and $q$, if $\log \left(p^2 + q^2\right) = \log p + \log q + 2 \log 3$, then, the value of $\frac{p^4 + q^4}{p^2 q^2}$ is

If two distinct non-zero real variables $x$ and $y$ are such that $(x + y)$ is proportional to $(x - y)$ then the value of $\frac{x}{y}$

If ‘→’ denotes increasing order of intensity, then the meaning of the words [dry → arid → parched] is analogous to [diet → fast → ________ ]. Which one of the given options is appr...

The number of coins of ₹1, ₹5, and ₹10 denominations that a person has are in the ratio 5:3:13. Of the total amount, the percentage of money in ₹5 coins is

Consider the following sample of numbers: 9, 18, 11, 14, 15, 17, 10, 69, 11, 13 The median of the sample is

A rectangular paper of 20 cm &times; 8 cm is folded 3 times. Each fold is made along the line of symmetry, which is perpendicular to its long edge. The perimeter of the final folde...

Consider the operator precedence and associativity rules for the integer arithmetic operators given in the table below. Operator Precedence Associativity + Highest Left − High Righ...

If ‘→’ denotes increasing order of intensity, then the meaning of the words [walk → jog → sprint] is analogous to [bothered → _______ → daunted]. Which one of the given options is...

Two wizards try to create a spell using all the four elements, water, air, fire, and earth . For this, they decide to mix all these elements in all possible orders. They also decid...

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

In an engineering college of 10,000 students, 1,500 like neither their core branches nor other branches. The number of students who like their core branches is 1/4 th of the number...

For positive non-zero real variables $x$ and $y$, if $\ln \left( \frac{x + y}{2} \right) = \frac{1}{2} [ \ln (x) + \ln (y) ]$ then, the value of $\frac{x}{y} + \frac{y}{x}$ is

In the sequence 6, 9, 14, $x$, 30, 41, a possible value of $x$ is

Sequence the following sentences in a coherent passage. P: This fortuitous geological event generated a colossal amount of energy and heat that resulted in the rocks rising to an a...

A person sold two different items at the same price. He made 10% profit in one item, and 10% loss in the other item. In selling these two items, the person made a total of

A cube is to be cut into 8 pieces of equal size and shape. Here, each cut should be straight and it should not stop till it reaches the other end of the cube. The minimum number of...

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 st...

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 o...

Let p and q be the following propositions: p : Fail grade can be given. q : Student scores more than 50% marks. Consider the statement: “Fail grade cannot be given when student sco...

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

The format of a single-precision floating-point number as per the IEEE 754 standard is: Sign (1 bit) Exponent (8 bits) Mantissa (23 bits) Choose the largest floating-point number a...

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

Let $f(x)$ be a continuous function from $\mathbb{R}$ to $\mathbb{R}$ such that $f(x) = 1 - f(2 - x)$ Which one of the following options is the CORRECT value of $\int_0^2 f(x) dx$?

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

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

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

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

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

Consider the following two sets: Set X P. Lexical Analyzer Q. Syntax Analyzer R. Intermediate Code Generator S. Code Optimizer Set Y 1. Abstract Syntax Tree 2. Token 3. Parse Tree...

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

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?

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

Which of the following statements is/are FALSE?

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

An instruction format has the following structure: Instruction Number: Opcode destination reg, source reg-1, source reg-2 Consider the following sequence of instructions to be exec...

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 $P$ be the partial order defined on the set {1,2,3,4} as follows: $P = \{(x, x) \mid x \in \{1,2,3,4\}\} \cup \{(1,2), (3,2), (3,4)\}$ The number of total orders on {1,2,3,4} t...

What is the output of the following C program? #include <studio.h> 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)); r...

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

You are given a set $V$ of distinct integers. A binary search tree $T$ is created by inserting all elements of $V$ one by one, starting with an empty tree. The tree $T$ follows the...

Consider the following context-free grammar where the start symbol is S and the set of terminals is {a,b,c,d}. $ S \rightarrow AaAb \mid BbBa $ $ A \rightarrow cS \mid \epsilon $ $...

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 b...

Consider the following expression: $x[i] = (p + r) * -s[i] + \frac{u}{w}$. The following sequence shows the list of triples representing the given expression, with entries missing...

Let $ x $ and $ y $ be random variables, not necessarily independent, that take real values in the interval $[0,1]$. Let $ z = xy $ and let the mean values of $ x, y, z $ be $ \bar...

The relation schema, Person ($\underline{\text{pid}}$, $city$), describes the city of residence for every person uniquely identified by $pid$. The following relational algebra oper...

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 var...

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

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

Let Z n be the group of integers {0, 1, 2, ..., n − 1} with addition modulo n as the group operation. The number of elements in the group Z 2 × Z 3 × Z 4 that are their own inverse...

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 i...

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

Consider an Ethernet segment with a transmission speed of $10^8$ bits/sec and a maximum segment length of 500 meters. If the speed of propagation of the signal in the medium is $2...

A functional dependency $F: X \to Y$ is termed as a useful functional dependency if and only if it satisfies all the following three conditions: $X$ is not the empty set. $Y$ is no...

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 f...

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-s...

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 divid...

Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each. Assume 1 KB = $2^{10}$ bytes. The OS uses a 2-level page table for memory management, with...

Consider the following augmented grammar, which is to be parsed with a SLR parser. The set of terminals is $\{ a, b, c, d, \, \#, \, @ \}$ $S' \rightarrow S$ $S \rightarrow SS \;|\...

Let $T(n)$ be the recurrence relation defined as follows: $T(0) = 1$ $T(1) = 2$, and $T(n) = 5T(n - 1) - 6T(n - 2)$ for $n \geq 2$ Which one of the following statements is TRUE?

Let $A$ be an array containing integer values. The distance of $A$ is defined as the minimum number of elements in $A$ that must be replaced with another integer so that the result...

Let $G$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $G$ has even weight. Which of the following statemen...

Let L 1 be the language represented by the regular expression b * ab * (ab * ab * ) * and L 2 = { w ∈ (a + b) * | |w| ≤ 4 } , where |w| denotes the length of string w . The number...

Consider a context-free grammar $G$ with the following 3 rules. $S \rightarrow aS, \ S \rightarrow aSbS, S \rightarrow c$ Let $w \in L(G)$. Let $n_a(w)$, $n_b(w)$, $n_c(w)$ denote...

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. S...

If '→' denotes increasing order of intensity, then the meaning of the words [dry → arid → parched] is analogous to [diet → fast → ______]. Which one of the given options is appropr...

If two distinct non-zero real variables x and y are such that (x + y) is proportional to (x - y) then the value of $\frac{x}{y}$

Consider the following sample of numbers: 9, 18, 11, 14, 15, 17, 10, 69, 11, 13 The median of the sample is

The number of coins of ₹1, ₹5, and ₹10 denominations that a person has are in the ratio 5:3:13. Of the total amount, the percentage of money in ₹5 coins is

For positive non-zero real variables p and q, if log (p² + q²) = log p + log q + 2 log 3, then, the value of $\frac{p^4+q^4}{p^2q^2}$ is

In the given text, the blanks are numbered (i)-(iv). Select the best match for all the blanks. Steve was advised to keep his head _______ (i) _______ before heading _______ (ii) __...

A rectangular paper sheet of dimensions 54 cm x 4 cm is taken. The two longer edges of the sheet are joined together to create a cylindrical tube. A cube whose surface area is equa...

The pie chart presents the percentage contribution of different macronutrients to a typical 2,000 kcal diet of a person. Macronutrient energy contribution [Pie chart showing: Carbo...

A rectangular paper of 20 cm × 8 cm is folded 3 times. Each fold is made along the line of symmetry, which is perpendicular to its long edge. The perimeter of the final folded shee...

The least number of squares to be added in the figure to make AB a line of symmetry is

Let f: R → R be a function such that f(x) = max{x,x³}, x ∈ R, where R is the set of all real numbers. The set of all points where f(x) is NOT differentiable is

The product of all eigenvalues of the matrix $\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}$ is

Consider a system that uses 5 bits for representing signed integers in 2's complement format. In this system, two integers A and B are represented as A=01010 and B=11010. Which one...

Consider a permutation sampled uniformly at random from the set of all permutations of {1, 2, 3, ..., n} for some n ≥ 4. Let X be the event that 1 occurs before 2 in the permutatio...

Which one of the following statements is FALSE?

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-lev...

Given an integer array of size N, 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 throug...

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 sta...

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

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

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

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

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

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

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

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

Let A and B be two events in a probability space with P(A) = 0.3, P(B) = 0.5, and P(A ∩ B) = 0.1. Which of the following statements is/are TRUE?

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 f...

TCP client P successfully establishes a connection to TCP server Q. Let Np denote the sequence number in the SYN sent from P to Q. Let NQ denote the acknowledgement number in the S...

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 fol...

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?

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

Consider the operator precedence and associativity rules for the integer arithmetic operators given in the table below. Operator | Precedence | Associativity ---|---|--- + | Highes...

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

Consider the following two relations, R(A,B) and S(A,C): The total number of tuples obtained by evaluating the following expression $\sigma_{B<C}(R \bowtie_{R.A=S.A} S)$ is _______...

Consider a network path P—Q—R between nodes P and R via router Q. Node P sends a file of size 10^6 bytes to R via this path by splitting the file into chunks of 10^3 bytes each. No...

Consider the following syntax-directed definition (SDD). S → DHTU { S.val = D.val + H.val + T.val + U.val; } D → "M"D₁ { D.val = 5 + D₁.val; } D → ε { D.val = -5; } H → "L"H₁ { H.v...

Consider the following grammar G, with S as the start symbol. The grammar G has three incomplete productions denoted by (1), (2), and (3). S → daT | ____ (1) T → aS | bT | ____ (2)...

Consider the following pseudo-code. L1: t1 = -1 L2: t2 = 0 L3: t3 = 0 L4: t4 = 4 * t3 L5: t5 = 4 * t2 L6: t6 = t5 * M L7: t7 = t4 + t6 L8: t8 = a[t7] L9: if t8 <= max goto L11 L10:...

Consider the following two threads T1 and T2 that update two shared variables a and b. Assume that initially a = b = 1. Though context switching between threads can happen at any t...

An array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified. Which one of the following options represents the first three elements in the heapified array?

Consider the following recurrence relation: $T(n) = \begin{cases} \sqrt{n}T(\sqrt{n}) + n & \text{for } n \geq 1, \\ 1 & \text{for } n = 1. \end{cases}$ Which one of the following...

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

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

Let G be a directed graph and T a depth first search (DFS) spanning tree in G that is rooted at a vertex v. Suppose T is also a breadth first search (BFS) tree in G, rooted at v. W...

Consider the following read-write schedule S over three transactions T1, T2, and T3, where the subscripts in the schedule indicate transaction IDs: S: r₁(z); w₁(z); r₂(x); r₃(y); w...

Consider a Boolean expression given by F(X, Y, Z) = ∑(3,5,6,7). Which of the following statements is/are CORRECT?

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 f...

Let A be any n × m matrix, where m > n. Which of the following statements is/are TRUE about the system of linear equations Ax = 0 ?

Consider the 5-state DFA M accepting the language L(M) ⊂ (0+1)* shown below. For any string w ∈ (0+1)* let n₀(w) be the number of 0's in w and n₁(w) be the number of 1's in w. Whic...

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let G be any graph with n vertices and chromatic number k. Which of the fo...

Consider the operators ◊ and □ defined by a◊ b = a + 2b, a□b = ab, for positive integers. Which of the following statements is/are TRUE?

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 Recent...

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 _______...

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

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 cac...

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 a...

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

Let G = (V, Σ, S, P) be a context-free grammar in Chomsky Normal Form with Σ = {a,b,c} and V containing 10 variable symbols including the start symbol S. The string w = a^30 b^30 c...

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

Consider the following two regular expressions over the alphabet {0,1}: r = 0* + 1* s = 01* + 10* The total number of strings of length less than or equal to 5, which are neither i...

Consider a memory management system that uses a page size of 2 KB. Assume that both the physical and virtual addresses start from 0. Assume that the pages 0, 1, 2, and 3 are stored...

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 p...

Consider a digital logic circuit consisting of three 2-to-1 multiplexers M1, M2, and M3 as shown below. X1 and X2 are inputs of M1. X3 and X4 are inputs of M2. A, B, and C are sele...

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

If '→' denotes increasing order of intensity, then the meaning of the words [walk → jog → sprint] is analogous to [bothered → _______ → daunted]. Which one of the given options is...

Two wizards try to create a spell using all the four elements, water, air, fire, and earth. For this, they decide to mix all these elements in all possible orders. They also decide...

In an engineering college of 10,000 students, 1,500 like neither their core branches nor other branches. The number of students who like their core branches is 1/4th of the number...

For positive non-zero real variables x and y, if $\ln\left(\frac{x+y}{2}\right) = \frac{1}{2}[\ln (x) + \ln (y)]$ then, the value of $\frac{x}{y} + \frac{y}{x}$ is

In the sequence 6, 9, 14, x, 30, 41, a possible value of x is

Sequence the following sentences in a coherent passage. P: This fortuitous geological event generated a colossal amount of energy and heat that resulted in the rocks rising to an a...

A person sold two different items at the same price. He made 10% profit in one item, and 10% loss in the other item. In selling these two items, the person made a total of

The pie charts depict the shares of various power generation technologies in the total electricity generation of a country for the years 2007 and 2023. The renewable sources of ele...

A cube is to be cut into 8 pieces of equal size and shape. Here, each cut should be straight and it should not stop till it reaches the other end of the cube. The minimum number of...

In the 4 x 4 array shown below, each cell of the first three rows has either a cross (X) or a number. 1 X 4 3 X 5 5 4 3 X 6 X The number in a cell represents the count of the immed...

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 o...

Let p and q be the following propositions: p: Fail grade can be given. q: Student scores more than 50% marks. Consider the statement: “Fail grade cannot be given when student score...

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",...

The format of a single-precision floating-point number as per the IEEE 754 standard is: Sign (1bit) Exponent (8 bits) Mantissa (23 bits) Choose the largest floating-point number am...

Let T(n) be the recurrence relation defined as follows: T(0) = 1, T(1) = 2, and T(n) = 5T(n - 1) – 6T(n-2) for n ≥ 2 Which one of the following statements is TRUE?

Let f(x) be a continuous function from ℝ to ℝ such that f(x) = 1 − f(2 – x) Which one of the following options is the CORRECT value of $\int_0^2 f(x)dx$?

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

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

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

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

Consider the following two sets: Set X P. Lexical Analyzer Q. Syntax Analyzer R. Intermediate Code Generator S. Code Optimizer Set Y 1. Abstract Syntax Tree 2. Token 3. Parse Tree...

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

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

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 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 st...

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?

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

Which of the following statements is/are FALSE?

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

An instruction format has the following structure: Instruction Number: Opcode destination reg, source reg-1, source reg-2 Consider the following sequence of instructions to be exec...

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

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 P be the partial order defined on the set {1,2,3,4} as follows P = {(x,x) | x ∈ {1,2,3,4}} ∪ {(1,2), (3,2), (3,4)} The number of total orders on {1,2,3,4} that contain P is ___...

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

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;}

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

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

You are given a set V of distinct integers. A binary search tree T is created by inserting all elements of V one by one, starting with an empty tree. The tree T follows the convent...

Consider the following context-free grammar where the start symbol is S and the set of terminals is {a,b,c,d}. S → AaAb | BbBa A → cS | ε B → dS | ε The following is a partially-fi...

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

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 b...

Consider the following expression: x[i] = (p + r) * -s[i] + u/w. The following sequence shows the list of triples representing the given expression, with entries missing for triple...

Let x and y be random variables, not necessarily independent, that take real values in the interval [0,1]. Let z = xy and let the mean values of x, y, z be x̄, ȳ, z̄, respectively....

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: sele...

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 var...

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

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. 4...

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

Consider 4-variable functions f1, f2, f3, f4 expressed in sum-of-minterms form as given below. f1 = ∑(0,2,3,5,7,8,11,13) f2 = ∑(1,3,5,7,11,13, 15) f3 = ∑(0,1,4,11) f4 = ∑(0,2,6,13)...

Let G be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in G has even weight. Which of the following statements i...

Consider a context-free grammar G with the following 3 rules. S → aS, S → aSbS, S → c Let w ∈ L(G). Let n_a(w), n_b(w), n_c(w) denote the number of times a, b, c occur in w, respec...

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 i...

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

Consider an Ethernet segment with a transmission speed of 10^8 bits/sec and a maximum segment length of 500 meters. If the speed of propagation of the signal in the medium is 2x10^...

A functional dependency F: X → Y is termed as a useful functional dependency if and only if it satisfies all the following three conditions: * X is not the empty set. * Y is not th...

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 f...

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-s...

The number of distinct minimum-weight spanning trees of the following graph 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 _________

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 divid...

Let L₁ be the language represented by the regular expression b*ab*(ab*ab*)* and L₂ = { w ∈ (a + b)* | |w| ≤ 4}, where |w| denotes the length of string w. The number of strings in L...

Let Zₙ be the group of integers {0, 1, 2, ..., n-1} with addition modulo n as the group operation. The number of elements in the group Z₂ × Z₃ × Z₄ that are their own inverses is _...

Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each. Assume 1 KB = 2^10 bytes. The OS uses a 2-level page table for memory management, with the...

Consider the following augmented grammar, which is to be parsed with a SLR parser. The set of terminals is {a,b,c,d,#,@} S' → S S → SS | Aa | bAc | Bc | bBa A → d# B → @ Let I₀ = C...