Be Paitent While your exam is being loaded

GATE (Graduate Aptitude Test in Engineering) Computer science and information Technology is an online examination conducted to get admission in M-Tech (Masters in Technology), ME (Master of Engineering ) and PhD at IITs (Indian Institutes of Technology), NITs (National Institutes of Technology), IIITs (Indian Institutes of Information Technology) and other universities in India. GATE exam is jointly conducted by IIT Bombay, IIT Delhi, IIT Guwahati, IIT Kanpur, IIT Kharagpur, IIT Madras, IIT Roorkee and Indian Institute for Science, Bangalore (IISC Bangalore). The exam is divided into two different parts General Aptitude (GA) and Candidate’s Selected Subject (Core Subjects). GATE Computer science and information Technology online mock tests help candidates in preparing for the GATE exam. By attempting GATE online mock tests candidates get familiar with the pattern of actual question paper. BrPaper provides all GATE question papers completely free. Here you can practice free online mock tests of complete exam of GATE Computer science and information Technology. We advise candidates to solve the online GATE Computer science and information Technology mock tests to get good marks in the exam. Start practicing Computer science and information TechnologyGATE 2018 Mock tests here online for free

View Solution

Participate to compete with other aspirants at an all India level.

Attempt Mock Test

Participate to compete with other aspirants at an all India level.

General Instructions

Choose Your Default Language

Please read the instructions carefully

General Instructions:

- Total duration of is 120 min.
The clock will be set at the server. The countdown timer in the top right corner of screen will display the remaining time available for you to complete the examination. When the timer reaches zero, the examination will end by itself. You will not be required to end or submit your examination.
The Questions Palette displayed on the right side of screen will show the status of each question using one of the following symbols:
1. You have not visited the question yet.
2. You have not answered the question.
3. You have answered the question.
4. You have NOT answered the question, but have marked the question for review.
5. The question(s) "Answered and Marked for Review" will be considered for evalution.
You can click on the ">" arrow which apperes to the left of question palette to collapse the question palette thereby maximizing the question window. To view the question palette again, you can click on "<" which appears on the right side of question window.
You can click on your "Profile" image on top right corner of your screen to change the language during the exam for entire question paper. On clicking of Profile image you will get a drop-down to change the question content to the desired language.
You can click on to navigate to the bottom and to navigate to top of the question are, without scrolling.

Navigating to a Question:

To answer a question, do the following:
1. Click on the question number in the Question Palette at the right of your screen to go to that numbered question directly. Note that using this option does NOT save your answer to the current question.
2. Click on Save & Next to save your answer for the current question and then go to the next question.
3. Click on Mark for Review & Next to save your answer for the current question, mark it for review, and then go to the next question.

Answering a Question:

Procedure for answering a multiple choice type question:
1. To select you answer, click on the button of one of the options.
2. To deselect your chosen answer, click on the button of the chosen option again or click on the Clear Response button
3. To change your chosen answer, click on the button of another option
4. To save your answer, you MUST click on the Save & Next button.
5. To mark the question for review, click on the Mark for Review & Next button.
To change your answer to a question that has already been answered, first select that question for answering and then follow the procedure for answering that type of question.

Navigating through sections:

Sections in this question paper are displayed on the top bar of the screen. Questions in a section can be viewed by click on the section name. The section you are currently viewing is highlighted.
After click the Save & Next button on the last question for a section, you will automatically be taken to the first question of the next section.
You can shuffle between sections and questions anything during the examination as per your convenience only during the time stipulated.
Candidate can view the corresponding section summery as part of the legend that appears in every section above the question palette.

Please note all questions will appear in your default language. This language can be changed for a particular question later on.

I have read and understood the instructions. All computer hardware allotted to me are in proper working condition. I declare that I am not in possession of / not wearing / not carrying any prohibited gadget like mobile phone, bluetooth devices etc. /any prohibited material with me into the Examination Hall.I agree that in case of not adhering to the instructions, I shall be liable to be debarred from this Test and/or to disciplinary action, which may include ban from future Tests / Examinations

Proceed

Category: GATE Computer science and information Technology 2018 General Aptitude

Question 1:

“From where are they bringing their books? ________ bringing _______ books from _____________.” The words that best fill the blanks in the above sentence are

Their, they’re, there

They’re, their, there

There, their, they’re

They’re, there, there

Category: GATE Computer science and information Technology 2018 General Aptitude

Question 2:

“A _________ investigation can sometimes yield new facts, but typically organized ones are more successful.” The word that best fills the blank in the above sentence is

meandering

timely

consistent

systematic

Category: GATE Computer science and information Technology 2018 General Aptitude

Question 3:

What would be the smallest natural number which when divided either by 20 or by 42 or by 76 leaves a remainder of 7 in each case?

3047

6047

7987

63847

Category: GATE Computer science and information Technology 2018 General Aptitude

Question 4:

What is the missing number in the following sequence?

2, 12, 60, 240, 720, 1440, _____, 0

2880

1440

720

Category: GATE Computer science and information Technology 2018 General Aptitude

Question 5:

In appreciation of the social improvements completed in a town, a wealthy philanthropist decided to gift Rs 750 to each male senior citizen in the town and Rs 1000 to each female senior citizen. Altogether, there were 300 senior citizens eligible for this gift. However, only 8/9th of the eligible men and 2/3rd of the eligible women claimed the gift. How much money (in Rupees) did the philanthropist give away in total?

1,50,000

2,00,000

1,75,000

1,51,000

Category: GATE Computer science and information Technology 2018 General Aptitude

Question 6:

I f p q r \neq a n d p^{- x} = \frac{1}{r}, q^{- y} = \frac{1}{r}, r^{- z} = \frac{1}{p},

what is the value of the product 𝑥𝑦𝑧?

A	-1	B	$\frac{1}{𝑝 𝑞 r}$
C	1	D	pqr

Category: GATE Computer science and information Technology 2018 General Aptitude

Question 7:

In a party, 60% of the invited guests are male and 40% are female. If 80% of the invited guests attended the party and if all the invited female guests attended, what would be the ratio of males to females among the attendees in the party?

2:3

1:1

3:2

2:1

Category: GATE Computer science and information Technology 2018 General Aptitude

Question 8:

In the figure below, ∠𝐷𝐸𝐶 + ∠𝐵𝐹𝐶 is equal to ____________ .

A	∠𝐵𝐶𝐷 − ∠𝐵𝐴D	B	∠𝐵𝐴𝐷 + ∠𝐵𝐶F
C	∠𝐵𝐴𝐷 + ∠𝐵𝐶D	D	∠𝐶𝐵𝐴 + ∠𝐴𝐷C

Category: GATE Computer science and information Technology 2018 General Aptitude

Question 9:

A six-sided unbiased die with four green faces and two red faces is rolled seven times. Which of the following combinations is the most likely outcome of the experiment?

Three green faces and four red faces

Four green faces and three red faces.

Five green faces and two red faces

Six green faces and one red face.

Category: GATE Computer science and information Technology 2018 General Aptitude

Question 10:

The area of a square is 𝑑. What is the area of the circle which has the diagonal of the square as its diameter?

A	𝜋𝑑	B	${πd}^{2}$
C	$\frac{1}{4} {πd}^{2}$	D	$\frac{1}{2} πd$

