CS : Computer Science and Information Technology

GATE Paper 2022  Solutions

Answer Key

General Aptitude

1. (D) 2. (C) 3. (D) 4. (A) 5. (B)

6. (B) 7. (D) 8. (D) 9. (B) 10. (D)

Computer Science and Information Technology

11. (A) 12. (D) 13. (D) 14. (A) 15. (A)

16. (B) 17. (A) 18. (B) 19. (C) 20. (C)

21. (D) 22. (C) 23. (B),(C),(D) 24. (A),(B),(D) 25. (A),(B)

509 to
26. (A),(D) 27. (A),(B),(C) 28. 29. 5 to 5 30. 36 to 36
509
0.85 to 0.5 to
31. 8 to 8 32. 7 to 7 33. 34. 35. 4 to 4
0.85 0.5

36. (A) 37. (D) 38. (C) 39. (A) 40. (C)

41. (B) 42. (D) 43. (A) 44. (A) 45. (D)

46. (A),(B),(C) 47. (A),(B),(C) 48. (B),(C),(D) 49. (A),(B),(C) 50. (A),(B),(C)

51. (A),(B),(C) 52. (A) 53. (A),(C),(D) 54. (A),(B),(D) 55. (B),(D)

7.07 to
56. 2 to 2 57. 0.5 to 0.5 58. 24 to 24 59. 60. 33 to 33
7.09
1.42 to 153 to
61. 62. 0 to 0 63. 64. 0.6 to 0.6 65. 80 to 80
1.45 153

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.548

 GATE PAPER 2022Solutions

General Aptitude
1. (D)
The fare is too high for it to be considered fair.

2. (C)

1  3 1  3
Area = 2 3    1 1  
3 4 3  4
2 5 1
=  3  1
3 12 4
2 15 1
=  
3 12 4
8  15  3
=
12
26 13
= 
12 6

3. (D)
r be the root of the equation x2 + 2x + 6 = 0
so it will satisfy
r2 + 2r + 6 = 0 ….(1)
Now, (r + 2) (r + 3) (r + 4) (r + 5)
 (r2 + 5r + 6) (r2 + 9r + 20)
 (r2 + 2r + 6 + 3r) (r2 + 2r + 6 + 7r + 14)
 (0 + 3r) (0 + 7r + 14)
 3r(7r + 14)
 21(r2 + 2r) = 21(6)
 126

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.549

Vidyalankar : GATE/CS

4. (A)

1. All students are inquisitive.

2. Some students are inquisitive.

If all are true then some also true so first and second can be true simultaneously.

3. No student is inquisitive.
4. Some students are not acquisitive.

If some students are in inquisitive true then some students are not inquisitive is also
true. Second and fourth can be true simultaneously.
5. (B)
A word, sentence or a number that reads the same backward or forward.
Ex. RADAR
MADAM
REFER
12321
So, option (B) R A R (after rotating 2nd and 3rd plates) is a palindrome.

6. (B)
Metrics are useful in organizations with good work culture

7. (D)
Let total candidates appeared = x
Appeared boys = 65% x = 0.65x
Appeared girls = 35% x = 0.35x
Let total qualified = y

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.550

 GATE PAPER 2022Solutions

qualified boys = 40% y = 0.4y

qualified girls = 0.65%y = 0.6y
Option (D) is correct because 0.6y > 0.4y.

8. (D)
G  Green
O  Orange

3 2 2 2
P(E)   
5 4 5 5
3 4 23
=  
10 25 50

9. (B)
Using above information we can draw,

S can’t be place at a corners because PR is parallel with QS.

10. (D)

R3  First additional Rope

R4  Second additional Rope
R5  Third additional Rope
So, using 3 additional ropes. We are able to divide into 4 similar shape plots.

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.551

Vidyalankar : GATE/CS

Computer Science and Information Technology

11. (A)
Growth rate of exponential function is greater than polynomial function.
Thus, f(n2) = (f(n)2), when f(n) is a polynomial.

12. (D)
Given finite automation,

(P + Q)* (ab* + ba*)

(ab*b + ba*a) * (ab* + ba*)

