GATE CSE topic:computing PYQs & Answers — Page 93

Questions 921–930 of 975. Imported answers require independent review unless marked reviewed.

Consider the following C function.

int fun(int n) { int i, j; for(i = 1; i<= n; i++) { for(j = 1; j < n; j += i) { printf("%d %d", i, j); } } }

Your answerChoose one option.

Θ(n√n)

Θ(n²)

Θ(n log n)

Θ(n² log n)

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

Let

and

be finite alphabets and let

be a symbol outside both

and

. Let

be a total function from

. We say

is computable if there exists a Turing machine

which given an input

, always halts with

on its tape. Let

denote the language

. Which of the following statements is true:

Your answerChoose one option.

is computable if and only if

is recursive.

is computable if and only if

is recursively enumerable.

is computable then

is recursive, but not conversely.

is computable then

is recursively enumerable, but not conversely.

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

Let δ denote the transition function and δ̂ denote the extended transition function of the ε-NFA whose transition table is given below:

δ	ε	a	b
→ q₀	{q₂}	{q₁}	{q₀}
q₁	{q₂}	{q₂}	{q₃}
q₂	{q₀}	∅	∅
q₃	∅	∅	{q₂}

Then δ̂(q₂, aba) is

Your answerChoose one option.

∅

{q₀, q₁, q₃}

{q₀, q₁, q₂}

{q₀, q₂, q₃}

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

Recall that Belady’s anomaly is that the page-fault rate may increase as the number of allocated frames increases. Now, consider the following statements:

S1: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady’s anomaly S2: LRU page replacement algorithm suffers from Belady’s anomaly

Which of the following is CORRECT?

Your answerChoose one option.

S1 is true, S2 is true

S1 is true, S2 is false

S1 is false, S2 is true

S1 is false, S2 is false

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:

L₁ = {aᵖ | p is a prime number} L₂ = {aⁿbᵐc²ᵐ | n ≥ 0, m ≥ 0} L₃ = {aⁿbⁿc²ⁿ | n ≥ 0} L₄ = {aⁿbⁿ | n ≥ 1}

Which of the following are CORRECT?

I. L₁ is context-free but not regular. II. L₂ is not context-free. III. L₃ is not context-free but recursive. IV. L₄ is deterministic context-free.

Your answerChoose one option.

I, II and IV only

II and III only

I and IV only

III and IV only

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

Consider a database that has the relation schemas EMP(EmpId, EmpName, DeptId), and DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus.

(I)

(II)

(III)

Which of the above queries are safe?

Your answerChoose one option.

(I) and (II) only

(I) and (III) only

(II) and (III) only

(I), (II) and (III)

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

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable?

I. Given a regular expression R and a string w, is w ∈ L(R)? II. Given a context-free grammar G, is L(G) = ∅? III. Given a context-free grammar G, is L(G) = Σ* for some alphabet Σ? IV. Given a Turing machine M and a string w, is w ∈ L(M)?

Your answerChoose one option.

I and IV only

II and III only

II, III and IV only

III and IV only

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

In a database system, unique timestamps are assigned to each transaction using Lamport’s logical clock. Let

and

be the timestamps of transactions

and

respectively. Besides,

holds a lock on the resource R, and

has requested a conflicting lock on the same resource R. The following algorithm is used to prevent deadlocks in the database system assuming that a killed transaction is restarted with the same timestamp.

then

is killed

else

waits.

Assume any transaction that is not killed terminates eventually. Which of the following is TRUE about the database system that uses the above algorithm to prevent deadlocks?

Your answerChoose one option.

The database system is both deadlock-free and starvation-free.

The database system is deadlock-free, but not starvation-free.

The database system is starvation-free, but not deadlock-free.

The database system is neither deadlock-free nor starvation-free.

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

The next state table of a 2-bit saturating up-counter is given below.

Q₁	Q₀	Q₁⁺	Q₀⁺
0	0	0	1
0	1	1	0
1	0	1	1
1	1	1	1

The counter is built as a synchronous sequential circuit using T flip-flops. The expressions for T₁ and T₀ are

Your answerChoose one option.

T₁ = Q₁Q₀, T₀ = Q̅₁Q̅₀

T₁ = Q̅₁Q₀, T₀ = Q̅₁ + Q̅₀

T₁ = Q₁ + Q₀, T₀ = Q̅₁ + Q̅₀

T₁ = Q̅₁Q₀, T₀ = Q₁ + Q₀

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

Consider the following grammar:

stmt

if expr then expr else expr; stmt

expr

term relop term

term

number

[0-9]

where relop is a relational operator (e.g.,<, >, …), ò refers to the empty statement, and if, then, else are terminals.

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 38

Question 39

Question 39

Question 40

Question 40

Question 41

Question 41

Question 42

Question 42

Question 43