GATE CSE year:2019 PYQs & Answers — Page 5

Questions 41–50 of 65. Imported answers require independent review unless marked reviewed.

Which one of the following languages over

is NOT context-free?

Your answerChoose one option.

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

Let the set of functional dependencies

hold on a relation schema

is not in BCNF. Suppose

is decomposed into two schemas

and

, where

and

. Consider the two statements given below. I. Both

and

are in BCNF II. Decomposition of

into

and

is dependency preserving and lossless Which of the above statements is/are correct?

Your answerChoose one option.

Both I and II

I only

II only

Neither I nor II

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

Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8 kB and the word size is 4 bytes. The Translation Look-aside Buffer (TLB) in the address translation path has 128 valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?

Your answerChoose one option.

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

Consider the following sets: S1. Set of all recursively enumerable languages over the alphabet

S2. Set of all syntactically valid C programs S3. Set of all languages over the alphabet

S4. Set of all non-regular languages over the alphabet

Which of the above sets are uncountable?

Your answerChoose one option.

S1 and S2

S3 and S4

S2 and S3

S1 and S4

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

Consider the first order predicate formula

Here ‘

’ denotes that ‘

divides

’, where

and

are integers. Consider the following sets: S1.

S2. Set of all positive integers S3. Set of all integers Which of the above sets satisfy

Your answerChoose one option.

S1 and S2

S1 and S3

S2 and S3

S1, S2 and S3

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 and the semantic actions to support the inherited type declaration attributes. Let

, and

be the placeholders for the non-terminals D, T, L or

in the following table:

Production rule	Semantic action
D → T L	.type = .type
T → int	T.type = int
T → float	T.type = float
L → , id	.type = .type; addType(id.entry, .type)
L → id	addType(id.entry, .type)

Which one of the following are the appropriate choices for

and

Your answerChoose one option.

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

There are

unsorted arrays:

. Assume that

is odd. Each of

contains

distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of

Your answerChoose one option.

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

Let

be any connected, weighted, undirected graph. I.

has a unique minimum spanning tree, if no two edges of

have the same weight. II.

has a unique minimum spanning tree, if, for every cut of

, there is a unique minimum-weight edge crossing the cut. Which of the above two statements is/are TRUE?

Your answerChoose one option.

I only

II only

Both I and II

Neither I nor II

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

Consider the following snapshot of a system running

concurrent processes. Process

is holding

instances of a resource R,

. Assume that all instances of R are currently in use. Further, for all

, process

can place a request for at most

additional instances of R while holding the

instances it already has. Of the

processes, there are exactly two processes

and

such that

. Which one of the following conditions guarantees that no other process apart from

and

can complete execution?

Your answerChoose one option.

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

Consider the following statements: I. The smallest element in a max-heap is always at a leaf node II. The second largest element in a max-heap is always a child of the root node III. A max-heap can be constructed from a binary search tree in

time IV. A binary search tree can be constructed from a max-heap in

time Which of the above statements are TRUE?

Your answerChoose one option.

I, II and III

I, II and IV

I, III and IV

II, III and IV

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

GATE CSE year:2019 PYQs

Question 31

Question 32

Question 33

Question 34

Question 35

Question 36

Question 37

Question 38

Question 39

Question 40