Computer Science Gate 2022 Questions

A palindrome is a word that reads the same forwards and backwards. In a game of words, a player has the following two plates painted with letters.

From the additional plates given in the options, which one of the combinations of additional plates would allow the player to construct a five-letter palindrome. The player should use all the five plates exactly once. The plates can be rotated in their plane.

a)
b)
c)
d)

The ______is too high for it to be considered ______.

a) faer / fair
b) fair / fare
c) fare / fare
d) fare / fair

A plot of land must be divided between four families. They want their individual plots to be similar in shape, not necessarily equal in area. The land has equally spaced poles, marked as dots in the below figure. Two ropes, R1 and R2, are already present and cannot be moved. What is the least number of additional straight ropes needed to create the desired plots? A single rope can pass through three poles that are aligned in a straight line.

a) 2
b) 4
c) 5
d) 3

Let r be a root of the equation x² + 2x + 6 = 0. Then the value of the expression (r+2) (r+3)(r+4)(r+5) is

a) -51
b) 51
c) -126
d) 126

Given below are four statements.
Statement 1: All students are inquisitive.
Statement 2: Some students are inquisitive.
Statement 3: No student is inquisitive.
Statement 4: Some students are not inquisitive.
From the given four statements, find the two statements that CANNOT BE TRUE simultaneously, assuming that there is at least one student in the class.

a) Statement 1 and Statement 3
b) Statement 1 and Statement 2
c) Statement 2 and Statement 4
d) Statement 3 and Statement 4

Some people believe that “what gets measured, improves”. Some others believe that “what gets measured, gets gamed”. One possible reason for the difference in beliefs is the work culture in organizations. In organizations with good work culture, metrics help improve outcomes. However, the same metrics are counterproductive in organizations with the poor work cultures.
Which one of the following is the CORRECT logical inference based on the information in the above passage?

a) Metrics are useful in organizations with poor work culture
b) Metrics are useful in organizations with good work culture
c) Metrics are always counterproductive in organizations with good work culture
d) Metrics are never useful in organizations with good work culture

In a recently conducted national entrance test, boys constituted 65% of those who appeared for the test. Girls constituted the remaining candidates and they accounted for 60% of the qualified candidates.

Which one of the following is the correct logical inference based on the information provided in the above passage?

a) Equal number of boys and girls qualified
b) Equal number of boys and girls appeared for the test
c) The number of boys who appeared for the test is less than the number of girls who appeared
d) The number of boys who qualified for the test is less than the number of girls who qualified

A box contains five balls of same size and shape. Three of them are green coloured balls and two of them are orange coloured balls. Balls are drawn from the box one at a time. If a green ball is drawn, it is not replaced. If an orange ball is drawn, it is replaced with another orange ball.

First ball is drawn. What is the probability of getting an orange ball in the next draw?

a) ¹⁄₂
b) ⁸⁄₂₅
c) ¹⁹⁄₅₀
d) ²³⁄₅₀

The corners and mid-points of the sides of a triangle are named using the distinct letters P, Q, R, S, T, and U, but not necessarily in the same order. Consider the following statements:

i)The line joining P and R is parallel to the line joining Q and S.
ii)P is placed on the side opposite to corner T.
iii)S and U cannot be placed on the same side.
Which one of the following statements is correct based on the above information?

a) P cannot be placed at a corner
b) S cannot be placed at a corner
c) U cannot be placed at a mid-point
d) R cannot be placed at a corner

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

a) (ab*bab*+ ba*aba*)
b) (ab*b)*ab+(ba*a)* ba*
c) (ab*b+ ba*a)* (a*+b*)
d) (ba*a+ ab*b)* (ab*+ba*)

Which of the following is/are undecidable?

a) Given two Turing machines M₁and M₂, decide if L(M₁)=L(M₂).
b) Given a Turing machine M, decide if L(M) is regular.
c) Given a Turing machine M, decide if M accepts all strings.
d) Given a Turing machine M, decide if M takes more than 1073 steps on every string.

Consider the following languages:

a) L1 is not context-free but L2 and L3 are deterministic context-free.
b) Neither L1 nor L2 is context-free.
c) L2, L3, and L2 ∩ L3 all are context-free.
d) Neither L1 nor its complement is context-free.

Which of the following statements is/are TRUE?

a) Every subset of a recursively enumerable language is recursive.
b) If a language L and its complement L are both recursively enumerable, then L must be recursive.
c) The complement of a context-free language must be recursive.
d) If L1 and L2 are regular, then L1∩ L2 must be deterministic context-free.

What is printed by the following ANSI C program?

a) 1  2  3
10 11 12
19 20 21

b) 1  4   7
10 13 16
19 22 25

c) 1 2 3
4 5 6
7 8 9

d) 1   2   3
13 14 15
25 26 27

What is printed by the following ANSI C program?

a) 1,10,11
b) 1,10,14
c) 10,14,11
d) 10,10,14

Consider three floating-point numbers A, B, and C stored in registers RA, RB, and RC, respectively as per IEEE-754 single-precision floating-point format. The 32-bit content stored in these registers (in hexadecimal form) is as follows.

RA= 0xC1400000
RB = 0x42100000
RC = 0x41400000

Which one of the following is FALSE?

a) A+ C= 0
b) C= A+B
c) B = 3C
d) (B-C)> 0

Consider a system with 2KB direct mapped data cache with a block size of 64bytes. The system has a physical address space of 64KB and a word length of 16bits. During the execution of a program, four data words P, Q, R, and S are accessed in that order 10 times (i.e., PQRSPQRS…). Hence, there are 40 accesses to data cache altogether. Assume that the data cache is initially empty and no other data words are accessed by the program. The addresses of the first bytes of P, Q, R, and S are 0xA248, 0xC28A, 0xCA8A, and 0xA262, respectively. For the execution of the above program, which of the following statements is/are TRUE with respect to the data cache?

a) Every access to S is a hit.
b) Once P is brought to the cache it is never evicted.
c) At the end of the execution only R and S reside in the cache.
d) Every access to R evicts Q from the cache.

Let WB and WT be two set associative cache organizations that use LRU algorithm for cache block replacement. WB is a write back cache and WT is a write through cache. Which of the following statements is/are FALSE?

a) Each cache block in WB and WT has a dirty bit.
b) Every write hit in WB leads to a data transfer from cache to main memory.
c) Eviction of a block from WT will not lead to data transfer from cache to main memory.
d) A read miss in WB will never lead to eviction of a dirty block from WB.

A processor X₁ operating at 2 GHz has a standard 5-stage RISC instruction pipeline having a base CPI (cycles per instruction) of one without any pipeline hazards. For a given program P that has 30% branch instructions, control hazards incur 2 cycles stall for every branch. A new version of the processor X₂ operating at same clock frequency has an additional branch predictor unit (BPU) that completely eliminates stalls for correctly predicted branches. There is neither any savings nor any additional stalls for wrong predictions. There are no structural hazards and data hazards for X₁ and X₂. If the BPU has a prediction accuracy of 80%, the speed up (rounded off to two decimal places) obtained by X₂ over X₁ in executing P is____________.

Which one of the following statements is TRUE?

a) The LALR(1) parser for a grammar G cannot have a reduce-reduce conflict if the LR(1) parser for G does not have reduce-reduce conflict.
b) The symbol table is accessed only during the lexical analysis phase.
c) Data flow analysis is necessary for run-time memory management.
d) LR(1) parsing is sufficient for deterministic context-free languages.

Consider an enterprise network with two Ethernet segments, a web server and a firewall, connected via three routers as shown below.

What is the number of subnets inside the enterprise network?

a) 3
b) 12
c) 6
d) 8

Consider a network with three routers P, Q, R shown in the figure below. All the links have cost of unity.

The routers exchange distance vector routing information and have converged on the routing tables, after which the link Q−R fails. Assume that P and Q send out routing updates at random times, each at the same average rate. The probability of a routing loop formation (rounded off to one decimal place) between P and Q, leading to count-to-infinity problem, is___________