13. (D)
We can create a LR parsser to pass a DCFL language. Sometime LR parser cannot
parse context free language( CFL) because CFL are sometime inherently ambiguous
and we cannot design a LR parser for ambiguous grammar. So, LR(1) is sufficient for
DCFL.
• Symbol table can be accessed in all phases of compiler.
• Data flow analysis is necessary in codeoptimization.
• LALR may have reduce-reduce conflict even if CLR don’t have any RR conflict
(conflict arising due to merging of states where lookaheads are same).

14. (A)
At last one of the following holds in BCNF.
(i)    is a trivial functional dependency i.e   .
(ii)  is a superkey.

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.552

 GATE PAPER 2022Solutions

Thus, a relation with only two attribute must be in BCNF.

BCNF decomposition doesn’t preserve functional dependencies.
It is not mandatory that every relation has at least one non-prime attribute.
If all attributes of relation are prime attribute, then the relation is always in 3NF.
15. (A)
Three pointers are required to reverse the linked list.
So, in worst case (n) time required to reverse the linked list.

16. (B)
Number of keys = n
Number of slots = m
As per question, we need to find out number of expected keys in a slot, i.e. each slot
how many keys are possible.
n
So, each slot expected key should be .
m
17. (A)
In programmed I/O CPU time is wastes.
In interrupt driven I/O at particular time interval CPU check the interrupt and CPU
transfer the data to memory as per interrupt requirement. But it doesn’t transfer the
data with maximum throughput.
In polling based I/O, the I/O device is continuously poll by asking whether it needs
CPU or not. So it also transfer data to main memory with low throughput.
DMA based I/O transfer doesn’t involved CPU for transferring data to main memory
and its throughput is maximum.
18. (B)
Given two four bit registers R1 and R2.
(A) R1 = 1011
R2 = 1110
R1 + R 2 = 1 0 1 1
1 1 1 0

1 0 0 1

No overflow occurred, because sign bit is same for (R1 + R2)

(B) R1 = 1100
R2 = 1010
R1 + R 2 = 1 1 0 0
1 0 1 0

0 1 1 0

Overflow occurred, because sign bit is different for (R1 + R2).

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.553

Vidyalankar : GATE/CS

(C) R1 = 0011
R2 = 0100
R1 + R 2 = 0 0 1 1
0 1 0 0

0 1 1 1

No overflow occurred, because sign bit is same for (R1 + R2).

(D) R1 = 1001
R2 = 1111
R1 + R 2 = 1 0 0 1
1 1 1 1

1 0 0 0
No overflow occurred, because sign bit is same for (R1 + R2).

19. (C)
Given threads are T1, T2 and T3 and three binary semaphore variable is used for
synchronization S1, S2 and S3.
T1 T2 T3

