GATE CSE topic:computing PYQs & Answers — Page 51

Questions 501–510 of 975. Imported answers require independent review unless marked reviewed.

Which of the following is/are undecidable?

Your answerSelect all correct options. You can choose more than one.

Given two Turing machines

and

, decide if

Given a Turing machine

, decide if

is regular.

Given a Turing machine

, decide if

accepts all strings.

Given a Turing machine

, decide if

takes more than

steps on every string.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following languages:

Note that

is the reversal of the string

. Which of the following is/are TRUE?

Your answerSelect all correct options. You can choose more than one.

and

are regular.

and

are context-free.

is regular and

is context-free.

and

are context-free but not regular.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following languages:

Which of the following statements is/are FALSE?

Your answerSelect all correct options. You can choose more than one.

is not context-free but

and

are deterministic context-free.

Neither

nor

is context-free.

and

all are context-free.

Neither

nor its complement is context-free.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider a simple undirected weighted graph

, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of

is/are TRUE?

Your answerSelect all correct options. You can choose more than one.

The edge with the second smallest weight is always part of any minimum spanning tree of

One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of

Suppose

be such that

and

. Consider the edge with the minimum weight such that one of its vertices is in

and the other in

. Such an edge will always be part of any minimum spanning tree of

can have multiple minimum spanning trees.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

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

Diagram for Computer Science and Information Technology question 50

Which of the following statements is/are TRUE?

Your answerSelect all correct options. You can choose more than one.

The chromatic number of the graph is 3.

The graph has a Hamiltonian path.

The following graph is isomorphic to the Peterson graph.

Diagram for Computer Science and Information Technology question 50 (figure 2)

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

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following recurrence:

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

Your answerSelect all correct options. You can choose more than one.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Which of the properties hold for the adjacency matrix

of a simple undirected unweighted graph having

vertices?

Your answerSelect all correct options. You can choose more than one.

The diagonal entries of

are the degrees of the vertices of the graph.

If the graph is connected, then none of the entries of

can be zero.

If the sum of all the elements of

is at most

, then the graph must be acyclic.

If there is at least a 1 in each of

's rows and columns, then the graph must be connected.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Which of the following is/are the eigenvector(s) for the matrix given below?

Your answerSelect all correct options. You can choose more than one.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider a system with 2 KB direct mapped data cache with a block size of 64 bytes. The system has a physical address space of 64 KB and a word length of 16 bits. During the execution of a program, four data words P, Q, R, and S are accessed in that order 10 times (i.e., PQRS PQRS...). 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 0x2A2, 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?

Your answerSelect all correct options. You can choose more than one.

Every access to S is a hit.

Once P is brought to the cache it is never evicted.

At the end of the execution only R and S reside in the cache.

Every access to R evicts Q from the cache.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider routing table of an organization’s router shown below:

Subnet Number	Subnet Mask	Next Hop
12.20.164.0	255.255.252.0	R1
12.20.170.0	255.255.254.0	R2
12.20.168.0	255.255.254.0	Interface 0
12.20.166.0	255.255.254.0	Interface 1
default		R3

Which of the following prefixes in CIDR notation can be collectively used to correctly aggregate all of the subnets in the route table?

Your answerSelect all correct options. You can choose more than one.

12.20.164.0/20

12.20.164.0/22

12.20.164.0/21

12.20.168.0/22

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

GATE CSE topic:computing PYQs

Question 46

Question 47

Question 48

Question 49

Question 50

Question 51

Question 52

Question 53

Question 54

Question 55