Consider the data transfer using TCP over a 1 Gbps link. Assuming that the maximum segment lifetime (MSL) is set to 60 seconds, the minimum number of bits required for the sequence number field of the TCP header, to prevent the sequence number space from wrapping around during the MSL is____________.

Consider a 100 Mbps link between an earth station (sender) and a satellite (receiver) at an altitude of 2100 km. The signal propagates at a speed of 3x10⁸ m/s. The time taken (in milliseconds, rounded off to two decimal places) for the receiver to completely receive a packet of 1000 bytes transmitted by the sender is_________.

Consider the resolution of the domain name www.gate.org.in by a DNS resolver. Assume that no resource records are cached anywhere across the DNS servers and that an iterative query mechanism is used in the resolution. The number of DNS query-response pairs involved in completely resolving the domain name is________.

Consider the following recurrence:

a) f(2ⁿ–1)=2ⁿ–1
b) f(2ⁿ)=1
c) f(5⋅2ⁿ)=2ⁿ⁺¹+1
d) f(2ⁿ+1)=2ⁿ+1

Which one of the following statements is TRUE for all positive functions f (n) ?

a) f(n²)=θ(f(n)²),when f(n) is a polynomial
b) f(n²)=o(f(n)²)
c) f(n²)=O(f(n)²),when f(n) is a exponential
d) f(n²)=Ω(f(n)²)

Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

a) The best algorithm for the problem takes θ(n) time in the worst case.
b) The best algorithm for the problem takes θ( nlog n) time in the worst case.
c) The best algorithm for the problem takes θ(n²) time in the worst case.
d) It is not possible to reverse a singly linked list in O(1) space.

Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?

a) The diagonal entries of A² are the degrees of the vertices of the graph.
b) If the graph is connected, then none of the entries of A^n-1+I_n can be zero.
c) If the sum of all the elements of A is at most 2(n-1), then the graph must be acyclic.
d) If there is at least a 1 in each of A’s rows and columns, then the graph must be connected.

Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

a) A³
b) A³ divided by 2
c) A³ divided by 3
d) A³ divided by 6

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.

Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index_______

Let Ri(z) and Wi(z) denote read and write operations on a data element z by a transaction Ti, respectively. Consider the schedule S with four transactions.

S: R4(x)R2(x)R3(x)R1(y)W1(y)W2(x)W3(y)R4(y)

Which one of the following serial schedules is conflict equivalent to S?

a) T₁→T₃→T₄→T₂
b) T₁→T₄→T₃→T₂
c) T₄→T₁→T₃→T₂
d) T₃→T₁→T₄→T₂

In a relational data model, which one of the following statements is TRUE?

a) A relation with only two attributes is always in BCNF.
b) If all attributes of a relation are prime attributes, then the relation is in BCNF.
c) Every relation has at least one non-prime attribute.
d) BCNF decompositions preserve functional dependencies.

Consider the following three relations in a relational database. Employee (eId, Name ), Brand (bId, bName), Own (eId, bId ) Which of the following relational algebra expressions return the set of eIds who own all the brands?

a) π_eld(π_eld,bld(own)/π_brand))
b) π_eld(own)-π_eld((π_eld(own)xπ_bld(brand))-π_bld,eld(own))
c) π_eld(π_eld,bld(own)/π_own))
d) π_eld((π_eld(own)xπ_bld(own))/π_bld(brand))

Consider two files systems A and B , that use contiguous allocation and linked allocation, respectively. A file of size 100 blocks is already stored in A and also in B. Now, consider inserting a new block in the middle of the file (between 50th and 51st block), whose data is already available in the memory. Assume that there are enough free blocks at the end of the file and that the file control blocks are already in memory. Let the number of disk accesses required to insert a block in the middle of the file in A and B are n_A and n_B respectively, then the value of n_A + n_B is_________.

Consider a digital display system (DDS) shown in the figure that displays the contents of register X. A 16-bit code word is used to load a word in X, either from S or from R. S is a 1024-word memory segment and R is a 32-word register file. Based on the value of mode bit M, T selects an input word to load in X. P and Q interface with the corresponding bits in the code word to choose the addressed word. Which one of the following represents the functionality of P, Q, and T?