Category: GATE Computer science and information Technology 2018

Question 11:

Which one of the following is a closed form expression for the generating function of the sequence {

a_{n}

}, where an = 2n + 3 for all

a_{n}

= 0, 1, 2,… ?

A	$\frac{3}{{(1 - x)}^{2}}$	B	$\frac{3 x}{{(1 - x)}^{2}}$
C	$\frac{2 - x}{{(1 - x)}^{2}}$	D	$\frac{3 - x}{{(1 - x)}^{2}}$

Category: GATE Computer science and information Technology 2018

Question 12:

Consider the following C program.

# i n c l u d e < s t d i o . h > s t r u c t O u r n o d e {c h a r x, y, z;}; i n t m a i n () {s t r u c t O u r n o d e p = {' 1',' 0',' a' + 2}; s t r u c t O u r n o d e * q = & p; p r i n t f (" % c, % c ", * ((c h a r *) q + 1), * ((c h a r *) q + 2)); r e t u r n 0;}

The output of this program is:

0, c

0, a+2

\'0\', \'a+2\'

\'0\', \'c\'

Category: GATE Computer science and information Technology 2018

Question 13:

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail.

Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?

θ(1), θ(1)

θ(1), θ(n)

θ(n), θ(1)

θ(n), θ(n)

Category: GATE Computer science and information Technology 2018

Question 14:

Let ⊕ and ⊙ denote the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is NOT CORRECT?

A	$P \oplus Q = P ⊙ Q$	B	$P \oplus Q = P ⊙ Q$
C	$P \oplus Q = P ⊙ Q$	D	$(P \oplus P) \oplus Q = (P ⊙ Q) ⊙ Q$

Category: GATE Computer science and information Technology 2018

Question 15:

Consider the following processor design characteristics. I. Register-to-register arithmetic operations only II. Fixed-length instruction format III. Hardwired control unit Which of the characteristics above are used in the design of a RISC processor?

I and II only

II and III only

I and III only

I, II and III

Category: GATE Computer science and information Technology 2018

Question 16:

Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?

A	$k \geq 2^{n}$	B	$k \geq 2$
C	$k \leq 2^{n}$	D	$k \leq 2^{n}$

Category: GATE Computer science and information Technology 2018

Question 17:

The set of all recursively enumerable languages is

closed under complementation.

closed under intersection.

a subset of the set of all recursive languages.

an uncountable set.

Category: GATE Computer science and information Technology 2018

Question 18:

Which one of the following statements is FALSE?

Context-free grammar can be used to specify both lexical and syntax rules.

Type checking is done before parsing.

High-level language programs can be translated to different Intermediate Representations.

Arguments to a function can be passed using the program stack.

Category: GATE Computer science and information Technology 2018

Question 19:

The following are some events that occur after a device controller issues an interrupt while process L is under execution. (P) The processor pushes the process status of L onto the control stack. (Q)The processor finishes the execution of the current instruction. (R) The processor executes the interrupt service routine. (S) The processor pops the process status of L from the control stack. (T) The processor loads the new PC value based on the interrupt. Which one of the following is the correct order in which the events above occur?

QPTRS

PTRSQ

TRPQS

QTPRS

Category: GATE Computer science and information Technology 2018

Question 20:

Consider a process executing on an operating system that uses demand paging. The average time for memory access in the system is M units if the corresponding memory page is available in memory, and D units if the memory access causes a page fault. It has been experimentally measured that the average time taken for memory access in the process is X units. Which one of the following is the correct expression for the page fault rate experienced by the process?

(D – M) / (X – M)

(X – M) / (D – M)

(D – X) / (D – M)

(X – M) / (D – X)

Category: GATE Computer science and information Technology 2018

Question 21:

In an Entity-Relationship (ER) model, suppose 𝑅 is a many-to-one relationship from entity set E1 to entity set E2. Assume that E1 and E2 participate totally in 𝑅 and that the cardinality of E1 is greater than the cardinality of E2. Which one of the following is true about 𝑅?

Every entity in E1 is associated with exactly one entity in E2

Some entity in E1 is associated with more than one entity in E2.

Every entity in E2 is associated with exactly one entity in E1.

Every entity in E2 is associated with at most one entity in E1.

Category: GATE Computer science and information Technology 2018

Question 22:

Consider the following two tables and four queries in SQL. Book (isbn, bname), Stock (isbn, copies) Query 1: SELECT B.isbn, S.copies FROM Book B INNER JOIN Stock S ON B.isbn = S.isbn; Query 2: SELECT B.isbn, S.copies FROM Book B LEFT OUTER JOIN Stock S ON B.isbn = S.isbn; Query 3: SELECT B.isbn, S.copies FROM Book B RIGHT OUTER JOIN Stock S ON B.isbn = S.isbn; Query 4: SELECT B.isbn, S.copies FROM Book B FULL OUTER JOIN Stock S ON B.isbn = S.isbn; Which one of the queries above is certain to have an output that is a superset of the outputs of the other three queries?

Query 1

Query 2

Query 3

Query 4

Category: GATE Computer science and information Technology 2018

Question 23:

Match the following: Field Length in bits P. UDP Header’s Port Number I. 48 Q. Ethernet MAC Address II. 8 R. IPv6 Next Header III. 32 S. TCP Header’s Sequence Number IV. 16

P-III, Q-IV, R-II, S-I

P-II, Q-I, R-IV, S-III

P-IV, Q-I, R-II, S-III

P-IV, Q-I, R-III, S-II

Category: GATE Computer science and information Technology 2018

Question 24:

Consider the following statements regarding the slow start phase of the TCP congestion control algorithm. Note that cwnd stands for the TCP congestion window and MSS denotes the Maximum Segment Size. i) The cwnd increases by 2 MSS on every successful acknowledgment. (ii) The cwnd approximately doubles on every successful acknowledgment. (iii) The cwnd increases by 1 MSS every round trip time. (iv) The cwnd approximately doubles every round trip time. Which one of the following is correct?

Only (ii) and (iii) are true

Only (i) and (iii) are true

Only (iv) is true

Only (i) and (iv) are true

Category: GATE Computer science and information Technology 2018

Question 25:

Two people, P, and Q, decide to independently roll two identical dice, each with 6 faces, numbered 1 to 6. The person with the lower number wins. In case of a tie, they roll the dice repeatedly until there is no tie. Define a trial as a throw of the dice by P and Q. Assume that all 6 numbers on each dice are equiprobable and that all trials are independent. The probability (rounded to 3 decimal places) that one of them wins on the third trial is _____.

0.021 to 0.024

0.022 to 0.024

0.023 to 0.024

0.024 to 0.024

Category: GATE Computer science and information Technology 2018

Question 26:

The value of

\int_{0}^{π / 4} x \cos (x^{2}) d x

correct to three decimal places (assuming that 𝜋 = 3.14 ) is ____________________.

0.25 to 0.28

0.26 to 0.29

0.27 to 0.30

0.28 to 0.31

Category: GATE Computer science and information Technology 2018

Question 27:

Consider a matrix

A = u v^{T} w h e r e u = (\begin{matrix} 1 \\ 2 \end{matrix}), v = (\begin{matrix} 1 \\ 1 \end{matrix}) .

