CS and IT GATE 2022 Questions with Answer

Ques 27 Data Structure

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.

Ques 28 Data Structure

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

Ques 29 Data Structure

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 Data Structure

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 DBMS

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₂

Ques 32 DBMS

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.

Ques 33 DBMS

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

Ques 34 DBMS

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 Design Algorithm Analysis

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

Ques 36 Design Algorithm Analysis

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

Ques 37 Digital Logic Design

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 Digital Logic Design

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 Digital Logic Design

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

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT GATE 2022 Questions with Answer