a) P is 10:1 multiplexer; Q is 5:1 multiplexer; T is 2:1 multiplexer
b) P is 10:2¹⁰ decoder; Q is 5:2⁵ decoder; T is 2:1 encoder
c) P is 10:2¹⁰ decoder; Q is 5:2⁵ decoder; T is 2:1 multiplexer
d) P is 1:10 de-multiplexer; Q is 1:5 de-multiplexer; T is 2:1 multiplexer

The following simple undirected graph is referred to as the Peterson graph

Which of the following statements is/are TRUE?

a) The chromatic number of the graph is 3.
b) The graph has a Hamiltonian path.
c) The following graph is isomorphic to the Peterson graph.

d) The size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)

Let R1 and R2 be two 4-bit registers that store numbers in 2’s complement form. For the operation R1+R2, which one of the following values of R1 and R2 gives an arithmetic overflow?

a) R1 = 1011 and R2 = 1110
b) R1 = 1100 and R2 = 1010
c) R1 = 0011 and R2 = 0100
d) R1 = 1001 and  R2 = 1111

Which of the following statements is/are TRUE for a group G ?

a) If for all x, y ∈ G, (xy)² = x² y² then G is commutative.
b) If for all x ∈ G, x²= 1, then G is commutative. Here, 1 is the identity element of G.
c) If the order of G is 2, then G is commutative.
d) If G is commutative, then a subgroup of G need not be commutative.

A function y(x) is defined in the interval [0, 1] on the 𝑥-axis as

a) 5/6
b) 6/5
c) 13/6
d) 6/13

The value of the following limit is ____________

The number of arrangements of six identical balls in three identical bins is______.

a) 36
b) 21
c) 12
d) 7

Consider the following two statements with respect to the matrices A_m×n , B_n×m , C_n×n and D_n×n

Statement 1: tr(AB) = tr(BA)
Statement 2: tr(CD) = tr(DC)
where tr() represents the trace of a matrix. Which one of the following holds?

a) Statement 1 is correct and Statement 2 is wrong.
b) Statement 1 is wrong and Statement 2 is correct.
c) Both Statement 1 and Statement 2 are correct.
d) Both Statement 1 and Statement 2 are wrong.

Consider four processes P, Q, R, and S scheduled on a CPU as per round robin algorithm with a time quantum of 4 units. The processes arrive in the order P, Q, R, S, all at time t = 0. There is exactly one context switch from S to Q, exactly one context switch from R to Q, and exactly two context switches from Q to R. There is no context switch from S to P. Switching to a ready process after the termination of another process is also considered a context switch. Which one of the following is NOT possible as CPU burst time (in time units) of these processes?

a) P=4, Q=10, R=6, S=2
b) P=2, Q=9, R=5, S=1
c) P=4, Q=12, R=5, S=4
d) P=3, Q=7, R=7, S=3

Which of the following statements is/are TRUE with respect to deadlocks?

a) Circular wait is a necessary condition for the formation of deadlock.
b) In a system where each resource has more than one instance, a cycle in its wait-for graph indicates the presence of a deadlock.
c) If the current allocation of resources to processes leads the system to unsafe state, then deadlock will necessarily occur.
d) In the resource-allocation graph of a system, if every edge is an assignment edge, then the system is not in deadlock state.

Consider a demand paging system with four-page frames (initially empty) and an LRU page replacement policy. For the following page reference string 7, 2,7,3, 2,5,3, 4,6,7,7,1,5,6,1 the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one decimal place) is_________.

A cache memory that has a hit rate of 0.8 has an access latency 10 ns and miss penalty 100 ns. Optimization is done on the cache to reduce the miss rate. However, the optimization results in an increase of cache access latency to 15 ns, whereas the miss penalty is not affected. The minimum hit rate (rounded off to two decimal places) needed after the optimization such that it should not increase the average memory access time is _____.