while (true) { while (true) { while (true) {

wait (S3); wait (S1); wait (S2);
print (C) ; print (B) ; print (A) ;
signal (S2) ; signal (S3) ; signal (S1) ;

Given sequence need to print,

BCABCABCA...
First element in this sequence is ‘B’. It means thread T2 should execute first.
Thus, at this moment
S1 = 1, S2 = 0, S3 = 0

20. (C)
The trace of a matrix is the sum of the diagonal elements of the matrix.
• In this question, property of trace is used that is trace of product (AB) = trace of
product (BA)
• Statement I  it said tr (Amn  Bnm) = tr(Bnm  Amn)
Let take example,
 1 4
 1 2 3
  ,B   2 5 
 4 5 6  2 3  3 6  32
14 22 
tr(AB) 14  7791
32 77 

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.554

 GATE PAPER 2022Solutions

17 22 27 
tr(BA)22 29 36  = 17 + 19 + 45 = 91
27 36 45 
91 = 91
StatementI is correct.
StatementII
tr(Cnn  Dnn) = tr(Dnn  Cnn)
Take example,
2 2   1 2
C  ,D   
 3 5  2 2  3 4  2 2
 8 12 
tr(CD) 82634
18 26 
 8 12 
tr(DC) 26  8  34
18 26 
StatementII is also true.
21. (D)

2000 0 1 4000
Compute
 1 , z 10 11 , Null (Line 1)
x 3000 3002 p

x 0 1 p
Compute
 1 , z 10 11 , Null 2000 (Line 2)
2000 3000 3002 4000
x 0 1 p
Compute
 1 10 , z 10 11 , 2000 (Line 3)
2000 3000 3002 4000
x 0 1 p
Compute
 10 , z 10 11 , 3002 (Line 4)
2000 3000 3002 4000
 *(&z[0] + 1) + = 3
 *(3000 + 1) + = 3
 *(3002) + = 3
 (11)+ = 3
 14
x z[0] z[1] p
 10 10 11 , 3002
2000 3000 3002 4000

 x = 10
z[0] = 10
z[1] = 14

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.555

Vidyalankar : GATE/CS

22. (C)
Given an enterprise network with two Ethernet segments, a web server and a firewall
connected via three routers. Each interface of router formed a subnet.

Number of subnet = 6

23. (B),(C),(D)
(A) It is not necessary that every subset of a recursively enummable language is
recursive.
(B) If language L and its complement ( L ) both are recursively enumerable then L
must be recursive.
(C) Context-free language is recursive so its complement is also recursive.
(D) Regular languages are closed under intersection, so their intersection must be
deterministic context-free.\

24. (A),(B),(D)
In write through policy, all the write operation is made in main memory and cache
memory simultaneously, ensure that main memory is valid.
In write back policy, at the time of block replacement when dirty bit is set on the line
changes is written back into the memory.
The cache eviction is a strategy in which the data is removed from the cache.
(i) To make room for more relevant cache entries.
(ii) To shrink the cache to make available more RAM for other users.
(A) In write back, dirty bit is set for those lines which are updated.
In write through, no dirty bit is required. Hence option (A) is FALSE.
(B) In write back, data transfer from cache to memory is required at the time of block
replacement, i.e. when eviction required. Hence, option (B) is FALSE.
(C) In write through, no need to do eviction of a block from cache. So there is no data
transfer required from cache to main memory. Hence, option (C) is TRUE.
(D) For read/write misses in write back, a line needed to be evicted for the newly
fetched block. Hence, option (D) is false.

25. (A),(B)
Given three relation,
Employee(eId, Name)
Brand(bId), bName)
Own(eId, bId)
Need to find “set of eIds who own all the brands”.
Required answer,
eId(eId,bId (own) / bId (Brand))
eId(own)  eId ((eId (own)  bId (Brand))  eId, bId (own))

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.556

 GATE PAPER 2022Solutions

26. (A),(D)
(A) Circular wait is a necessary condition for the formation of deadlock.
(B) No deadlock occurred when more than one instance of resource exist.
(C) An unsafe state doesn’t leads to deadlock.
(D) If there is no request edge then no deadlock.

27. (A),(B),(C)
(A) (xy)2 = x2y2
 xy xy = xx yy
Take x1 and y1 on both side.
x1 xy xy y1 = x1 xx yyy1
yx = xy, so it is commutative.
(B) x  G, x2 = 1 then G is
xx = 1  x = x1
If every element has its own inverse in a graph, then graph is commutative.
(C) If the order of ‘G’ is 2 means it is order of prime, so ‘G’ is commutative.
(D) If G is commutative then the subgroup is G is also commutative.
Let take I is a subgroup of G, if e, f  I, we have e, f  G, then ef = fe. So, I is
commutative.

28. 509 to 509

Given binary search tree with 1000 distinct elements. And the tree is stored using the
array representation of binary heap trees. Array indices start with 0.
Index number of first node at each level can be found by (2h –1), where h is the
height of the tree.
And, Number of node at each level can be find out by (2n –1), where n is the number
of level.

At 10th level number of nodes = 210–1 = 512.

At height 9, index number of first node = 29 – 1 = 511
Since, total number of node is 1000, so we need to check upper level. Because
rightmost number in binary seachtree is maximum.
At 9th level, no. of nodes = 291 = 256.
At high 8, index no. of first node = 281 = 255 .
Index number of last node in 9th level, = 255 × 2 = 510

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.557

Vidyalankar : GATE/CS

Required answer is 509.

29. 5 to 5
Apply augmented grammar is :

30. 36 to 36
We are given that vertices = n
The maximum number of possible edges in an undirected graph with ‘n’ vertices and
‘k’ components is :
Example :
To get maximum edges, take one vertex each for each complement, except last
component.
Now, (K–1) components have 1 vertex each and last component has n–(K–1)
vertices. Make the last component complete i.e. it has
n  (k 1) (n  K)(n  K  1)
C2 
2
(n  K)(n  K  1)
Number of edges (e) =
2
Complement (K) = 2
(10  2)(10  2  1)
=
2
89
= 36
2
31. 8 to 8
Given three functional dependencies,
AB  C
BC  D
CE

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.558

 GATE PAPER 2022Solutions

Compute closure of attribute,

(AB)+ = {A, B, C, D, E}
(BC)+ = {B, C, D, E}
C+ = {C, E}
Only one candidate key is possible for given relation : {A B}
Superkey can be found by adding any combination of attribute {C, D, E} with
candidate key (AB).
Number of possible combination with candidate key required = 23 = 8.

32. 7 to 7
So, balls and bins are identical, the possible ways are :
We have three bins.
B1 B2 B3
6 0 0
5 1 0
4 1 1
4 2 0
3 2 1
3 3 0
2 2 2
Total ways is 7.

33. 0.85 to 0.85

Cache memory hit rate = 0.8
Access Latency = 10 nsec.
Miss penalty = 100 nsec.
Optimization increases cache access latency to 15 nsec.
Miss penalty is not affected.
Average memory access time in first case
= 0.8 ×10 + (1 – 0.8) × 100 = 28 n sec
Average memory access time in second case
= x × 15 + (1 – x) × 100 = 28
15x + 100 – 100x = 28
85x = 72
72
x= = 0.85
85

34. 0.5 to 0.5

x
lim 
x  0 1  e2 x

0 0
 put 0 in equation  
1 1 0
Apply L’ hospital rule, we get (differentiate numerator and denominator)

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.559

Vidyalankar : GATE/CS

1
 lim 2 x
x  0 2
0  e2 x 
2 x
1
x
 lim 2
x  0 1
2e2 x

2 x
1
 lim
x  0 2e2 x

1
   0.5
2

35. 4 to 4
Given domain name,
[Link]
Iterative query mechanism is used in the resolution,

There are 4-pairs involved in completely resolving the domain name.

36. (A)
n  1, nisodd
an  
 1, otherwise
(n  1)(n  K  1)
a 0  a1x  a 2 x 2  a 3 x 3  a 4 x 4  a 5 x 5  ....
2
= 12xx 2  4x 3  x 4  6x 5  ....
= (1xx 2  x 3  ...)x(13x 2  5x 4  ...)

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.560

 GATE PAPER 2022Solutions

1 d
=  x (xx 3  x 5  ...)
(1  x) dx
1 d  x 
= x  
(1  x) dx  (1  x 2 ) 
1 x(1  x 2 )
= 
(1  x) (1  x 2 )2

37. (D)
All pair shortest paths for adjacency matrix = Anij .
Anij = n vertices can walk from i  j.
Since, the cycle has 3 vertices and it is counted for every vertex, we need to divide
Aij3
by 3. To get the three vertex loop for directed graph = .
3
For undirected graph, A-B-C-A is same as A-C-B-A cycle. So, 2 possibility will be
formed.
Aij3 Aij3
The number of 3-cycle for undirected graph is  .
32 6
38. (C)
(A) TLB perform parallel search.
(B) TLB hit means word will always present in main memory.
(C) Inverted Page Table
Frame 0 Process Page

Frame 1 Process Page

Memory access time using inverted page table is not some because in inverted
page table no indexing is applied and there is no equal linear searching. So, this
statement is false.
(D) Virtual address  entry number.

If they map to same value while hashing, there memory access time of
addresses will not same because there is a chance that some elements are
present at the end of linked list.

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.561

Vidyalankar : GATE/CS

39. (A)
Given schedule S with four transactions,

T1 T2 T3 T4
R4(x)
R2(x)
R3(x)
R1(y)
W1(y)
W2(x)
W3(y)
R4(y)

Thus, T1  T3  T4  T2

40. (C)
Given digital display system, in which 16-bit code word is used.
S is a 1024-word memory segment.
R is a 32-word register file.
So, there are 10-input required for decoder P and output of decoder P is 210.
Similarly, there are 5-input required for decoder Q and output of decoder Q is 25.
And T is a multiplexer, which takes 2 input and gives 1 output.

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.562

 GATE PAPER 2022Solutions

P  10:210 decoder
R  5:25 decoder
T  2:1 Multiplexer

41. (B)
C=A+B
RA = 0  C1400000  1100 0001 0100 00000
RB = 0  42100000  0100 0010 0001 00000
RC = 0  41400000  0100 0001 0100 00000
If you see carefully A and C are changes only in sign bit.
IEEE754 single precision = (1)S1.M2E127.
In every register, first bit is sign bit, next 8 bit is for exponent, and after that remaining
bit is mantissa.
RA = 1100 0001 01000 00000
= Sign = ()
= Exponent = 130
= (1)1 1.1  2130127
= 1.1  23
= (1100)2 = 12
RC = Similarly RC = +12 because only difference is sign bit.
RB = 0100 0010 0001 00000
= Sign = (+)
= Exponent = 132
= +1.001  2132127
= +1.001  25
= +(100100) = +36
So, false option is C = A + B

42. (D)
Given four processes P, Q, R and S.
Scheduling algorithm : Round Robin
Time quanta = 4 time unit.
All the processes arrives at time t = 0.
(i) Exactly one context switch from S to Q.
(ii) Exactly one context switch from R to Q.
(iii)Exactly two context switch from Q to R.
(iv) No context switch from S to P.
(v) Switching to a ready process after the termination of another process is also
considered a context switch.
(A)

(B)

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.563

Vidyalankar : GATE/CS

(C)

(D)

In option (D), there is no context switching exist from R to Q.

43. (A)
X[3] [3] [3]

Three 2-D arrays

Three 1-D array in
each 2-D array
Three element in
each 1-D array

0 1 2 0 1 2
a[0] a[1]
0 1 2 3 0 10 11 12
1 4 5 6 1 13 14 15
2 7 8 9 2 16 17 18

0 1 2
a[2]
0 19 20 21
1 22 23 24
2 25 26 27
a[000] = 1
a[001] = 2
a[002] = 3
a[100] = 10
a[101] = 11
a[102] = 12
a[200] = 19
a[201] = 20
a[202] = 21

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.564

 GATE PAPER 2022Solutions

44. (A)
Step-I  80 120 because we take small ‘p’ and capital ‘X’.
a b
char c  (a & b) + ‘*’
 Bitwise & = (80 & 120) + 42
 80 = 1010000
120 = 1111000
a&b = 1010000 = 80 + 42 = 12 = z

char d  (a | b) + ‘’
 Bitwise | = (80 | 120) + 45
 80 = 1010000
120 = 1111000
a | b = 1111000 = 120  45 = 75 = K

Char e  (a  b) + ‘+’
 Bitwise = (80  120) + 43

a  b = 1010000
= 1111000
a  b = 0101000 = 40 + 43 = 83 = S
Print character = (z, K, S)
45. (D)
Let take coefficient matrix,
 1 1 2 
A 1 3 1
 2 1 5 
Perform row-column operation.
R2  R2  R1
 1 1 2 
0 2 1 
 
 2 1 5 
R3  R3  2R1
 1 1 2 
0 2 1 
 
 0 1 1
 1
R3  R3    R2
 2
 
 1 1 2 
 
u0 2 1 
 1
0 0  
 2

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.565

Vidyalankar : GATE/CS

A=Lu
  
 1 1  2   1 1 0   1 0 2 
 1 3 1 1 1 0 0 2 1 
    
 2 1 5   1  1
2  1 0 0  
 2  2
1
u33 = 
2
1
L32 = 
2

46. (A),(B),(C)
(A) Undecidable
(B) Undecidable
(C) Undecidable
(D) Decidable, Turing Machine M decide if language L takes more than 1073 steps.
Language L takes almost 1073 steps. So, it is decidable. Then its complement is
also decidable. Hence, L is decidable.

47. (A),(B),(C)
Given language,
n n
L1 = {a wa | w{a,b}*}
L2 = {wxwR | w, x{a,b)*, |w|, |x|> 0}
Regular expression can be written for the language L1 and L2.
For L1,
(a + b)
For L2,
a(a + b)+ a + b(a + b)+ b
Hence, both language are regular. And regular language are context free.

48. (B),(C),(D)
Option (A) : L1 is not context-free but L2 and L3 are deterministic context-free.
True, L1 is not context-free and L2 and L3 are clearly DCFLs since they have only one
comparison and DPDA can accept both.
Option (B) : Neither L1 nor L2 is context-free.
False, L2 is DCFL and every DCFL is a CFL.
L2  Context-free
L3  Context-free
L2  L3 = {anbncn or ambmcm, m, n  0}
This language is context sensitive language.
Option (C) : L2, L3 and L2 L3 all are context-free
False,
L2  Context-free
L3  Context-free
L2  L3 = {anbncn , n  0}. We cannot compare the anbncn with one single stack.
Hence it is not context-free.

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.566

 GATE PAPER 2022Solutions

Option (D) : Neither L1 nor its complement is context-free.

False, L1  Not context-free
L1 Complement of L1 is accepted by a context-free grammar is CFL.
Hence the correct answer is option (B), (C), (D).

49. (A),(B),(C)
(A) : True
(B) : True
(C) : True
(D) : No, G cannot have multiple minimum spanning trees when all the edges are
distinct.

50. (A),(B),(C)
(A) Yes, it is true.

(B) Peterson graph has Hamiltonian path but not Hamiltonian cycle.
(C) Yes, it is isomorphic to the given graph.
Step-I

(D) Vertex independent set is a set of vertices which are not adjacent.
Maximum vertex independent set is a set in which we cannot add one more
vertex to it. So, largest independent set of Peterson graph is 4.

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.567

Vidyalankar : GATE/CS

51. (A),(B),(C)
Eliminating option is the way for solving this question  f(2n) is even function and
f(2n + 1) is add function.
f(1) = 1
f(2) = f(2*1) = 2f(1)  1 = 2  1 = 1 [f(2n) = 2f(n)  1]
f(3) = f(2*2 + 1) = 2*f(1) + 1 = 3 [f(2n + 1) = 2(n) + 1]
f(4) = f(2*2) = 2f(2)  1 = 2*1  1 ] 1
f(5) = f(2*2 + 1) = 2f(2) + 1 = 2*1 + 1 = 3
f(6) = f(2*3) = 2f(3)  1 = 2*3  1 = 5
f(7) = f(2*3 + 1) = 2f(3) + 1 = 7
f(8) = f(23) = f(2*4) = 2f(4)  1 = 2*1  1 = 1
f(9) = f(2*4 + 1) = 2f(4) + 1 = 2*1 + 1 = 3
f(10) = f(5*2) = 2f(5)  1 = 2*3  1 = 5
.
.
.
.

f(20) = f(5*4) = f(10*2) = 2f(10)  1 = 2*5  1 = 9

 Computation of f(2), f(4) and f(8) show that f(2n) = 1 is correct.
 Computation of f(3) and f(7) show that f(2n  1) = 2n  1 is correct.
 Computation of f(10) and f(20) show that f(5.2n) = 2n+1 + 1 is correct.
 Computation of f(5) and f(9) show that f(2n + 1) = 2n + 1 is not correct.

52. (A)
p

Consider a graph  q

r
p q r
p 0 1 0
K is adjacency matrix = q  1 0 1
r  0 1 0 

0 1 0  0 1 0 
K =  1 0 1 1 0 1
2

 0 1 0  0 1 0 

 1 0 1
=  0 2 0 
 1 0 1

Degree sequence of (p, q, r) = (1, 2, 1)

Diagonal elements= (1, 2, 1)

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.568

 GATE PAPER 2022Solutions

53. (A),(C),(D)
Use AX = X in each options.
 = Scalar quantity.
(A) AX = X
 9 6 2 4   1  1
 8 6 3 1  1   1 
     AX = 1X
 20 15 8 5   0   0 
    
 32 21 7 12   1   1 
(B) AX = X
 9 6 2 4   1   7 
 8 6 3 1  0   5 
     AX  X
 20 15 8 5   1 12 
    
 32 21 7 12   0  25 
(C) AX = X
 9 6 2 4   1  1
 8 6 3 1  0   
  3  0   AX = 3X
 20 15 8 5   2  2
    
 32 21 7 12   2  2
(D) AX = X
 9 6 2 4   0  0  0
 8 6 3 1  1  3   
    3  1   AX = 3X
 20 15 8 5   3  9   3 
      
 32 21 7 12   0  0  0

54. (A),(B),(D)
Cache Memory Size = 2 KB
Main Memory Size = 64 KB
Block Size = 64 B
CacheMemorySize
Number of Lines =
BlockSize
2K 211
=  25
64 26
16 bit

Number of Word
tag
lines Offset
5 bit 5 bit 6 bit

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.569

Vidyalankar : GATE/CS

P:(A248)H 1010 0010 0100 1000; 9th block

Q:(C284)H 1100 0010 1000 0100; 10th block

R:(CA8A)H 1100 1010 1000 1010; 10th block

S:(A262)H 1010 0010 0110 0010; 9th block

But P&S are from same memory block (10100).

0

1st 2nd
8 P:M P : Hit
9 Q:M Q:M
P
10 R:M R:M
11 S : Hit S : Hit
R

• Every access of S is hit.

• Once P is brought to the cache it is never evicted.
• Every access to R evicts Q from cache.

55. (B),(D)
Given routing table,
1. [Link] [Link]
12.20.10100100.00000000
2. [Link] [Link]
12.20.10101010.00000000
3. [Link] [Link]
12.20.10101000.00000000
4. [Link] [Link]
12.20.10100110.00000000
Subnet (2) and (3) can be aggregated.
12.20.10101010.00000000
12.20.10101000.00000000
Network id Host id
[Link]/22
Subnet (1) and (4) can be aggregated
12.20.10100100.00000000
12.20.10100110.00000000
Network id Host id
[Link]/22

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.570

 GATE PAPER 2022Solutions

56. 2 to 2
Given schemes,
Student(SNO, SName, dNo)
Dept(dNo, dName)
Course(CNO, CName, dNo)
Register (SNo, CNo)
Select * from student as S where NOT EXIST
(select CNO from course where dNo = “DO1”
EXCEPT
Select CNO FROM Register WHERE SNO=[Link])
In above case, first inner query return is independent and return <{C11, C12>.
Second inner query is dependent on student relation. The condition is sNo = [Link].
So, for sNo = S01, second inner query returns <C11, C12>. And the except operation
between two inner query gives empty result.
Except operation : R1 EXCEPT R2 = R1  (R1  R2)
Now, NOT EXIST returns TRUE and outer query gives <S01, James, D01> as
output.
When second inner query is checked for sNo = S02. It return <C11>. And the except
operation between two inner query gives non-empty result. AND NOT EXISTS gives
FALSE result. And outer query doesn’t give any result.
Similarly for sNo = S04, outer query gives output <S04, jane, D01>.
Hence 2 rows found.
57. 0.5 to 0.5

When link between Q and R is broken.

When Node P receives triggered update first from Q, then P successfully updated.

In this case no issue observed and count-infinity problem doesn’t arised.

If node Q receives update first from node P.

So, routing table of Q is updated and it causes count-infinity problem.

So, out of two node, one node is responsible for count-to-infinity issue.
So, the probability of a routing loop formation between P and Q is 0.5.

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.571

Vidyalankar : GATE/CS

58. 24 to 24
Given vertex,
V = {1, 2, 3, 4, 5}
A matrix ‘A’ is given in such a way that,
 1 1 j i 5
A[i ][j]
0 Otherwise
i
 
12345
1 1 0 0 0 0 
2 1 1 0 0 0 
j3 1 1 1 0 0 
 
4 1 1 1 1 0 
5 1 1 1 1 1

Directed spanning tree rooted at vertex 5 is 4 × 3 × 2 × 1 = 24

59. 7.07 to 7.09

Given, Bandwidth = 100 Mbps
Distance = 2100 Km.
Propagation speed = 3  108 m/sec
Packetsize 1000bytes
Time taken to receive the packet = 
Bandwidth 100Mbps
10008bits
=
100106 bits / sec
= 0.08 Msec.
Distance
Propagation time =
Propagation speed
2100Km
=
3108 m / sec
2100103 m
=
3108 m / sec
= 7  103 sec
= 7 m sec.
Required time = 7 + 0.08 = 7.08 m sec

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.572

 GATE PAPER 2022Solutions

60. 33 to 33
230
Bandwidth = 1 GbPS = bytes/sec
8
Maximum segment lifetime (MSL) = 60 seconds
Totalsequencenumber
Wrap around time =
Bandwidth
Wrap around time > Maximum segment lifetime
Number
Total sequence > Maximum segment life time.
Bandwidth
Suppose, minimum number of bits required for the sequence number field = x.
2x
60
230
1
8
60  230
2x 
8
 60  230 
log 2x log  
 8 
x > log 60 + 30  log 8
Minimum value of x = 30 + 5.9  3  33

61. 1.42 to 1.45

Cycle time (tp) = 2 GHz = 0.5 nanoseconds
K = 5, X1  without branch prediction.

CPI = 1 + Number of stalls instruction = 1 + (0.3)  2 = 1.6

Average instruction execution time
= CPI  Cycle time
= 1.6  0.5 n sec
= 0.8 ns.
X2  “If BPU predicted correct branch then it eliminate stalls but if BPU predicted
wrong branch then BPU not add any additional stalls but remaining stalls we present.”

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.573

Vidyalankar : GATE/CS

CPI = 1 + (0.3  0.2  2)

= 1.12
Average instruction execution time = CPI  Cycle time
= 1.12  0.5 ns = 0.56 ns
0.8
Speed up =  1.42
0.56

62. 0 to 0
Given queues Q1 and Q2
Head

Q1 1 2 3 4

Q2

Head

Traverse head of Q2 at the end of queue so Queue format becomes,

Head

Q1 1 2 3 4

Q2

Head
Now perform dequeue operation in Q1 at head position and perform enqueue
operation in Q2 at head position.
Step (1) :

Q1 : 1 2 3 4

Head

Q2 : 1

Head

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.574

 GATE PAPER 2022Solutions

Step (2) :

Q1 : 1 2 3 4

Head

Q2 : 2 1

Head
Step (3) :

Q1 : 1 2 3 4

Head

Q2 : 3 2 1

Head

Step (4) :

Q1 :

Q2 : 4 3 2 1

Head
Thus, there are zero enque operation performed on queue Q1.

63. 153 to 153

For linked allocation, we need to access the block from 1 to 50, new block access
that should insert between 50 and 51 block, and access 51 block. So, the total
access is 52.

For contiguous allocation, we have 100 block, in contiguous allocation first we push
the 100th block to 101th block (we need two access), then we push 99th block to

GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.575

Vidyalankar : GATE/CS

100th block (we need two access again) and so on upto 51th block. Now, 51 block is
empty, then we push new block to 51 position list need one access). So, total access
are
50

 2  
1 1001101
(For51to100block) fornewblock

Total required access are 101 + 52 = 153.

64. 0.6 to 0.6

Given page reference string,
7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7, 1, 5, 6, 1
Numberofpagefaults
Page fault rate =
Numberofmemoryaccess
There are four page frames are given and LRU page replacement policy is used.

7 2 7 3 2 5 3 4 6 7 7 1 5 6 1
5 5 5 7 7 7
3 3 3 3 3 1 1
2 2 2 2 6 6 6 6
7 7 7 7 4 4 4 4 5

Number of page fault = 9

Number of memory access = 15
9
Page fault rate =  0.6
15

65. 80 to 80
S  S1 # T {[Link] = [Link] * [Link]}
ST {[Link] = [Link]}
T  T1%R {[Link] = [Link]  [Link]}
TR {[Link] = [Link]}
Rid {[Link] = [Link]}
 20  10  5  8  2  2
Rule 1 : has higher priority then * because it is away from starting symbol.
Rule 2 : Both ( and *) are left associative.
= 20  10  5  8  2  2
= 20  2  4  2
= 20  2  2
= 40  2
= 80



GATE/CS/EQ_Soln/GATE Paper 2022Soln/Pg.576