Note that

v^{T}

denotes the transpose of v. The largest eigenvalue of A is ___________________.

0 to 0

0 to 3

3 to 3

-3 to -3

Category: GATE Computer science and information Technology 2018

Question 28:

The chromatic number of the following graph is _______

3 to 3

-3 to -3

-3 to 3

All of these

Category: GATE Computer science and information Technology 2018

Question 29:

Let G be a finite group on 84 elements. The size of the largest possible proper subgroup of G is ___________.

39 to 39

40 to 40

41 to 41

42 to 42

Category: GATE Computer science and information Technology 2018

Question 30:

The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ____________.

4 to 4

-4 to -4

-4 to 4

None of these

Category: GATE Computer science and information Technology 2018

Question 31:

Consider the following C program:

# i n c l u d e < s t d i o . h > i n t c o u n t e r = 0; i n t c a l c (i n t a, i n t b) {i n t c; c o u n t e r + +; i f (b = = 3) r e t u r n (a * a * a); e l s e {c = c a l c (a, b / 3); r e t u r n (c * c * c);}} i n t m a i n () {c a l c (4, 81); p r i n t f (" % d ", c o u n t e r);}

The output of this program is _____.

0 to 0

0 to 4

4 to 4

-4 to -4

Category: GATE Computer science and information Technology 2018

Question 32:

Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered D flip-flops.

The number of states in the state transition diagram of this circuit that have a transition back to the same state on some value of “in” is _____________.

0 to 0

1 to 1

2 to 2

3 to 3

Category: GATE Computer science and information Technology 2018

Question 33:

A 32-bit wide main memory unit with a capacity of 1 GB is built using 256M × 4-bit DRAM chips. The number of rows of memory cells in the DRAM chip is 2 14. The time taken to perform one refresh operation is 50 nanoseconds. The refresh period is 2 milliseconds. The percentage (rounded to the closest integer) of the time available for performing the memory read/write operations in the main memory unit is ______________.

56.0 to 57.0

57.0 to 58.0

58.0 to 59.0

59.0 to 60.0

Category: GATE Computer science and information Technology 2018

Question 34:

Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of 𝐾 instances. Resource instances can be requested and released only one at a time. The largest value of 𝐾 that will always avoid deadlock is ____.

0 to 0

0 to 2

2 to 2

-2 to- 2

Category: GATE Computer science and information Technology 2018

Question 35:

Consider a long-lived TCP session with an end-to-end bandwidth of 1 Gbps (= 109 bits-per second). The session starts with a sequence number of 1234. The minimum time (in seconds, rounded to the closest integer) before this sequence number can be used again is _______.

32 to 33

34 to 35

36 to 37

38 to 39

Category: GATE Computer science and information Technology 2018

Question 36:

Consider a matrix P whose only eigenvectors are the multiples of

[\begin{matrix} 1 \\ 4 \end{matrix}]

. Consider the following statements. (I) P does not have an inverse (II) P has a repeated eigenvalue (III) P cannot be diagonalized Which one of the following options is correct?

Only I and III are necessarily true

Only II is necessarily true

Only I and II are necessarily true

Only II and III are necessarily true

Category: GATE Computer science and information Technology 2018

Question 37:

Let N be the set of natural numbers. Consider the following sets. P: Set of Rational numbers (positive and negative) Q: Set of functions from {0, 1} to N R: Set of functions from N to {0, 1} S: Set of finite subsets of N. Which of the sets above is countable?

Q and S only

P and S only

P and R only

P, Q and S only

Category: GATE Computer science and information Technology 2018

Question 38:

Consider the first-order logic sentence 𝜑 ≡ ∃𝑠∃𝑡∃𝑢∀𝑣∀𝑤∀𝑥∀𝑦 𝜓(𝑠,𝑡, 𝑢, 𝑣, 𝑤, 𝑥, 𝑦) where 𝜓(𝑠,𝑡, 𝑢, 𝑣, 𝑤, 𝑥, 𝑦) is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose 𝜑 has a model with a universe containing 7 elements. Which one of the following statements is necessarily true?

There exists at least one model of 𝜑 with universe of size less than or equal to 3.

There exists no model of 𝜑 with universe of size less than or equal to 3.

There exists no model of 𝜑 with universe of size greater than 7.

Every model of 𝜑 has a universe of size equal to 7.

Category: GATE Computer science and information Technology 2018

Question 39:

Consider the following C program:

# i n c l u d e < s t d i o . h > v o i d f u n 1 (c h a r * s 1, c h a r * s 2) {c h a r * t m p; t m p = s 1; s 1 = s 2;} v o i d f u n 2 (c h a r * * s 1, c h a r * * s 2) {c h a r * t m p; t m p = * s 1; * s 1 = * s 2; * s 2 = t m p;} i n t m a i n () {c h a r * s t r 1 = " H i ", * s t r 2 = " B y e "; f u n 1 (s t r 1, s t r 2); p r i n t f (" % s % s ", s t r 1, s t r 2); f u n 2 (& s t r 1, & s t r 2); p r i n t f (" % s % s ", s t r 1, s t r 2); r e t u r n 0;}

The output of the program above is

Hi Bye Bye Hi

Hi Bye Hi Bye

Bye Hi Hi Bye

Bye Hi Bye Hi

Category: GATE Computer science and information Technology 2018

Question 40:

