CS and IT Gate 2022 Questions with Answer

1 2 3 4 5

Ques 27 Gate 2022

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

The diagonal entries of A² are the degrees of the vertices of the graph.

If the graph is connected, then none of the entries of A^n-1+I_n can be zero.

If the sum of all the elements of A is at most 2(n-1), then the graph must be acyclic.

If there is at least a 1 in each of A’s rows and columns, then the graph must be connected.

(a) is the correct answer.

Ques 28 Gate 2022

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³ divided by 2

A³ divided by 3

A³ divided by 6

(d) is the correct answer.

Ques 29 Gate 2022

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

(36) is the correct answer.

Ques 30 Gate 2022

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_______

(509) is the correct answer.

Ques 31 Gate 2022

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?

T₁→T₃→T₄→T₂

T₁→T₄→T₃→T₂

T₄→T₁→T₃→T₂

T₃→T₁→T₄→T₂

(a) is the correct answer.

Ques 32 Gate 2022

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

A relation with only two attributes is always in BCNF.

If all attributes of a relation are prime attributes, then the relation is in BCNF.

Every relation has at least one non-prime attribute.

BCNF decompositions preserve functional dependencies.

(a) is the correct answer.

Ques 33 Gate 2022

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?

π_eld(π_eld,bld(own)/π_brand))

π_eld(own)-π_eld((π_eld(own)xπ_bld(brand))-π_bld,eld(own))

π_eld(π_eld,bld(own)/π_own))

π_eld((π_eld(own)xπ_bld(own))/π_bld(brand))

(a,b) is the correct answer.

Ques 34 Gate 2022

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

(153) is the correct answer.

Ques 35 Gate 2022

Consider the following recurrence:

f(1) = 1;
f(2n) = 2f(n) -1, for n≥1;
f(2n+1) = 2f(n) +1, for n≥1;

Then, which of the following statements is/are TRUE?

f(2ⁿ–1)=2ⁿ–1

f(2ⁿ)=1

f(5⋅2ⁿ)=2ⁿ⁺¹+1

f(2ⁿ+1)=2ⁿ+1

(a,b,c) is the correct answer.

Ques 36 Gate 2022

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

f(n²)=θ(f(n)²),when f(n) is a polynomial

f(n²)=o(f(n)²)

f(n²)=O(f(n)²),when f(n) is a exponential

f(n²)=Ω(f(n)²)

(a) is the correct answer.

Ques 37 Gate 2022

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?

P is 10:1 multiplexer; Q is 5:1 multiplexer; T is 2:1 multiplexer

P is 10:2¹⁰ decoder; Q is 5:2⁵ decoder; T is 2:1 encoder

P is 10:2¹⁰ decoder; Q is 5:2⁵ decoder; T is 2:1 multiplexer

P is 1:10 de-multiplexer; Q is 1:5 de-multiplexer; T is 2:1 multiplexer

Ques 38 Gate 2022

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

Which of the following statements is/are TRUE?

The chromatic number of the graph is 3.

The graph has a Hamiltonian path.

The following graph is isomorphic to the Peterson graph.

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

Ques 39 Gate 2022

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?

R1 = 1011 and R2 = 1110

R1 = 1100 and R2 = 1010

R1 = 0011 and R2 = 0100

R1 = 1001 and R2 = 1111

(b) is the correct answer.

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT Gate 2022 Questions with Answer

Question Options

Sign in to ExamPrev