GATE-2024-CS1(Forenoon)

March 9, 2025

GATE 2022

March 9, 2025

GATE-2024-CS1(Forenoon)

Question 35

Consider the following two relations, R(A,B) and S(A,C):

S
A	C
10	90
30	45
40	80

R
A	B
10	20
20	30
30	40
30	50
50	95

The total number of tuples obtained by evaluating the following expression
σ_B<C(R⋈_R.A=S.A S)
is ______

A	2
B
C
D

database-management-systemRelational-Algebra

Question 35 Explanation:

Three rows are satisfying the condition R.A=S.A.
out of three rows,only two rows satisfying B<c condition=""

Question 36

Consider a network path P–Q–R between nodes P and R via router Q. Node P sends a file of size 10⁶ bytes to R via this path by splitting the file into chunks of 10³ bytes each. Node P sends these chunks one after the other without any wait time between the successive chunk transmissions. Assume that the size of extra headers added to these chunks is negligible, and that the chunk size is less than the MTU

Each of the links P–Q and Q–R has a bandwidth of 10⁶ bits/sec, and negligible propagation latency. Router Q immediately transmits every packet it receives from P to R, with negligible processing and queueing delays. Router Q can simultaneously receive on link P–Q and transmit on link Q–R .

Assume P starts transmitting the chunks at time t=0.

Which one of the following options gives the time (in seconds, rounded off to 3 decimal places) at which R receives all the chunks of the file?

A	8.000
B	8.008
C	15.992
D	16.000

computer-networksRouting

Question 37

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 )?

A	45
B	50
C	55
D	65

compiler-designSyntax-Directed-Translation

Question 38

Consider the following grammar G, with S as the start symbol. The grammar G has three incomplete productions denoted by (1), (2), and (3).

Which one of the following options CORRECTLY fills in the incomplete productions?.

A	(1) S → Rf (2) T —> Ε (3) R → cTR
B	(1) S →fR (2) T —> Ε (3)R → cTR
C	(1) S →fR (2) T→cT (3) R→ cR
D	(1) S → Rf (2) T→cT (3) R→ cR

compiler-designGrammar

Question 39

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:t1=t8

L11:t3=t3+1

L12: if t3 < M goto L4

L13:t2=t2+1

L14: if t2 < N goto L3

L15: max=t1

Which one of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively ?

A	6 and 6
B	6 and 7
C	7 and 7
D	7 and 6

computer-organizationInstruction-Cycle

Question 40

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 time, each statement of T1 or T2 is executed atomically without interruption.

a=a+1

b=b+1

b=2*b

a=2*a

Which one of the following options lists all the possible combinations of values of a and b after both T1 and T2 finish execution?

A	(a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3)
B	(a = 3, b = 4); (a = 4, b = 3); (a = 3, b = 3)
C	(a = 4, b = 4); (a = 4, b = 3); (a = 3, b = 4)
D	(a = 2, b = 2); (a = 2, b = 3); (a = 3, b = 4)

operating-systemsContext-Switching

Question 41

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?

A	82, 90, 101
B	82, 11, 93
C	131, 11, 93
D	131, 111, 90

data-structuresHeap

Question 41 Explanation:

After heapifying the given array, the root element will be the maximum value. So, the root element is 131.

Now, let’s consider the options again:

(A) 82, 90, 101 – This cannot be correct because the root element, which is the maximum, is not included.
(B) 82, 11, 93 – This cannot be correct because the second element is not necessarily the second maximum in the array.
(C) 131, 11, 93 – This cannot be correct because 11 and 93 are not necessarily the next largest values after the root.
(D) 131, 111, 90 – This is the most likely option because after the root (131), the next largest values in the array are 111 and 90.

Question 42

Consider the following recurrence relation:

T(n)=√nT(√n)+n for n>=1,
1 for n=1

Which one of the following options is CORRECT?

A	T(n)= Θ(n loglogn )
B	T(n)=Θ(n logn)
C	T(n)=Θ(n² logn)
D	T(n)=Θ(n²loglogn)

algorithmsRecurrences

Question 43

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 of k is

A	53
B	52
C	27
D	1

data-structuresHeap

Question 44

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

A	(X,Y)→ (Z,W) implies X→ (Z,W)
B	(X,Y)→ (Z,W) implies (X,Y)→ Z
C	((X,Y)→ Z and W→ Y) implies (X,W)→ Z
D	(X→Yand Y→ Z) implies X→ Z

database-management-systemFunctional-Dependency