Let G be a simple undirected graph. Let TD be a depth-first search tree of G. Let TB be a breadth-first search tree of G. Considers the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.) (II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |𝑖 − 𝑗| = 1. Which of the statements above must necessarily be true?

I only

II only

Both I and II

Neither I nor II

Category: GATE Computer science and information Technology 2018

Question 41:

Assume that multiplying a matrix

G_{1}

of dimension 𝑝 × 𝑞 with another matrix

G_{2}

of dimension 𝑞 × 𝑟 requires 𝑝𝑞𝑟 scalar multiplications. Computing the product of n matrices

G_{1} G_{2} G_{3} . . . . G_{n}

…Gn can be done by parenthesizing in different ways. Define

G_{1} G_{i + 1}

as an explicitly computed pair for given parenthesizations if they are directly multiplied. For example, in the matrix multiplication chain

G_{1} G_{2} G_{3} G_{4} G_{5} G_{6}

using parenthesization

(G_{1} (G_{2} G_{3})) (G_{4} (G_{5} G_{6}))

G_{2} G_{3} a n d G_{5} G_{6}

are the only explicitly computed pairs. Consider a matrix multiplication chain

F_{1}, F_{2}, F_{3}, F_{4}, F_{5}

, where matrices

F_{1}, F_{2}, F_{3}, F_{4}, a n d F_{5}

are of dimensions 2×25, 25×3, 3×16, 16×1, and 1×1000, respectively. In the parenthesization of

F_{1}, F_{2}, F_{3}, F_{4}, F_{5}

that mini

A	$F_{1}, F_{2}, a n d F_{3}, F_{4},$	B	$, F_{2}, F_{3} o n l y$
C	$, F_{3}, F_{4} o n l y$	D	$F_{1}, F_{2} a n d F_{4}, F_{5}$

Category: GATE Computer science and information Technology 2018

Question 42:

Consider the following C code. Assume that the unsigned long int type length is 64 bits.

u n s i g n e d l o n g i n t f u n (u n s i g n e d l o n g i n t n) {u n s i g n e d l o n g i n t i, j = 0, s u m = 0; f o r (i = n; i > 1; i = i / 2) j + +; f o r (; j > 1; j = j / 2) s u m + +; r e t u r n (s u m);}

The value returned when we call fun with the input

2^{40}

Category: GATE Computer science and information Technology 2018

Question 43:

Consider the unsigned 8-bit fixed-point binary number representation below,

b_{7} b_{6} b_{5} b_{4} b_{3} . b_{2} b_{1} b_{0}

where the position of the binary point is between b3 and b2. Assume b7 is the most significant bit. Some of the decimal numbers listed below cannot be represented exactly in the above representation: (i) 31.500 (ii) 0.875 (iii) 12.100 (iv) 3.001 Which one of the following statements is true?

None of (i), (ii), (iii), (iv) can be exactly represented

Only (ii) cannot be exactly represented

Only (iii) and (iv) cannot be exactly represented

Only (i) and (ii) cannot be exactly represented

Category: GATE Computer science and information Technology 2018

Question 44:

The size of the physical address space of a processor is

2^{p}

bytes. The word length is

2^{w}

bytes. The capacity of cache memory is

2^{N}

bytes. The size of each cache block is

2^{M}

words. For a 𝐾-way set-associative cache memory, the length (in number of bits) of the tag field is

A	𝑃 − 𝑁 − lo $g^{2}$ K	B	𝑃 − 𝑁 + lo $g^{2}$ K
C	𝑃 − 𝑁 − 𝑀 − 𝑊 − lo $g^{2}$ K	D	𝑃 − 𝑁 − 𝑀 − 𝑊 + lo $g^{2}$ K

Category: GATE Computer science and information Technology 2018

Question 45:

Consider the following languages: I.

\{a^{m} b^{n} c^{p} d^{q} | m + p = n + q, w h e r e m, n, p, q \geq 0\}

II.

\{a^{m} b^{n} c^{p} d^{q} | m = n a n d p = q, w h e r e m, n, p, q \geq 0\}

III.

\{a^{m} b^{n} c^{p} d^{q} | m = n = p a n d p \neq q, w h e r e m, n, p, q \geq 0\}

IV.

\{a^{m} b^{n} c^{p} d^{q} | m n = p + q, w h e r e m, n, p, q \geq 0\}

Which of the languages above are context-free?

I and IV only

I and II only

II and III only

II and IV only

Category: GATE Computer science and information Technology 2018

Question 46:

Consider the following problems. 𝐿(𝐺) denotes the language generated by a grammar 𝐺. 𝐿(𝑀) denotes the language accepted by a machine M. (I) For an unrestricted grammar 𝐺 and a string 𝑤, whether 𝑤 ∈ 𝐿(𝐺) (II) Given a Turing machine M, whether L(M) is regular (III) Given two grammars

G_{1} a n d G_{2}

g, whether

L (G_{1}) = L (G_{2})

(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language. Which one of the following statements is correct?

Only I and II are undecidable

Only III is undecidable

Only II and IV are undecidable

Only I, II and III are undecidable

Category: GATE Computer science and information Technology 2018

Question 47:

A lexical analyzer uses the following patterns to recognize three tokens

T_{1}, T_{2}, T_{3}

over the alphabet {a,b,c}.

T_{1} : a ? {(b | c)}^{*} a

T_{2} : b ? {(a | c)}^{*} b

T_{3} : a ? {(b | c)}^{*} c

Note that ‘x?’ means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix. If the string 𝑏𝑏𝑎𝑎𝑐𝑎𝑏𝑐 is processed by the analyzer, which one of the following is the sequence of tokens it outputs?

A	$T_{1}, T_{2}, T_{3}$	B	$T_{1}, T_{1}, T_{3}$
C	$T_{2}, T_{1}, T_{3}$	D	$T_{3}, T_{3}$

Category: GATE Computer science and information Technology 2018

Question 48:

Consider the following parse tree for the expression a#b$c$d#e#f, involving two binary operators $ and #.

Which one of the following is correct for the given parse tree?

$ has higher precedence and is left associative; # is right associative

# has higher precedence and is left associative; $ is right associative

$ has higher precedence and is left associative; # is left associative

# has higher precedence and is right associative; $ is left associative

Category: GATE Computer science and information Technology 2018

Question 49:

In a system, there are three types of resources: 0 E, F, and G. Four processes

P_{0}, P_{1}, P_{2}, a n d P_{3}

execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[

P_{2}

,F] is the maximum number of instances of F that

P_{2}

would require. The number of instances of the resources allocated to the various processes at any given state is given by a matrix named Allocation. Consider a state of the system with the Allocation matrix as shown below, and in which 3 instances of E and 3 instances of F are the only resources available.

From the perspective of deadlock avoidance, which one of the following is true?

The system is in safe state.

The system is not in safe state, but would be safe if one more instance of E were available

The system is not in safe state, but would be safe if one more instance of F were available

The system is not in safe state, but would be safe if one more instance of G were available

Category: GATE Computer science and information Technology 2018

Question 50:

Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is 𝑁. Three semaphores empty, full and mutex are defined with respective initial values of 0, 𝑁 and 1. Semaphore empty denotes the number of available slots in the buffer, for the consumer to read from. Semaphore full denotes the number of available slots in the buffer, for the producer to write to. The placeholder variables, denoted by P, Q, R, and S, in the code below can be assigned either empty or full. The valid semaphore operations are: wait() and signal().

Producer:	Consumer:
do{ wait(P); wait(mutex); //Add item to buffer signal(mutex); signal(Q); }while(1);	do{ wait(R); wait(mutex); //Consume item from buffer signal(mutex); signal(S); }while(1);

Which one of the following assignments to P, Q, R and S will yield the correct solution?

A	P: full, Q: full, R: empty, S: empty	C	P: empty, Q: empty, R: full, S: full
B	P: full, Q: empty, R: empty, S: full	D	P: empty, Q: full, R: full, S: empty

Category: GATE Computer science and information Technology 2018

Question 51:

Consider the relations r(A, B) and s(B, C), where s.B is a primary key and r.B is a foreign key referencing s.B. Consider the query

Q : r ⋈ (σ_{B < 5} (S))

Let LOJ denote the natural left outer-join operation. Assume that r and s contain no null values. Which one of the following queries is NOT equivalent to Q?

A	$σ_{B < 5} (r ⋈ s)$	B	$σ_{B < 5} (r L O J s)$
C	$σ_{B < 5} (r) L O J s$	D	$(r) L O J (σ_{B < 5} (s))$

Category: GATE Computer science and information Technology 2018

Question 52:

Consider the following four relational schemas. For each schema, all non-trivial functional dependencies are listed. The underlined attributes are the respective primary keys.

S c h e m a I : R e g i s t r a t i o n (r o l \ln o, c o u r s e s) F i e l d ‘ c o u r s e s ’ i s a s e t - v a l u e d a t t r i b u t e c o n t a i n i n g t h e s e t o f c o u r s e s a s t u d e n t h a s r e g i s t e r e d f o r . N o n - t r i v i a l f u n c t i o n a l d e p e n d e n c y : r o l \ln o \to c o u r s e s

S c h e m a I I : R e g i s t r a t i o n (r o l \ln o, c o u r s e i d, e m a i l) N o n - t r i v i a l f u n c t i o n a l d e p e n d e n c i e s : r o l \ln o, c o u r s e i d \to e m a i l e m a i l \to r o l \ln o

S c h e m a I I I : R e g i s t r a t i o n (r o l \ln o, c o u r s e i d, m a r k s, g r a d e) N o n - t r i v i a l f u n c t i o n a l d e p e n d e n c i e s : r o l \ln o, c o u r s e i d \to m a r k s, g r a d e m a r k s \to g r a d e

S c h e m a I V : R e g i s t r a t i o n (r o l \ln o, c o u r s e i d, c r e d i t) N o n - t r i v i a l f u n c t i o n a l d e p e n d e n c i e s : r o l \ln o, c o u r s e i d \to c r e d i t c o u r s e i d \to c r e d i t

Which one of the relational schemas above is in 3NF but not in BCNF?

Schema I

Schema II

Schema III

Schema IV

Category: GATE Computer science and information Technology 2018

Question 53:

Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, …, 100. There is an edge between vertices 𝑢 and 𝑣 if and only if the label of 𝑢 can be obtained by swapping two adjacent numbers in the label of 𝑣. Let 𝑦 denote the degree of a vertex in G, and 𝑧 denote the number of connected components in G. Then, 𝑦 + 10𝑧 = _____

107 to 107

108 to 108

109 to 109

110 to 110

Category: GATE Computer science and information Technology 2018

Question 54:

Consider Guwahati (G) and Delhi (D) whose temperatures can be classified as high (𝐻), medium (𝑀), and low (𝐿). Let 𝑃(

H_{G}

) denote the probability that Guwahati has a high temperature. Similarly, 𝑃(

M_{G}

) and 𝑃(

L_{G}

) denotes the probability of Guwahati having medium and low temperatures respectively. Similarly, we use 𝑃(

H_{D}

), 𝑃(

M_{D}

), and 𝑃(

L_{D}

) for Delhi. The following table gives the conditional probabilities for Delhi’s temperature given Guwahati’s temperature.

Consider the first row in the table above. The first entry denotes that if Guwahati has a high temperature (

(H_{G})

) then the probability of Delhi also having a high temperature (

H_{D_{}}

) is 0.40; i.e., 𝑃(

H_{D} / H_{G}

) = 0.40. Similarly, the next two entries are 𝑃(

M_{D} / H_{G}

) = 0.48 and𝑃(

L_{D} / H_{G}

) = 0.12. Similarly for the other rows. If it is known that 𝑃(

H_{G}

) = 0.2, 𝑃(

M_{G}

) = 0.5, and 𝑃(

L_{G}

) = 0.3, then the probability (correct to two decimal places) that Guwahati has high temperature given that Delhi has high temperature is _______.

0.60 to 0.62

0.62 to 0.64

0.64 to 0.66

0.66 to 0.68

Category: GATE Computer science and information Technology 2018

Question 55:

Consider the following program written in pseudo-code. Assume that x and y are integers. Count(x,y) { if (y != 1){ if (x != 1) { print("*"); Count(x/2, y); } else { y = y-1; Count(1024, y); } } } The number of times that the print statement is executed by the call Count(1024,1024) is _____.

10229 to 10229

10230 to 10230

10231 to 10231

10232 to 10232

Category: GATE Computer science and information Technology 2018

Question 56:

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ____________.

70 to 80

80 to 80

80 to 90

90 to 90

Category: GATE Computer science and information Technology 2018

Question 57:

Consider the following undirected graph G:

Choose a value for x that will maximize the number of minimum weight spanning trees (MSTs) of G. The number of MWSTs of G for this value of x is ______

0 to 0

0 to 4

4 to 4

None of these

Category: GATE Computer science and information Technology 2018

Question 58:

Consider the weights and values of the items listed below. Note that there is only one unit of each item.

Item number	Weight(in Kgs)	Value(in Rupees)
1	10	60
2	7	28
3	4	20
4	2	24

The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by 𝑉opt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by 𝑉greedy. The value of

V_{o p t} - V_{g r e e d y}

is ____________.

13 to 13

14 to 14

15 to 15

16 to 16

Category: GATE Computer science and information Technology 2018

Question 59:

Consider the minterm list form of a Boolean function 𝐹 given below.

F (P, Q, R, S) = Σ m (0, 2, 5, 7, 9, 11) = d (3, 8, 10, 12, 14)

Here, 𝑚 denotes a minterm and 𝑑 denotes a don’t care term. The number of essential prime implicants of the function 𝐹 is ______.

-3 to -3

-3 to 3

3 to 3

All of these

Category: GATE Computer science and information Technology 2018

Question 60:

The instruction pipeline of a RISC processor has the following stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO), and Writeback (WB). The IF, ID, OF and WB stages take 1 clock cycle each for every instruction. Consider a sequence of 100 instructions. In the PO stage, 40 instructions take 3 clock cycles each, 35 instructions take 2 clock cycles each, and the remaining 25 instructions take 1 clock cycle each. Assume that there are no data hazards and no control hazards. The number of clock cycles required for completion of execution of the sequence of instructions is ______.

211 to 211

213 to 213

217 to 217

219 to 219

Category: GATE Computer science and information Technology 2018

Question 61:

A processor has 16 integer registers (R0, R1, .. , R15) and 64 floating point registers (F0, F1,…, F63). It uses a 2-byte instruction format. There are four categories of instructions: Type-1, Type-2, Type-3, and Type-4. The type-1 category consists of four instructions, each with 3 integer register operands (3Rs). The type-2 category consists of eight instructions, each with 2 floating-point register operands (2Fs). The type-3 category consists of fourteen instructions, each with one integer register operand and one floating-point register operand (1R+1F). The type-4 category consists of N instructions, each with a floating-point register operand (1F). The maximum value of N is __________

12 to 12

32 to 32

52 to 52

72 to 72

Category: GATE Computer science and information Technology 2018

Question 62:

Given a language 𝐿, define

L^{i}

as follows:

L^{o} = \{ε\} L^{i} = L^{i} - 1 . L f o r a l l i > 0

The order of a language L is defined as the smallest k such that

L^{k} = L^{k + 1}

. Consider the language L1 (over alphabet 0) accepted by the following automaton.

The order of L1 is _____

0 to 0

0 to 2

-2 to 2

2 to 2

Category: GATE Computer science and information Technology 2018

Question 63:

Consider a storage disk with 4 platters (numbered as 0, 1, 2 and 3), 200 cylinders (numbered as 0, 1, … , 199), and 256 sectors per track (numbered as 0, 1, … , 255). The following 6 disk requests of the form [sector number, cylinder number, platter number] are received by the disk controller at the same time: [120, 72, 2] , [180, 134, 1] , [60, 20, 0] , [212, 86, 3] , [56, 116, 2] , [118, 16, 1] Currently, the head is positioned at sector number 100 of cylinder 80, and is moving towards higher cylinder numbers. The average power dissipation in moving the head over 100 cylinders is 20 milliwatts and for reversing the direction of the head movement once is 15 milliwatts. Power dissipation associated with rotational latency and switching of head between different platters is negligible. The total power consumption in milliwatts to satisfy all of the above disk requests using The Shortest Seek Time First disk scheduling algorithm is _______.

85 to 85

86 to 86

87 to 87

88 to 88

Category: GATE Computer science and information Technology 2018

Question 64:

Consider an IP packet with a length of 4,500 bytes that includes a 20-byte IPv4 header and a 40-byte TCP header. The packet is forwarded to an IPv4 router that supports a Maximum Transmission Unit (MTU) of 600 bytes. Assume that the length of the IP header in all the outgoing fragments of this packet is 20 bytes. Assume that the fragmentation offset value stored in the first fragment is 0. The fragmentation offset value stored in the third fragment is _______.

142 to 144

143 to 144

144 to 144

145 to 144

Category: GATE Computer science and information Technology 2018

Question 65:

Consider a simple communication system where multiple nodes are connected by a shared broadcast medium (like Ethernet or wireless). The nodes in the system use the following carrier-sense-based medium access protocol. A node that receives a packet to transmit will carrier-sense the medium for 5 units of time. If the node does not detect any other transmission in this duration, it starts transmitting its packet in the next time unit. If the node detects another transmission, it waits until this other transmission finishes, and then begins to carrier-sense for 5 time units again. Once they start to transmit, nodes do not perform any collision detection and continue transmission even if a collision occurs. All transmissions last for 20 units of time. Assume that the transmission signal travels at the speed of 10 meters per unit time in the medium. Assume that the system has two nodes P and Q, located at a distance d meters from each other. P starts transmitting a packet at time t=0 after successfully completing its carrier-sense phase. Node Q has a packet to transmit at time t=0 and begins to carrier-sense the medium. The maximum distance d (in meters, rounded to the closest integer) that allows Q to successfully avoid a collision between its proposed transmission and P’s ongoing transmission is __________.

40 to 50

50 to 50

50 to 60

60 to 60

⮜ Back Next ⮞

Not Visited	0	Not Answered
Answered	0	Marked for Review
Answered & Marked for Review (will be considered for evaluation)

Question 1:

“From where are they bringing their books? ________ bringing _______ books from _____________.” The words that best fill the blanks in the above sentence are

Correct Answer : They’re, their, there

Question 2:

“A _________ investigation can sometimes yield new facts, but typically organized ones are more successful.” The word that best fills the blank in the above sentence is

Correct Answer : meandering

Question 3:

What would be the smallest natural number which when divided either by 20 or by 42 or by 76 leaves a remainder of 7 in each case?

Correct Answer : 7987

Question 4:

What is the missing number in the following sequence?

2, 12, 60, 240, 720, 1440, _____, 0

Correct Answer : 1440

Question 5:

Correct Answer : 2,00,000

Question 6:

I f p q r \neq a n d p^{- x} = \frac{1}{r}, q^{- y} = \frac{1}{r}, r^{- z} = \frac{1}{p},

what is the value of the product 𝑥𝑦𝑧?

A	-1	B	$\frac{1}{𝑝 𝑞 r}$
C	1	D	pqr

Correct Answer : C

Question 7:

Correct Answer : 1:1

Question 8:

In the figure below, ∠𝐷𝐸𝐶 + ∠𝐵𝐹𝐶 is equal to ____________ .

A	∠𝐵𝐶𝐷 − ∠𝐵𝐴D	B	∠𝐵𝐴𝐷 + ∠𝐵𝐶F
C	∠𝐵𝐴𝐷 + ∠𝐵𝐶D	D	∠𝐶𝐵𝐴 + ∠𝐴𝐷C

Correct Answer : A

Question 9:

A six-sided unbiased die with four green faces and two red faces is rolled seven times. Which of the following combinations is the most likely outcome of the experiment?

Correct Answer : Five green faces and two red faces

Question 10:

The area of a square is 𝑑. What is the area of the circle which has the diagonal of the square as its diameter?

A	𝜋𝑑	B	${πd}^{2}$
C	$\frac{1}{4} {πd}^{2}$	D	$\frac{1}{2} πd$

Correct Answer : D

Question 11:

Which one of the following is a closed form expression for the generating function of the sequence {

a_{n}

}, where an = 2n + 3 for all

a_{n}

= 0, 1, 2,… ?

A	$\frac{3}{{(1 - x)}^{2}}$	B	$\frac{3 x}{{(1 - x)}^{2}}$
C	$\frac{2 - x}{{(1 - x)}^{2}}$	D	$\frac{3 - x}{{(1 - x)}^{2}}$

Correct Answer : D

Question 12:

Consider the following C program.

# i n c l u d e < s t d i o . h > s t r u c t O u r n o d e {c h a r x, y, z;}; i n t m a i n () {s t r u c t O u r n o d e p = {' 1',' 0',' a' + 2}; s t r u c t O u r n o d e * q = & p; p r i n t f (" % c, % c ", * ((c h a r *) q + 1), * ((c h a r *) q + 2)); r e t u r n 0;}

The output of this program is:

Correct Answer : 0, c

Question 13:

Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?

Correct Answer : θ(1), θ(n)

Question 14:

Let ⊕ and ⊙ denote the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is NOT CORRECT?

A	$P \oplus Q = P ⊙ Q$	B	$P \oplus Q = P ⊙ Q$
C	$P \oplus Q = P ⊙ Q$	D	$(P \oplus P) \oplus Q = (P ⊙ Q) ⊙ Q$

Correct Answer : D

Question 15:

Correct Answer : I, II and III

Question 16:

Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?

A	$k \geq 2^{n}$	B	$k \geq 2$
C	$k \leq 2^{n}$	D	$k \leq 2^{n}$

Correct Answer : D

Question 17:

The set of all recursively enumerable languages is

Correct Answer : closed under intersection.

Question 18:

Which one of the following statements is FALSE?

Correct Answer : Type checking is done before parsing.

Question 19:

Correct Answer : QPTRS

Question 20:

Correct Answer : (X – M) / (D – M)

Question 21:

Correct Answer : Every entity in E1 is associated with exactly one entity in E2

Question 22:

Correct Answer : Query 4

Question 23:

Match the following: Field Length in bits P. UDP Header’s Port Number I. 48 Q. Ethernet MAC Address II. 8 R. IPv6 Next Header III. 32 S. TCP Header’s Sequence Number IV. 16

Correct Answer : P-IV, Q-I, R-II, S-III

Question 24:

Correct Answer : Only (iv) is true

Question 25:

Correct Answer : 0.021 to 0.024

Question 26:

The value of

\int_{0}^{π / 4} x \cos (x^{2}) d x

correct to three decimal places (assuming that 𝜋 = 3.14 ) is ____________________.

Correct Answer : 0.27 to 0.30

Question 27:

Consider a matrix

A = u v^{T} w h e r e u = (\begin{matrix} 1 \\ 2 \end{matrix}), v = (\begin{matrix} 1 \\ 1 \end{matrix}) .

Note that

v^{T}

denotes the transpose of v. The largest eigenvalue of A is ___________________.

Correct Answer : 3 to 3

Question 28:

The chromatic number of the following graph is _______

Correct Answer : 3 to 3

Question 29:

Let G be a finite group on 84 elements. The size of the largest possible proper subgroup of G is ___________.

Correct Answer : 42 to 42

Question 30:

Correct Answer : 4 to 4

Question 31:

Consider the following C program:

# i n c l u d e < s t d i o . h > i n t c o u n t e r = 0; i n t c a l c (i n t a, i n t b) {i n t c; c o u n t e r + +; i f (b = = 3) r e t u r n (a * a * a); e l s e {c = c a l c (a, b / 3); r e t u r n (c * c * c);}} i n t m a i n () {c a l c (4, 81); p r i n t f (" % d ", c o u n t e r);}

The output of this program is _____.

Correct Answer : 4 to 4

Question 32:

Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered D flip-flops.

The number of states in the state transition diagram of this circuit that have a transition back to the same state on some value of “in” is _____________.

Correct Answer : 2 to 2

Question 33:

Correct Answer : 59.0 to 60.0

Question 34:

Correct Answer : 2 to 2

Question 35:

Correct Answer : 34 to 35

Question 36:

Consider a matrix P whose only eigenvectors are the multiples of

[\begin{matrix} 1 \\ 4 \end{matrix}]

. Consider the following statements. (I) P does not have an inverse (II) P has a repeated eigenvalue (III) P cannot be diagonalized Which one of the following options is correct?

Correct Answer : Only II and III are necessarily true

Question 37:

Correct Answer : P, Q and S only

Question 38:

Correct Answer : There exists at least one model of 𝜑 with universe of size less than or equal to 3.

Question 39:

Consider the following C program:

# i n c l u d e < s t d i o . h > v o i d f u n 1 (c h a r * s 1, c h a r * s 2) {c h a r * t m p; t m p = s 1; s 1 = s 2;} v o i d f u n 2 (c h a r * * s 1, c h a r * * s 2) {c h a r * t m p; t m p = * s 1; * s 1 = * s 2; * s 2 = t m p;} i n t m a i n () {c h a r * s t r 1 = " H i ", * s t r 2 = " B y e "; f u n 1 (s t r 1, s t r 2); p r i n t f (" % s % s ", s t r 1, s t r 2); f u n 2 (& s t r 1, & s t r 2); p r i n t f (" % s % s ", s t r 1, s t r 2); r e t u r n 0;}

The output of the program above is

Correct Answer : Hi Bye Bye Hi

Question 40:

Correct Answer : I only

Question 41:

Assume that multiplying a matrix

G_{1}

of dimension 𝑝 × 𝑞 with another matrix

G_{2}

of dimension 𝑞 × 𝑟 requires 𝑝𝑞𝑟 scalar multiplications. Computing the product of n matrices

G_{1} G_{2} G_{3} . . . . G_{n}

…Gn can be done by parenthesizing in different ways. Define

G_{1} G_{i + 1}

as an explicitly computed pair for given parenthesizations if they are directly multiplied. For example, in the matrix multiplication chain

G_{1} G_{2} G_{3} G_{4} G_{5} G_{6}

using parenthesization

(G_{1} (G_{2} G_{3})) (G_{4} (G_{5} G_{6}))

G_{2} G_{3} a n d G_{5} G_{6}

are the only explicitly computed pairs. Consider a matrix multiplication chain

F_{1}, F_{2}, F_{3}, F_{4}, F_{5}

, where matrices

F_{1}, F_{2}, F_{3}, F_{4}, a n d F_{5}

are of dimensions 2×25, 25×3, 3×16, 16×1, and 1×1000, respectively. In the parenthesization of

F_{1}, F_{2}, F_{3}, F_{4}, F_{5}

that mini

A	$F_{1}, F_{2}, a n d F_{3}, F_{4},$	B	$, F_{2}, F_{3} o n l y$
C	$, F_{3}, F_{4} o n l y$	D	$F_{1}, F_{2} a n d F_{4}, F_{5}$

Correct Answer : C

Question 42:

Consider the following C code. Assume that the unsigned long int type length is 64 bits.

u n s i g n e d l o n g i n t f u n (u n s i g n e d l o n g i n t n) {u n s i g n e d l o n g i n t i, j = 0, s u m = 0; f o r (i = n; i > 1; i = i / 2) j + +; f o r (; j > 1; j = j / 2) s u m + +; r e t u r n (s u m);}

The value returned when we call fun with the input

2^{40}

Correct Answer : 5

Question 43:

Consider the unsigned 8-bit fixed-point binary number representation below,

b_{7} b_{6} b_{5} b_{4} b_{3} . b_{2} b_{1} b_{0}

Correct Answer : Only (iii) and (iv) cannot be exactly represented

Question 44:

The size of the physical address space of a processor is

2^{p}

bytes. The word length is

2^{w}

bytes. The capacity of cache memory is

2^{N}

bytes. The size of each cache block is

2^{M}

words. For a 𝐾-way set-associative cache memory, the length (in number of bits) of the tag field is

A	𝑃 − 𝑁 − lo $g^{2}$ K	B	𝑃 − 𝑁 + lo $g^{2}$ K
C	𝑃 − 𝑁 − 𝑀 − 𝑊 − lo $g^{2}$ K	D	𝑃 − 𝑁 − 𝑀 − 𝑊 + lo $g^{2}$ K

Correct Answer : B

Question 45:

Consider the following languages: I.

\{a^{m} b^{n} c^{p} d^{q} | m + p = n + q, w h e r e m, n, p, q \geq 0\}

II.

\{a^{m} b^{n} c^{p} d^{q} | m = n a n d p = q, w h e r e m, n, p, q \geq 0\}

III.

\{a^{m} b^{n} c^{p} d^{q} | m = n = p a n d p \neq q, w h e r e m, n, p, q \geq 0\}

IV.

\{a^{m} b^{n} c^{p} d^{q} | m n = p + q, w h e r e m, n, p, q \geq 0\}

Which of the languages above are context-free?

Correct Answer : I and II only

Question 46:

G_{1} a n d G_{2}

g, whether

L (G_{1}) = L (G_{2})

(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language. Which one of the following statements is correct?

Correct Answer : Only I, II and III are undecidable

Question 47:

A lexical analyzer uses the following patterns to recognize three tokens

T_{1}, T_{2}, T_{3}

over the alphabet {a,b,c}.

T_{1} : a ? {(b | c)}^{*} a

T_{2} : b ? {(a | c)}^{*} b

T_{3} : a ? {(b | c)}^{*} c

A	$T_{1}, T_{2}, T_{3}$	B	$T_{1}, T_{1}, T_{3}$
C	$T_{2}, T_{1}, T_{3}$	D	$T_{3}, T_{3}$

Correct Answer : D

Question 48:

Consider the following parse tree for the expression a#b$c$d#e#f, involving two binary operators $ and #.

Which one of the following is correct for the given parse tree?

Correct Answer : $ has higher precedence and is left associative; # is right associative

Question 49:

In a system, there are three types of resources: 0 E, F, and G. Four processes

P_{0}, P_{1}, P_{2}, a n d P_{3}

execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[

P_{2}

,F] is the maximum number of instances of F that

P_{2}

From the perspective of deadlock avoidance, which one of the following is true?

Correct Answer : The system is in safe state.

Question 50:

Producer:	Consumer:
do{ wait(P); wait(mutex); //Add item to buffer signal(mutex); signal(Q); }while(1);	do{ wait(R); wait(mutex); //Consume item from buffer signal(mutex); signal(S); }while(1);

Which one of the following assignments to P, Q, R and S will yield the correct solution?

A	P: full, Q: full, R: empty, S: empty	C	P: empty, Q: empty, R: full, S: full
B	P: full, Q: empty, R: empty, S: full	D	P: empty, Q: full, R: full, S: empty

Correct Answer : C

Question 51:

Consider the relations r(A, B) and s(B, C), where s.B is a primary key and r.B is a foreign key referencing s.B. Consider the query

Q : r ⋈ (σ_{B < 5} (S))

Let LOJ denote the natural left outer-join operation. Assume that r and s contain no null values. Which one of the following queries is NOT equivalent to Q?

A	$σ_{B < 5} (r ⋈ s)$	B	$σ_{B < 5} (r L O J s)$
C	$σ_{B < 5} (r) L O J s$	D	$(r) L O J (σ_{B < 5} (s))$

Correct Answer : C

Question 52:

Consider the following four relational schemas. For each schema, all non-trivial functional dependencies are listed. The underlined attributes are the respective primary keys.

S c h e m a I : R e g i s t r a t i o n (r o l \ln o, c o u r s e s) F i e l d ‘ c o u r s e s ’ i s a s e t - v a l u e d a t t r i b u t e c o n t a i n i n g t h e s e t o f c o u r s e s a s t u d e n t h a s r e g i s t e r e d f o r . N o n - t r i v i a l f u n c t i o n a l d e p e n d e n c y : r o l \ln o \to c o u r s e s

S c h e m a I I : R e g i s t r a t i o n (r o l \ln o, c o u r s e i d, e m a i l) N o n - t r i v i a l f u n c t i o n a l d e p e n d e n c i e s : r o l \ln o, c o u r s e i d \to e m a i l e m a i l \to r o l \ln o

S c h e m a I I I : R e g i s t r a t i o n (r o l \ln o, c o u r s e i d, m a r k s, g r a d e) N o n - t r i v i a l f u n c t i o n a l d e p e n d e n c i e s : r o l \ln o, c o u r s e i d \to m a r k s, g r a d e m a r k s \to g r a d e

S c h e m a I V : R e g i s t r a t i o n (r o l \ln o, c o u r s e i d, c r e d i t) N o n - t r i v i a l f u n c t i o n a l d e p e n d e n c i e s : r o l \ln o, c o u r s e i d \to c r e d i t c o u r s e i d \to c r e d i t

Which one of the relational schemas above is in 3NF but not in BCNF?

Correct Answer : Schema II

Question 53:

Correct Answer : 109 to 109

Question 54:

Consider Guwahati (G) and Delhi (D) whose temperatures can be classified as high (𝐻), medium (𝑀), and low (𝐿). Let 𝑃(

H_{G}

) denote the probability that Guwahati has a high temperature. Similarly, 𝑃(

M_{G}

) and 𝑃(

L_{G}

) denotes the probability of Guwahati having medium and low temperatures respectively. Similarly, we use 𝑃(

H_{D}

), 𝑃(

M_{D}

), and 𝑃(

L_{D}

) for Delhi. The following table gives the conditional probabilities for Delhi’s temperature given Guwahati’s temperature.

Consider the first row in the table above. The first entry denotes that if Guwahati has a high temperature (

(H_{G})

) then the probability of Delhi also having a high temperature (

H_{D_{}}

) is 0.40; i.e., 𝑃(

H_{D} / H_{G}

) = 0.40. Similarly, the next two entries are 𝑃(

M_{D} / H_{G}

) = 0.48 and𝑃(

L_{D} / H_{G}

) = 0.12. Similarly for the other rows. If it is known that 𝑃(

H_{G}

) = 0.2, 𝑃(

M_{G}

) = 0.5, and 𝑃(

L_{G}

) = 0.3, then the probability (correct to two decimal places) that Guwahati has high temperature given that Delhi has high temperature is _______.

Correct Answer : 0.60 to 0.62

Question 55:

Correct Answer : 10230 to 10230

Question 56:

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ____________.

Correct Answer : 80 to 80

Question 57:

Consider the following undirected graph G:

Choose a value for x that will maximize the number of minimum weight spanning trees (MSTs) of G. The number of MWSTs of G for this value of x is ______

Correct Answer : 4 to 4

Question 58:

Consider the weights and values of the items listed below. Note that there is only one unit of each item.

Item number	Weight(in Kgs)	Value(in Rupees)
1	10	60
2	7	28
3	4	20
4	2	24

V_{o p t} - V_{g r e e d y}

is ____________.

Correct Answer : 16 to 16

Question 59:

Consider the minterm list form of a Boolean function 𝐹 given below.

F (P, Q, R, S) = Σ m (0, 2, 5, 7, 9, 11) = d (3, 8, 10, 12, 14)

Here, 𝑚 denotes a minterm and 𝑑 denotes a don’t care term. The number of essential prime implicants of the function 𝐹 is ______.

Correct Answer : 3 to 3

Question 60:

Correct Answer : 219 to 219

Question 61:

Correct Answer : 32 to 32

Question 62:

Given a language 𝐿, define

L^{i}

as follows:

L^{o} = \{ε\} L^{i} = L^{i} - 1 . L f o r a l l i > 0

The order of a language L is defined as the smallest k such that

L^{k} = L^{k + 1}

. Consider the language L1 (over alphabet 0) accepted by the following automaton.

The order of L1 is _____

Correct Answer : 2 to 2

Question 63:

Correct Answer : 85 to 85

Question 64:

Correct Answer : 144 to 144

Question 65:

Correct Answer : 50 to 50

Back
Scrore Card
Total Question		Total Attempted
Correct Answers		Incorrect Answers
Score

GATE 2018 Computer science and information Technology complete exam Practice Online with solution

View Solution

Attempt Mock Test

General Instructions

Please read the instructions carefully

General Instructions:

Navigating to a Question:

Answering a Question:

Navigating through sections:

Question 1:

Question 2:

Question 3:

Question 4:

Question 5:

Question 6:

Question 7:

Question 8:

Question 9:

Question 10:

Question 11:

Question 12:

Question 13:

Question 14:

Question 15:

Question 16:

Question 17:

Question 18:

Question 19:

Question 20:

Question 21:

Question 22:

Question 23:

Question 24:

Question 25:

Question 26:

Question 27:

Question 28:

Question 29:

Question 30:

Question 31:

Question 32:

Question 33:

Question 34:

Question 35:

Question 36:

Question 37:

Question 38:

Question 39:

Question 40:

Question 41:

Question 42:

Question 43:

Question 44:

Question 45:

Question 46:

Question 47:

Question 48:

Question 49:

Question 50:

Question 51:

Question 52:

Question 53:

Question 54:

Question 55:

Question 56:

Question 57:

Question 58:

Question 59:

Question 60:

Question 61:

Question 62:

Question 63:

Question 64:

Question 65:

Exam Summary

Are you sure you want to submit for final marking? No changes will be allowed after submission.

Thank you, Submitted Successfully.

Question 1:

Question 2:

Question 3:

Are you sure you want to submit for final marking?
No changes will be allowed after submission.