CS and IT GATE 2025 SET-1 Questions with Answer

Ques 1 Algorithms

Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices, u and v, let d₁(u,v) and d₂(u,v) be the shortest distances between u and v in G and T, respectively. Which ONE of the options is CORRECT for all possible G, T, u and v?

d₁(u,v)=d₂(u,v)

d₁(u,v)≤d₂(u,v)

d₁(u,v)≥d₂(u,v)

d₁(u,v)≠d₂(u,v)

Ques 2 Algorithms

Consider the following recurrence relation:
T(n)=2T(n-1)+n2ⁿ for n>0, T(0)=1.
Which ONE of the following options is CORRECT?

T(n)=Θ(n²2ⁿ)

T(n)=Θ(n2ⁿ)

T(n)=Θ((log n)²2ⁿ)

T(n)=Θ(4ⁿ)

Ques 3 Algorithms

The pseudocode of a function fun () is given below:

Let A[0,...,29] be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function fun () is called with A[0,...,29] as argument, is ______ (Answer in integer)

Ques 4 Algorithms

Let G(V,E) be an undirected and unweighted graph with 100 vertices. Let d(u,v) denote the number of edges in a shortest path between vertices u and v in V. Let the maximum value of d(u,v) u, v∈V such that u≠v, be 30. Let T be any breadth-first-search tree of G. Which ONE of the given options is CORRECT for every such graph G?

The height of T is exactly 15.

The height of T is exactly 30.

The height of T is at least 15.

The height of T is at least 30.

Ques 5 Algorithms

The maximum value of x 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)

Ques 6 Compilers

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

Symbol table is responsible for keeping track of the scope of variables.

Symbol table can be implemented using a binary search tree.

Symbol table is not required after the parsing phase.

Symbol table is created during the lexical analysis phase.

Ques 7 Compilers

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

Run-time function call management

Strength reduction

Constant folding

Ques 8 Compilers

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

For a production A→ε, ε will be added to First.

If there is any input right end marker, it will be added to First(S), where S is the start symbol.

For a production A→ε, ε will be added to Follow(A).

If there is any input right end marker, it will be added to Follow(S), where S is the start symbol.

Ques 9 Compilers

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=t1+j
1005:	t3=8*t2
1006:	t4=t3-88
1007:	a[t4]=0.0
1008:	j=j+1
1009:	if j<=10 goto 1003
1010:	i=i+1
1011:	if i<=10 goto 1002
1012:	i=1
1013:	t5=i-1
1014:	t6=88*t5
1015:	a[t6]=1.0
1016:	i=i+1
1017:	if i<=10 goto 1013

Ques 10 Computer Networks

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

OSI Layers	Functionalities
(a) Network layer	(I) Packet routing
(b) Transport layer	(II) Framing and error handling
(c) Datalink layer	(III) Host to host communication

(a)-(I), (b)-(II), (c)-(III)

(a)-(I), (b)-(III), (c)-(II)

(a)-(II), (b)-(I), (c)-(III)

(a)-(III), (b)-(II), (c)-(I)

Ques 11 Computer Networks

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 following option(s) is/are TRUE with respect to TCP header flags that are set in the packets?

P3: SYN=1, ACK=1

P2: SYN=1, ACK=1

P2: SYN=0, ACK=1

P1: SYN=1

Ques 12 Computer Networks

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?

Subnet Address	Subnet Mask (in CIDR notation)	Interface
145.36.0.0	/16	E1
145.36.128.0	/17	E2
145.36.64.0	/18	E3
145.36.255.0	/24	E4
Default	..	E5

Ques 13 Computer Networks

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 is independent of one another. The probability that the message is delivered error-free to the destination is ______ (rounded off to three decimal places)

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT GATE 2025 SET-1 Questions with Answer