Question 44 Explanation:

(A) (X,Y) → (Z,W) implies X → (Z,W)
This statement is not necessarily true. The functional dependency (X,Y) → (Z,W) means that for any given value of X and Y, there is a unique value of Z and W. However, this does not imply that for any given value of X, there is a unique value of Z and W. So, option (A) is FALSE.

(B) (X,Y) → (Z,W) implies (X,Y) → Z
This statement is TRUE. If (X,Y) functionally determines (Z,W), then it also functionally determines Z. This is because for any given combination of X and Y, there is a unique value of Z according to the functional dependency. So, option (B) is TRUE.

(C) ((X,Y) → Z and W → Y) implies (X,W) → Z
This statement is TRUE. If X and Y together determine Z and W determines Y, then X and W together determine Z. This is because for any given combination of X and W, we can find the corresponding values of Y and then use (X,Y) → Z to determine the value of Z. So, option (C) is TRUE.

(D) (X → Y and Y → Z) implies X → Z
This statement is TRUE. If X determines Y and Y determines Z, then X determines Z. This is because the transitive property of functional dependency applies here. So, option (D) is TRUE

Question 45

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. Which of the following statements is/are TRUE for every such graph G and tree T ?

A	There are no back-edges in G with respect to the tree T
B	There are no cross-edges in G with respect to the tree T
C	There are no forward-edges in G with respect to the tree T
D	The only edges in G are the edges in T

data-structuresBFS-and-DFS

Question 45 Explanation:

(A) Not True: Back edges are still possible in this scenario, as explained before.
(B) Not True: While the BFS aspect reduces the likelihood of cross-edges, it’s not guaranteed. Imagine a graph with a cycle that connects back to an earlier explored level. Such a cycle would create a cross-edge in G relative to T.
(C) True: In a BFS tree, all vertices at a level are explored before moving to the next level. This ensures that for any two connected vertices in G:
If they are in the same level of T, there cannot be a forward edge because BFS explores neighbors at a level before moving deeper (they would be explored in the opposite order if it were a forward edge).
If one vertex is an ancestor of the other in T, it cannot be a forward edge by definition (a forward edge points from a vertex to its descendant).
Therefore, since T is both a DFS spanning tree and a BFS tree rooted at v, all edges in T must be either back edges (pointing to an ancestor) or edges that explore neighbors at the same level. This eliminates the possibility of forward edges in G with respect to T.

Question 46

Consider the following read-write schedule S over three transactions T1, T2, and T3, where the subscripts in the schedule indicate transaction IDs:
S: r1(z); w1(z); r2(x); r3(y); w3(y); r2(y); w2(x); w2(y);
Which of the following transaction schedules is/are conflict equivalent to S ?

A	T1T2T3
B	T1T3T2
C	T3T2T1
D	T3T1T2

database-management-systemTransactions and concurrency control

Question 47

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

A	F(X,Y,Z)=Π(0,1,2,4)
B	F(X,Y,Z)=XY+YZ+XZ
C	F(X,Y,Z) is independent of input Y
D	F(X,Y,Z) is independent of input X

digital-logic-designMinimization

Question 47 Explanation:

(A) F(X, Y, Z) = Π(0, 1, 2, 4)
This statement represents the product of terms (AND operation) for the minterms (0, 1, 2, 4). However, the actual expression uses the sum of terms (OR operation) denoted by Σ.
Here’s the key point: The given minterms (3, 5, 6, 7) can be interpreted in two ways:
Standard Interpretation (Sum of Terms): This is the more common interpretation, where the expression represents the OR operation of the minterms. In this case, the statement (A) would be incorrect.
Less Common Interpretation (Negation of Product of Terms): In some contexts, a Boolean expression can be written as the negation of its complement. The complement of F(X, Y, Z) would be the product of terms for all combinations where the output is 0 (maxterms). In this specific case, the maxterms would be (0, 1, 2, 4). Taking the negation (NOT operation) of the complement would result in the original expression F(X, Y, Z). So, under this less common interpretation, statement (A) could be considered correct.
(B) F(X, Y, Z) = XY + YZ + XZ
This statement represents an OR operation (sum of terms) using product of variables (XY, YZ, XZ). However, these specific terms don’t directly correspond to the minterms (3, 5, 6, 7).

Question 48

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?

A	If the inputs are x=20, y=10, then the return value is greater than 220
B	If the inputs are x=20, y=20, then the return value is greater than 220
C	If the inputs are x=20, y=10, then the return value is less than 210
D	If the inputs are x=10, y=20, then the return value is greater than 220

programmingControl-Statement

Question 48 Explanation:

The function f(int x, int y) takes two integer arguments x and y. It uses a for loop that iterates y times. Inside the loop, the value of x is updated using the expression x = x + x + y.

Analyzing Statements:

(A) If the inputs are x=20, y=10, then the return value is greater than 220

Let’s simulate the function call with x = 20 and y = 10:

Iteration 1: x = 20 + 20 + 10 = 50
Iteration 2: x = 50 + 50 + 10 = 110
… (similar updates in every iteration)
Iteration 10 (assuming y = 10): x = … + … + 10 = ~210 (The exact value will be slightly higher than 210)
Therefore, statement (A) is False. The return value is likely around 210, not greater than 220.

(B) If the inputs are x=20, y=20, then the return value is greater than 220

Similar to (A), with y = 20, the final value of x will be significantly higher than 220. Statement (B) is True.

As shown in the analysis of (A), the return value is around 210. Statement (C) is False.

(D) If the inputs are x=10, y=20, then the return value is greater than 220

With x = 10 and y = 20, the final value of x will be even higher than in (B). Statement (D) is True.

Question 49

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

A	There exist at least m-n linearly independent solutions to this system
B	There exist m-n linearly independent vectors such that every solution is a linear combination of these vectors
C	There exists a non-zero solution in which at least m-n variables are 0
D	There exists a solution in which at least n variables are non-zero

engineering-mathematicsLinear-Algebra

Question 50

Which of the following statements is/are FALSE?

A	States 2 and 4 are distinguishable in M
B	States 3 and 4 are distinguishable in M
C	States 2 and 5 are distinguishable in M
D	Any string w with n(w)=n₁(w) is in L(M)

theory-of-computationDFA

Question 51

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 following statements is/are always TRUE?

A	G contains a complete subgraph with k vertices
B	G contains an independent set of size at least n/k
C	G contains at least k(k−1)/2 edges
D	G contains a vertex of degree at least k
E

engineering-mathematicsGraph-Theory

Question 51 Explanation:

The existence of a proper k-coloring implies the existence of color classes (sets of vertices with the same color) that form independent sets. In a worst-case scenario, where all color classes except one have fewer than n/k vertices, the remaining color class must have at least n/k vertices to ensure all vertices are colored.
Dense graphs with a chromatic number k are more likely to have at least k(k-1)/2 edges

Question 52

A	A
B	B
C	C
D	D
E

engineering-mathematicsGroup-Theory

Question 53

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 replacement policy. The cache memory is connected to the main memory. Which of the following statements is/are TRUE?

A	A read miss in WBC never evicts a dirty block
B	A read miss in WTC never triggers a write back operation of a cache block to main memory
C	A write hit in WBC can modify the value of the dirty bit of a cache block
D	A write miss in WTC always writes the victim cache block to main memory before loading the missed block to the cache
E

computer-organizationMemory-Organization

Question 53 Explanation:

(B) A read miss in WTC never triggers a write back operation of a cache block to main memory

In a Write Through Cache (WTC), every write operation to the cache is immediately propagated to main memory. However, a read miss only involves reading data from main memory into the cache; it does not trigger any write back operations. Therefore, a read miss in WTC does not cause any write back operation. This statement is true.

(C) A write hit in WBC can modify the value of the dirty bit of a cache block

In a Write Back Cache (WBC), a write hit means that the data to be written is already present in the cache. When a write occurs, the value of the dirty bit for the block is set to indicate that the block has been modified. Thus, a write hit in WBC will modify (set) the dirty bit of the cache block. This statement is true.

Question 54

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	4096
B
C
D
E

operating-systemsDisk-Management

Question 54 Explanation:

1. Total storage capacity:
o Given: 512 GB
o Convert GB to bytes: 512 GB=512×2^30 bytes=512×1073741824 bytes=549755813888 bytes
2. Bytes per track:
o Number of sectors per track = 4096
o Number of bytes per sector = 1024
o Total bytes per track: Bytes per track=4096 sectors/track×1024 bytes/sector=4194304 bytes
3. Total number of tracks:
o Total storage capacity / Bytes per track: Number of tracks=549755813888 bytes/4194304 bytes/track=131072
4. Calculate the number of cylinders:
o Given: 32 storage surfaces
o Each cylinder contains one track per surface.
o Number of cylinders = Number of tracks / Number of surfaces: Number of cylinders=131072 tracks /32 surfaces=4096
Therefore, the number of cylinders in the hard disk is indeed 4096

Question 55

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 an additional core is 10 ns when running on a multicore system. Assume that all cores in the multicore system run their share of the parallelized code for an equal amount of time.
The number of cores that minimize the execution time of the program is ________

A	3
B
C
D
E

computer-organizationParallel-processing

Question 56

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 on data cache. The miss penalty is 100 cycles. The speedup (rounded off to two decimal places) achieved with a perfect cache (i.e., with NO data or instruction cache misses) is _________

A	3.00
B
C
D
E

computer-organizationCache

Question 57

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;
while(x > 0) {
fork();
printf(“hello”);
wait(NULL);
x–;
}
The total number of times the printf statement is executed is _______

A	14
B
C
D
E

operating-systemsFork

Question 57 Explanation:

To find the total number of times printf(“hello”); is executed, we sum up the executions from each iteration:
First iteration: 2 executions
Second iteration: 4 executions
Third iteration: 8 executions
So, 2+4+8=14

Question 58

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 address matches the prefix. The notation “/N” in a prefix indicates a subnet mask with the most significant N bits set to 1.

This router forwards 20 packets each to 5 hosts. The IP addresses of the hosts are 10.1.1.16, 10.1.1.72, 10.1.1.132, 10.1.1.191, and 10.1.1.205 . The number of packets forwarded via the next hop router R2 is _______

A	40
B
C
D
E

computer-networksRouting

Question 59

A	179
B
C
D
E

theory-of-computationContest-Free-Grammar

Question 60

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 _________

A	60
B
C
D
E

data-structuresGraph-Theory

Question 60 Explanation:

Let K be the number of connected components (or trees) in the forest.
Number of edges=V-K
40=100-K
K=60

Question 61

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 in r nor in s, is _________

A	44
B
C
D
E

theory-of-computationRegular-Expression

Question 62

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 in the page frames 1, 3, 2, and 0, respectively. The physical address (in decimal format) corresponding to the virtual address 2500 (in decimal format) is _________

A	6596
B
C
D
E

operating-systemsMemory-Management

Question 62 Explanation:

Page number=Virtual address / Page size= 2500 / 2048 = 1
Offset=Virtual address mod Page size
Offset= 2500 mod 2048=452
Frame number for Page 1 is 3
Page size = 2048 bytes
Calculate the Physical Address:
Physical address = (Frame number × Page size) + Offset =(3*2048)+452=6596

Question 63

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 balls drawn are red is _________

A	0.370 to 0.380
B
C
D
E

engineering-mathematicsProbability

Question 63 Explanation:

Given:
Total number of red balls: 10
Total number of blue balls: 15
Total balls: 25
Two balls are drawn randomly without replacement.
The first ball drawn is red.
Let’s denote:
A = Event that the first ball drawn is red.
B = Event that both balls drawn are red.
We need to find P(B|A), the probability that both balls are red given that the first ball is red.

Total number of ways to draw two balls:
Since the first ball is known to be red, we need to find the probability of drawing another red ball from the remaining balls.

Remaining Balls After First Draw:

After drawing the first red ball, there are 9 red balls and 15 blue balls left.
Total remaining balls = 24
Probability of Drawing a Second Red Ball:
The number of favorable outcomes for drawing another red ball is 9 (since there are 9 red balls left).
The total number of outcomes is 24 (total remaining balls).
So, the probability of drawing a second red ball given that the first one was red is:
P(Second ball is red |First ball is red)= Number of remaining red balls
/ Total remaining balls = 9/24=0.375

Question 64

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 select lines of M1, M2, and M3, respectively.

For an instance of inputs X1=1, X2=1, X3=0, and X4=0, the number of
combinations of A, B, C that give the output Y=1 is _________

A	4
B
C
D
E

digital-logic-designMultiplexer

Question 65

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) has an MTU (Maximum Transmission Unit)
size of 542 bytes, while the second link (router to receiver) has an MTU size of 360
bytes. The number of fragments that would be delivered at the receiver is ________

A	6
B
C
D
E

computer-networksIP-Datagram

Once you are finished, click the button below. Any items you have not completed will be marked incorrect.
Get Results

Correct Answer: A

Question 35 Explanation:

Three rows are satisfying the condition R.A=S.A.
out of three rows,only two rows satisfying B<c condition=""

Sohail Kumar

0 0 votes

Article Rating

0 Comments

Inline Feedbacks

View all comments