Official Paper

GATE CS 2017 Official Paper: Shift 2 (Previous Year Paper)

65 questions · 180 minutes · with answers · free

Attempt as Timed Mock Test

General Aptitude (10 questions)

Choose the option with words that are not synonyms.

((a))
aversion, dislike
((b))
luminous, radiant
((c))
plunder, loot
((d))
yielding, resistant

Show Answer

Answer: ((d))

yielding, resistant

The correct answer is option 4)

Aversion - a strong dislike or disinclination towards something**;** DISLIKE - to feel distaste for or hostility towards something.
Luminous - giving off light; bright or shining; Radiant - sending out light; shining or glowing brightly.
Plunder - steal (goods), typically using force and in a time of disorder; Loot - steal (goods) in a war, riot, etc.
Yielding - giving a product or generating a financial return of a specified amount; Resistant - offering resistance to something or someone.

we can clearly see in points 1,2 & 3 that words given in pairs are somehow similar in meaning, but in point 4 words Yielding and Resistant are completely different in meaning. So the words of this pair are not synonyms.

Saturn is______to be seen on a clear night with the naked eye.

((a))
enough bright
((b))
bright enough
((c))
as enough bright
((d))
bright as enough

Show Answer

Answer: ((b))

bright enough

The correct answer is option 2)

In option 1) enough has been before bright (an adjective) which is grammatically incorrect, for "enough" always follows an adjective and precedes a noun. E.g. enough money, intelligent enough, etc.
For the same reason, option 2) is grammatically correct which is the correct answer.
'As' is used with 'enough' when we have some level of expectation involved (जितना हो सके). For e.g. "Yet this high level of commitment to preventative health care is still not seen as enough."

There are five buildings called V, W, X, Y and Z in a row (not necessarily in that order). V is to the West of W. Z is to the east of X and the West of V. W is to the West of Y. Which is the building in the middle?

((a))
V
((b))
W
((c))
X
((d))
Y

Show Answer

Answer: ((a))

i) V is to the west of W

∴ V ← w

ii) Z is to the east of Y

∴ X → Z

iii) Z is to the west of V

(∵ from 1, 2) ∴ X → Z ← V ← w

iv) W is to the west of Y

∴ X – Z – V – W – Y

∴ V is in the middle.

A test has twenty questions worth 100 marks in total. There are two types of questions. Multiple choice questions are worth 3 marks each and essay questions are worth 11 marks each. How many multiple choice questions does the exam have?

((a))
12
((b))
15
((c))
18
((d))
19

Show Answer

Answer: ((b))

Solution: Let the no. of multiple choice question be ‘x’

Let the no. of essay question be ‘y’

∴ According to given into

x + y = 20 ---(1)

Now given that

Total paper is of 100 marks
MCQ question are of 3 marks each
Essay questions are of 11 marks each

∴ 3x + 11y = 100 ---(2)

Solving (1) and (2)

x + y = 20 -- (1)

3x + 11y = 100 ---(2)

Multiply eqn (1) by 3

∴ 3x + 3y = 60 ---(3)

Now subtract eqn (3) from eqn (2)

$\frac{{\begin{array}{{20}{c}} {\therefore ;;3x + 11y = 100}\ { - 3x + 3y = 60} \end{array}}}{{\begin{array}{{20}{c}} {;;;;;;;;;8y = 40}\ {;;;;;;;;y = 5} \end{array}}}$

Put y = 5 in eqn (1)

∴ x = 15

∴ No. of multiple choice questions are 15.

There are 3 red socks, 4 green socks and 3 blue socks. You choose 2 socks. The probability that they are of the same colour is

((a))
1/5
((b))
7/30
((c))
1/4
((d))
4/15

Show Answer

Answer: ((d))

4/15

Given:

Red socks → 3

Green socks → 4

Blue socks → 3

To find that if we choose 2 socks then the probability that they both are of same column.

∴ Probability of same 2 coloured socks

$= \left( {\frac{{3{{\rm{C}}_2}}}{{10{{\rm{C}}_2}}}} \right) + \left( {\frac{{3{{\rm{C}}_2}}}{{10{{\rm{C}}_2}}}} \right) + \left( {\frac{{4{{\rm{C}}_2}}}{{10{{\rm{C}}_2}}}} \right)$

$= \frac{3}{{45}} + \frac{3}{{45}} + \frac{6}{{45}}$

$= \frac{{12}}{{45}}$

$= \frac{4}{{15}}$

‘’We lived in a culture that denied any merit to literary works, considering them important only when they were handmaidens to something seemingly more urgent – namely ideology. This was a country where all gestures, even the most private, were interpreted in political terms.’’

The author’s belief that ideology is not as important as literature is revealed by the word:

((a))
‘culture’
((b))
‘seemingly’
((c))
‘urgent’
((d))
‘political’

Show Answer

Answer: ((b))

‘seemingly’

Explanation:

Through these lines, the author means to convey that he lived in a culture that did not consider literature important unless it was supporting something that was seen to be more important or urgent, and names 'ideology' as that thing.

By stating that ideology was 'seemingly' more important, he implies that, in his opinion, it wasn't more important than literature but was seen to be.

Therefore, the correct answer is 'seemingly'.

There are three boxes. One contains apples another contains oranges and the last one contains both apples and oranges. All three are known to be incorrectly labelled. If you are permitted to open just one box and them pull out and inspect only one fruit, which box would you open to determine the contents of all three boxes?

((a))
The box labelled ‘Apples’
((b))
The box labelled ‘Apples and Oranges’
((c))
The box labelled ‘Oranges’
((d))
Cannot be determined

Show Answer

Answer: ((b))

The box labelled ‘Apples and Oranges’

So according to the question there are 3 boxes and all are incorrectly labelled.

→ We have to choose only one box and inspect one fruit & determine the contents of all three boxes.

→ Here two things are important to notice that labels are incorrect and we can only inspect one fruit from any of the one box.

→ So we will take into consideration the box which is labelled as apples and oranges

As it is incorrectly labelled so there will be only apples or only oranges so lets assume that we got apples.

so the box on which oranges label is attached will have apples and oranges both in it because in the question it is mentioned that they are incorrectly labelled.

if (apples and orange) will be in the box labelled as apples then only one fruit orange and one label orange is remaining and they cannot be on same box.

Hence orange will be in the box labelled as apple.

Hence when we will choose the box labelled as apple and oranges we will be able to determine the content of all 3 boxes.

Similarly if in the beginning if we assume oranges we wiil be able to determine the contents of every box too but the arrangement will be in the following way

X is a 30 digit number starting with the digit 4 followed by the digit 7. Then he number X³ will have

((a))
90 digits
((b))
91 digits
((c))
92 digits
((d))
93 digits

Show Answer

Answer: ((a))

90 digits

X is a 30-digit number

The first digit is 4, and the rests are 7

i.e. X = 47777 _______ up to 29 terms (digit 7 only)

X = 4.777 × 10²⁹

Taking, Log₁₀ both sides

${\rm{lo}}{{\rm{g}}_{10}}X = {\log _{10}}\left( {4.777{\rm{;}} \times {\rm{;}}{{10}^{29}}} \right)$

$= {\log _{10}}4.777; + \log _{10}^;{10^{29}}$

= 0.679 + 29

= 29.679

Also,

${\log _{10}}\left( {{X^3}} \right) = 3{\log _{10}}X$

${\log _{10}}\left( {{X^3}} \right) = 3 \times 29.679$

${\log _{10}}\left( {{X^3}} \right) = 89.037$

Taking anti ${\rm{lo}}{{\rm{g}}_{10}}$ both sides,

${X^3} = {10^{89.037}}$

${X^3} = {10^{89}} \times {10^{0.037}}$

${X^3} = 1.0889 \times {10^{89}}$

Thus, there are 90 digits in X³.

The number of roots of e^x + 0.5x² – 2 = 0 in the range [-5, 5] is

((a))
0
((b))
1
((c))
2
((d))
3

Show Answer

Answer: ((c))

Given, ${e^x} + 0.5{x^2} - 2$

e^x + 0.5x² – 2 = 0 ---(i)

We have to find the number of roots in the range [ -5, 5]

Differentiating both sides,

$;\frac{d}{{dr}}\left( {{e^x} + 0.5{x^2} - 2} \right) = 0$

${e^x} + 0.5 \times 2x = 0$

${e^x} = - x$ ---(ii)

Any dependent variable differentiation w.r.t. the independent variable gives the maximum value of dependent variable at one of the roots when we put the differentiation equals to zero.

As, the value gives a root of the dependent variable,

So from equation (ii), using this as a root of equation (i)

we get,

$- x + 0.5{x^2} - 2 = 0$ [putting eqn (ii) in eqn (i)]

$\frac{{{x^2}}}{2} - x - 2 = 0$

${x^2} - 2x - 4 = 0$

$x = \frac{{2 \pm \sqrt {4 - 4 \times 1 \times \left( { - 4} \right)} }}{2}$

$= 1 \pm \sqrt 5$

$ie.;x = 1 + \sqrt 5 ;& ;1 - \sqrt 5 $

So, there are two root of the equation.

An air pressure contour line joins locations in a region having the same atmospheric pressure. The following is an air pressure contour plot of a geographical region. Contour lines are shown at 0.05 bar intervals in this plot

If the possibility of a thunderstorm is given by how fast air pressure rises or drops over a region, which of the following regions is most likely to have a thunderstorm?

((a))
P
((b))
Q
((c))
R
((d))
S

Show Answer

Answer: ((c))

Possibility of thunderstorm = ?

They defined possibility of thunderstorm is given by low fast air pressure rises or drops over region.

Now if you will closely notice the diagram given in the question then you will notice that only in the region ‘R’ there are 4 contour lines passing i.e. variation of pressure or pressure rise/drop in a that region is very fast and rapid Hence the answer is R.

Computer Science and Information Technology (55 questions)

The representation of the value of a 16-bit unsigned integer X in hexadecimal number system is BCA9. The representation of the value of X in octal number system is

((a))
571244
((b))
736251
((c))
571247
((d))
136251

Show Answer

Answer: ((d))

136251

STEPS:

First, convert the given hexadecimal number into binary equivalent.
Convert that binary number into an octal number.

Binary equivalent of BCA9: 1011110010101001

Representation of this binary equivalent to octal number system is: 136251

Tips and Tricks:

For hexadecimal number, pair of 4 binary bits are taken from right to left and for octal number, pair of 3 binary bits is taken starting from least significant bits.

Match the following:

(P)	static char var;	(i)	A sequence of memory locations to store addresses
(Q)	m = malloc(10); m = NULL;	(ii)	A variable located in the data section of memory
(R)	char *ptr[10];	(iii)	Request to allocate a CPU register to store data
(S)	register int var1;	(iv)	A lost memory which cannot be freed

((a))
P → (ii), Q → (iv), R→ (i), S → (iii)
((b))
P → (ii), Q → (i), R → (iv), S → (iii)
((c))
P → (ii), Q → (iv), R → (iii), S → (i)
((d))
P → (iii), Q → (iv), R → (i), S → (ii)

Show Answer

Answer: ((a))

P → (ii), Q → (iv), R→ (i), S → (iii)

A static variable is the one that remains in the memory while the program is running. So, static char var; => matches with => A variable located in the data section of memory
m = malloc(10); m = NULL, As here memory is first allocated to m, then m becomes NULL, it means the program has no longer a pointer to memory. This is the problem of lost memory which cannot be freed.
char *ptr[10]; It is an array of 10 pointers. It means a sequence of memory locations to store addresses.
Register int var1; Here, variable var1 is declared with register keyword which means the variable can be put into registers. A request to allocate a CPU to store data.

Match the algorithms with their time complexities:

	Algorithm		Time complexity
(P)	Towers of Hanoi with n disks	(i)	Θ (n²)
(Q)	Binary search given n sorted numbers	(ii)	Θ (n log n)
(R)	Heap sort given n numbers at the worst case	(iii)	Θ (2ⁿ⁾
(S)	Addition of two n × n matrices	(iv)	Θ (log n)

((a))
P – (iii), Q – (iv), R – (i), S – (ii)
((b))
P – (iv), Q – (iii), R – (i), S – (ii)
((c))
P – (iii), Q – (iv), R – (ii), S – (i)
((d))
P – (iv), Q – (iii), R – (ii), S – (i)

Show Answer

Answer: ((c))

P – (iii), Q – (iv), R – (ii), S – (i)

Recurrence relation for tower of Hanoi problem is T (n) = 2 T (n - 1) + 1, So, time complexity for tower of Hanoi problem is Θ (2 n).
Binary search algorithm searches a sorted array by repeatedly dividing the search interval in half. If value of search key is less than the item in middle, search in the lower half otherwise, search in upper half. In this way, time complexity of binary search in sorted array becomes Θ (log n).
Heap sort algorithm worst case time complexity is Θ (n log n).
Addition of two n × n matrices takes Θ (n 2) time to execute. As there are two for loop used while addition of two n × n matrices.

Let L₁, L₂ be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?

I. L₁ ∪ L₂ is context-free

II. L̅₁ is context-free

III. L₁ – R is context-free

IV. L₁ ∩ L₂ is context-free

((a))
I, II and IV only
((b))
I and III only
((c))
II and IV only
((d))
I only

Show Answer

Answer: ((b))

I and III only

Concept: Property of context-free languages is:

Context-free languages are closed under union and difference but not closed under complementation and intersection.

Explanation:

Option 1) L1 ∪ L2 is context-free

As context-free languages are closed under union. So it is correct.

Option 2). L̅1 is context-free

L1 is a context-free language. According to the property, its complement can’t be context-free.

Option 3) L1 – R is context-free

As the difference of a context-free language with regular is context-free. So, it is correct.

Option 4) L1 ∩ L2 is context-free

It violated the context-free language property. The intersection of two CFL’s is not CFL. So, it is incorrect.

Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it:

(P)	Syntax tree	(i)	Code generator
(Q)	Character steam	(ii)	Syntax analyzer
(R)	Intermediate representation	(iii)	Semantic analyser
(S)	Token stream	(iv)	Lexical analyzer

((a))
P → (ii), Q → (iii), R → (iv), S → (i)
((b))
P → (ii), Q → (i), R → (iii), S → (iv)
((c))
P → (iii), Q → (iv), R → (i), S → (ii)
((d))
P → (i), Q → (iv), R → (ii), S → (iii)

Show Answer

Answer: ((c))

P → (iii), Q → (iv), R → (i), S → (ii)

Phases of the compiler are:

Diagram

Phases of Compiler	Input	Output
Lexical Analyzer	Character stream	Token stream
Syntax Analyzer	Token stream	Syntax tree
Semantic Analyzer	Syntax tree	Syntax tree
Intermediate Code Generator	Syntax tree	Intermediate representation
Machine-Independent Code Optimizer	Intermediate representation	Intermediate representation
Code Generator	Intermediate representation	Target-machine code
Machine-Dependent Code Optimizer	Target-machine code	Target-machine code

Which of the following statements about parser is/are CORRECT?

I. Canonical LR is more powerful than SLR.

II. SLR is more powerful than LALR.

III. SLR is more powerful than Canonical LR.

((a))
I only
((b))
II only
((c))
III only
((d))
II and III only

Show Answer

Answer: ((a))

I only

Concept: LR parsers in terms of their power:

CLR > LALR > SLR > LR (0)

Explanation:

I. Canonical LR is more powerful than SLR. TRUE

II. SLR is more powerful than LALR. FALSE

III. SLR is more powerful than Canonical LR. FALSE

Which of the following is/are shared by all the threads in a process?

I. Program counter

II. Stack

III. Address space

IV. Registers

((a))
I and II only
((b))
III only
((c))
IV only
((d))
III and IV only

Show Answer

Answer: ((b))

III only

Multiple threads of the same process share other resources of process except register, stack and stack pointer. In particular, a process is generally considered to consist of a set of threads sharing an address space, heap, static data, code segments and file descriptors.

In a file allocation system, which of the following allocation scheme(s) can be used if no external fragmentation is allowed?

I. Contiguous

II. Linked

III. Indexed

((a))
I and III only
((b))
II only
((c))
III only
((d))
II and III only

Show Answer

Answer: ((d))

II and III only

Concept:

Internal fragmentation occurs when a process is allocated more memory than required, few space is left unused.

External fragmentation occurs when blocks of memory are there, but they are non-contiguous and can’t fill the upcoming request for memory.

Explanation:

Linked and indexed allocation are free from external fragmentation but contiguous allocation scheme suffered from external fragmentation problem.

Consider the following statements about the routing protocols. Routing Information Protocol (RIP) and Open Shortest Path First (OSPE) in an IPv4 network.

I. RIP uses distance vector routing

II. RIP packets are sent using UDP

III. OSPF packets are sent using TCP

IV. OSPF operation is based on link-state routing

Which of the statements above are CORRECT?

((a))
I and IV only
((b))
I, II and III only
((c))
I, II and IV only
((d))
II, III and IV only

Show Answer

Answer: ((c))

I, II and IV only

Option 1) RIP uses distance vector routing

RIP is a dynamic routing protocol which uses hop count as a routing metric between source and destination. It uses distance vector routing So, it is correct.

Option 2) RIP packets are sent using UDP

RIP uses the UDP protocol for transmission of data. So, it is correct.

Option 3) OSPF packets are sent using TCP

OSPF is a link state routing protocol which uses multicast address to find the best path between source and destination. As, TCP does not support multicasting. So, OSPF packets are not sent using TCP. So, it is incorrect.

Option 4) OSPF operation is based on link-state routing. It is correct.

If $f\left( x \right) = R\sin \left( {\frac{{\pi x}}{2}} \right) + S,;f'\left( {\frac{1}{2}} \right) = \sqrt 2 ;and;\mathop \smallint \nolimits_0^1 f\left( x \right)dx = \frac{{2R}}{\pi }$, then the constants R and S are, respectively.

((a))
$\frac{2}{\pi };and\frac{{16}}{\pi }$
((b))
$\frac{2}{\pi };and;0$
((c))
$\frac{4}{\pi };and;0$
((d))
$\frac{4}{\pi };and\frac{{16}}{\pi }$

Show Answer

Answer: ((c))

$\frac{4}{\pi };and;0$

Given, $f\left( x \right) = R\sin \left( {\frac{{\pi x}}{2}} \right) + S,;f'\left( {\frac{1}{2}} \right) = \sqrt 2 ;and;\mathop \smallint \nolimits_0^1 f\left( x \right)dx = \frac{{2R}}{\pi }$

$f'\left( x \right) = R;{\rm{cos}}\left( {\frac{{\pi x}}{2}} \right) \times \frac{\pi }{2}$

$f'\left( {\frac{1}{2}} \right) = R\cos \left( {\frac{{\pi \left( {\frac{1}{2}} \right)}}{2}} \right) \times \frac{\pi }{2} = ;\sqrt {2;} ;{f'}\left( {\frac{1}{2}} \right) = \sqrt 2$

$f'\left( {\frac{1}{2}} \right) = R \times \frac{1}{{\surd 2}} \times \frac{\pi }{2} = ;\sqrt 2$

$R = ;\frac{{\sqrt 2 ; \times ;\sqrt 2 ; \times 2}}{\pi } = ;\frac{4}{\pi }$

Now, f(x) becomes,

$f\left( x \right) = ;\frac{4}{{\pi ;}} \times \sin \left( {\frac{{\pi \times x}}{2}} \right) + S$

$\mathop \smallint \nolimits_0^1 f\left( x \right)dx = ;\mathop \smallint \nolimits_0^1 \left( {\frac{4}{\pi }; \times \sin \left( {\frac{{\pi \times x}}{2}} \right) + S} \right)dx = ;\frac{{2 \times R}}{\pi } = ;\frac{8}{{{\pi ^2}}}$

$\frac{4}{\pi }\mathop \smallint \nolimits_0^1 \sin \left( {\frac{{\pi x}}{2}} \right)dx + ;\mathop \smallint \nolimits_0^1 Sdx = ;\frac{8}{{{\pi ^2}}}$

${4}{\pi }\left[ { - \cos \left( {\frac{{\pi x}}{2}} \right) \times \frac{2}{\pi }} \right]_0^1 + S\left[ x \right]_0^1 = ;\frac{8}{{{\pi ^2}}}$

$\frac{8}{{{\pi ^2}}}\left[ { - 0 + 1} \right] + S = ;\frac{8}{{{\pi ^{2;}}}};$

$\therefore ;S = 0$

Let p, q, r denotes the statements ‘’It is raining’’, ‘’It is cold’’, and ‘’It is pleasant’’, respectively. Then the statement ‘’It is not raining, and it is pleasant, and it is not pleasant only if it is raining and it is cold’’ it represented by

((a))
(¬ p ∧ r) ∧ (¬ r → (p ∧ q))
((b))
(¬ p ∧ r) ∧ ((p ∧ q) → ¬ r)
((c))
(¬ p ∧ r) ∨ ((p ∧ q) → ¬ r)
((d))
(¬ p ∧ r) ∨ (r → (p ∧ q))

Show Answer

Answer: ((a))

(¬ p ∧ r) ∧ (¬ r → (p ∧ q))

Concept:

And operator - ʌ

Only if meaning: q only if means that p is a necessary condition for q , denoted as : q → p

Explanation:

p = it is raining

q = it is cold

r = it is pleasant

¬ p = it is not raining

Now, “’ It is not raining, and it is pleasant” = ¬ p ʌ r

“it is not pleasant only if it is raining and it is cold’’ denoted as = ¬ r → (p ʌ q)

So, the overall expression for ‘’It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold’’ will be:

( ¬ p ʌ r ) ʌ ( ¬ r → (p ʌ q ) )

Option 1) is true.

Given the following binary number in 32-bit (single precision) IEEE-754 format:

00111110011011010000000000000000

The decimal value closest to this floating-point number is

((a))
1.45 × 10¹
((b))
1.45 × 10^-1
((c))
2.27 × 10^-1
((d))
2.27 × 10¹

Show Answer

Answer: ((c))

2.27 × 10^-1

Concept:

32-bit floating-point representation of a binary number in IEEE- 754 is

Sign (1 bit)	Exponent (8 bit)	Mantissa bit (23 bits)

Calculation:

Given binary number is

00111110011011010000000000000000

Here, sign bit is 0. So, number is positive.

0	01111100	11011010000000000000000

Exponent bits = E = 01111100 = 124 (in decimal)

Mantissa bits M = 11011010000000000000000

In IEEE-754 format, 32-bit (single precision)

(-1)^s × 1.M × 2^{E – 127}

= (-1)⁰ × 1.1101101 × 2^{124 – 127}

= 1.1101101 × 2^-3

= (1 + 2^-1 + 2^-2 + 2^-4 + 2^-5 + 2^-7) × 2-3

= 0.231 = 2.31 × 10^-1 ≈ 2.27 × 10^-1

A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the near node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time?

I. Next pointer of front node points to the rear node.

II. Next pointer of rear node points to the front node.

((a))
I only
((b))
II only
((c))
Both I and II
((d))
Neither I and II

Show Answer

Answer: ((b))

II only

Solution:

Concept:

In a queue, elements are deleted from front and inserted from rear end. Whenever a new element is inserted, rear is incremented.

Explanation:

Diagram

So, in case of a circular queue to make an insert and delete operation in O (1) time, the rear pointer will point to the next node i.e. front node. After storing this pointer rear will point to the newly created node.

For enqueue: struct node *ptr

ptr -> next = rear -> next;

rear -> next = ptr

rear = ptr

For dequeue: ptr(front node)

rear -> next = front ->next

ptr = front

front =rear -> next

free(ptr)

Important Points:

For above enqueue and dequeue,

Assume linked list contains more than one element

Structure:

struct node

{

int data;

struct node *next;

}

Consider the following function implemented in C:

void printxy(int x, int y) {

int *ptr;

x = 0;

ptr = &x;

y = *ptr;

*ptr = 1;

printf ("%d, %d", x, y) ;

}

The output of invoking printxy(1, 1) is

((a))
0, 0
((b))
0, 1
((c))
1, 0
((d))
1, 1

Show Answer

Answer: ((c))

1, 0

When printxy(1, 1) is called, this part of the program will execute.

Code Explanation:

void printxy (int x, int y) { // Here x and y becomes 1

int *ptr;

x = 0 ; // it will make x = 0

ptr = &x; // here, ptr contains the address of x,

y = *ptr; // value of y = 0

*ptr = 1; // value of x = 1

printf (‘’%d, %d’’, x, y); // it will print x as 1 and y as 0

}

Explanation

y = *ptr;

y is pointing to ptr but as * is there, value of ptr will be accesses which is same as value of x

because ptr is pointing to x location.

*ptr = 1;

Sine ptr is pointing at location x, x value chances to 1.

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

((a))
MNOPQR
((b))
NQMPOR
((c))
QMNROP
((d))
POQNMR

Show Answer

Answer: ((d))

POQNMR

Concept:

Breadth first search involves search through a tree one level at a time. Traverse through one entire level of child node first, before moving to traverse through the grandchildren nodes.

Explanation:

MNOPQR

In this, traversal starts from S but O is visited first before child node N and Q of M. So, incorrect.

NQMPOR

It is also incorrect, P is traversed before O.

QMNROP

Incorrect, because O must be traversed before R.

So, option 4) is correct.

Identify the language generated by the following grammar, where S is the start variable.

S → XY

X → aX | a

Y → aYb | ϵ

((a))
{a^mbⁿ | m ≥ n, n > 0}
((b))
{a^mbⁿ | m ≥ n, n ≥ 0}
((c))
{a^mbⁿ | m > n, n ≥ 0}
((d))
{a^mbⁿ | m > n, n > 0}

Show Answer

Answer: ((c))

{a^mbⁿ | m > n, n ≥ 0}

Grammar:

S → XY

X → aX | a

Y → aYb | ϵ

Explanation:

X generates at least one a. Generates a string of type {a, aa, aaa, aaaa……}

a^mbⁿ, if n = 0 and m = 0 ∴ string = ϵ which cannot be generated from the given grammar and hence option 2 is incorrect.

Y generates an equal number of a and b { ϵ, ab, aabb, ……} with a comes before b.

Since at least one a is generated by X and an equal number of a’s and b’s generated by Y ∴ m> n and hence option 1 is incorrect

The smallest length string generated by Y is ϵ. In a^mbⁿ, n ≥ 0 and hence option 4 is incorrect.

{ a, aab, aaabb,………….} which is equivalent to :

L = {a^mbⁿ | m > n, n ≥ 0}

An ER model of a database consists of entity types A and B. These are connected by a relationship R which does not have its own attribute. Under which one of the following conditions, can the relational table for R be merged with that of A?

((a))
Relationship R is one-to-many and the participation of A in R is total.
((b))
Relationship is one-to-many and the participation of A in R is partial.
((c))
Relationship R is many-to-one and the participation of A in R is total.
((d))
Relationship R is many-to-one and the participation of A in R is partial.

Show Answer

Answer: ((c))

Relationship R is many-to-one and the participation of A in R is total.

Concept:

Total participation: It specifies that each entity in the entity set must compulsorily participate in at least one relationship instance in that relationship set.

Partial participation: It specifies that each entity in the entity set may or may not participate in the relationship instance in that relationship set.

Explanation:

In one to many or many to one relation, the relation between two entities is merged on the many side with total participation. As, it is given that relationship R doesn’t have its own attributes. So, it must be combined with entity A. So, the relation must be many to one and there should be total participation of A in R.

Consider socket API on a Linux machine that supports connected UDP sockets. A connected UDP socket is a UDP socket on which connect function has already been called. Which of the following statements is/are CORRECT?

I. A connected UDP socket can be used to communicate with multiple peers simultaneously.

II. A process can successfully call connect function again for an already connected UDP socket.

((a))
I only
((b))
II only
((c))
Both I and II
((d))
Neither I nor II

Show Answer

Answer: ((b))

II only

A connected UDP socket calls connect function again to specify a new IP address and port. Also to disconnect the socket.

I. A connected UDP socket can be used to communicate with multiple peers simultaneously.

Servers that use UDP are normally iterative in nature means that the server processes one request at a time. A server gets the request received in a datagram from UDP, processes the request and gives the response to UDP to send to the client. So, this statement is incorrect.

II. A process can successfully call connect function again for an already connected UDP socket.

As, it is already known that a connect function can be called again to setup new peers and to disconnect the already connected sockets. So, this statement is correct.

Consider the following tables T1 and T2.

P	Q
2	2
3	8
7	3
5	8
6	9
8	5
9	8

R	S
2	2
8	3
3	2
9	7
5	7
7	2

In table T1, P is the primary key and Q is the foreign key referencing R in table T2 with on-delete cascade and on-update cascade. In table T2, R is the primary key and S is the foreign key referencing P in table T1 with on-delete set NULL and on-update cascade. In order to delete record (3, 8) from table T1, the number of additional records that need to be deleted from table T1 is ______.

The maximum number of IPv4 router addresses that can be listed in the record route (RR) option field of an IPv4 header is _____.

Consider the set X = {a, b, c, d, e} under the partial ordering R = {(a, a), (a, b), (a, c), (a, d), (a, e), (b, b), (b, c), (b, e), (c, c), (c, e), (d, d), (d, e), (e, e)}.

The Hasse diagram of the partial order (X, R) is shown below.

The minimum number of ordered pairs that need to be added to R to make (X, R) a lattice is _____.

Let $P = \left[ {\begin{array}{{20}{c}} 1&1&{ - 1}\ 2&{ - 3}&4\ 3&{ - 2}&3 \end{array}} \right];and;Q = \left[ {\begin{array}{{20}{c}} { - 1}&{ - 2}&{ - 1}\ 6&{12}&6\ 5&{10}&5 \end{array}} \right]$ be two matrices.

Then the rank of P + Q is ______.

G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is ______.

Consider a quadratic equation x² – 13x + 36 = 0 with coefficients in a base b. The solutions of this equation in the same base b are x = 5 and x = 6. Then b = _______.

The minimum possible number of states of a deterministic finite automation that accepts the regular language L = {w₁aw₂ | w₁, w₂ ϵ {a, b}*, |w₁| = 2, |w₂| ≥ 3} is ________.

P and Q are considering to apply for a job. The probability that P applies for the job is $\frac{1}{4}$ , the probability that P applies for the job given that Q applies for the job is $\frac{1}{2}$ , and the probability that Q applies for the job given that P applies for the job is $\frac{1}{3}$ . Then the probability that P does not apply for the job given that Q does not apply for the job is

((a))
$\frac{4}{5}$
((b))
$\frac{5}{6}$
((c))
$\frac{7}{8}$
((d))
$\frac{{11}}{{12}}$

Show Answer

Answer: ((a))

$\frac{4}{5}$

Data:

$p\left( P \right) = \frac{1}{4}$

$P\left( {\frac{P}{Q}} \right) = ;\frac{1}{2}$ , $P\left( {\frac{Q}{P}} \right) = ;\frac{1}{3}$

Formula

$P\left( {\frac{A}{B}} \right) = ;\frac{{P\left( {A \cap B} \right)}}{{P\left( B \right)}}$

Calculation:

$P\left( {\frac{Q}{P}} \right) = ;\frac{{P;\left( {P \cap Q} \right)}}{{P\left( P \right)}},;;$

$\frac{1}{3} = ;\frac{{P\left( {P \cap Q} \right)}}{{\frac{1}{4}}}$ ,

$P\left( {P \cap Q} \right) = ;\frac{1}{{12}}$

Also, $P\left( {\frac{P}{Q}} \right) = \frac{{P;\left( {P \cap Q} \right)}}{{P\left( Q \right)}},;;$

$\frac{1}{2} = \frac{{\frac{1}{{12}}}}{{P\left( Q \right)}}$ ,

$P\left( Q \right) = \frac{1}{6}$

Required probability, $P\left( {\frac{{P'}}{{Q'}}} \right) = \frac{{P\left( {P' \cap Q'} \right)}}{{P\left( {Q'} \right)}}$

$= \frac{{P{{\left( {P \cup Q} \right)}'}}}{{1 - P\left( Q \right)}}; = \frac{{1 - P\left( {P \cup Q} \right)}}{{1 - P\left( Q \right)}}$

$= \frac{{1 - \left( {P\left( P \right) + P\left( Q \right) - P;\left( {P \cap Q} \right)} \right)}}{{1 - P\left( Q \right)}};$

$= \frac{{1 - \left( {\frac{1}{4} + \frac{1}{6} - \frac{1}{{12}}} \right)}}{{1 - \frac{1}{6}}}$

$= \frac{{\frac{8}{{12}}}}{{\frac{5}{6}}} = \frac{4}{5}$

If w, x, y, z Boolean variables, then which one of the following is INCORRECT?

((a))
wx + w(x + y) + x(x + y) = x + wy
((b))
$\overline {w\bar x\left( {y + \bar z} \right)} + \bar wx = \bar w + x + ;\bar yz$
((c))
(wx̅ (y + xz̅ ) + w̅ x̅)y = xy̅
((d))
(w + y) (wxy + wyz) = wxy + wyz

Show Answer

Answer: ((c))

(wx̅ (y + xz̅ ) + w̅ x̅)y = xy̅

Formula:

A + A = A; A.A = A ; A + A.B = A;

1 + A = 1; 1.A = A

Explanation:

Consider all the options

Option 1:

wx + w(x + y) + x(x + y) = x + wy

wx + wx + wy + xx + xy = x + wy

wx + wy + x + xy = x + wy

x + wy = x + wy

Option 2:

$\overline {w\bar x\left( {y + \bar z} \right)} + \bar wx = \bar w + x + ;\bar yz$

$\bar w + \overline {\bar x} + \bar y;;\overline {\bar z} + ;\bar wx = ;\bar w + x + \bar yz$

$\bar w + x + \bar y;;z + ;\bar wx = ;\bar w + x + \bar yz$

$\bar w + x + \bar y;;z; = ;\bar w + x + \bar yz$

Option 3:

(wx̅ (y + xz̅ ) + w̅ x̅)y = xy̅

$\left( {w;\bar x;y + w\bar z + \bar w;\overline {x;} ;} \right)y = x\bar y;$

$\left( {w;\bar x;y + w\bar z;y + \bar w;\overline {x;} ;;y} \right) = x\bar y$

$\left( {;\bar x;y + w\bar z;y} \right) = \bar x;\bar y$

$\therefore \left( {;\bar x;y + w\bar z;y} \right) \ne \bar x;\bar y$

Option 4:

(w + y) (wxy + wyz) = wxy + wyz

wxy + wyz + wxy + wyz = wxy + wyz

wxy + wyz = wxy + wy

Given f(w, x, y, z) = ∑_m (0, 1, 2, 3, 7, 8, 10) + ∑_d (5, 6, 11, 15), where d represents the don’t-care condition in Karnaugh maps. Which of the following is a minimum product-of-sums (POS) form of f(w, x, y, z)?

((a))
f = (w̅ + z̅ )(x̅ + z)
((b))
f = (w̅ + z)(x + z)
((c))
f = (w + z)(x̅ + z)
((d))
f = (w + z̅ )(x̅ + z)

Show Answer

Answer: ((a))

f = (w̅ + z̅ )(x̅ + z)

Concept:

In SOP (sum of product) form, a min term is represented by 1.

In POS (product of sum) form, a max term is represented by 0.

Sum of product: (SOP)

f(w, x, y, z) = ∑_m (0, 1, 2, 3, 7, 8, 10) + ∑_d (5, 6, 11, 15)

Product of sum: (P0S)

f(w, x, y, z) = Π (4, 9, 12, 13, 14) + ∑_d (5, 6, 11, 15),

Diagram:

K-map from this expression is:

f(x, y, w, z) = (w’ + z’) (x’ + z)

In a two-level cache system, the access times of L₁ and L₂ caches are 1 and 8 clock cycles, respectively. The miss penalty from the L₂ cache to main memory is 18 clock cycles. The miss rate of L₁ cache is twice that of L₂. The average memory access time (AMAT) of this cache system is 2 cycle. The miss rates of L₁ and L₂ respectively are:

((a))
0.111 and 0.056
((b))
0.056 and 0.111
((c))
0.0892 and 0.1784
((d))
0.1784 and 0.0892

Show Answer

Answer: ((a))

0.111 and 0.056

Data:

Access time of L₁ = T₁ = 1 clock cycle

Access time of L₂ = T₂ = 8 clock cycle

L₂ miss penalty = T₃ = 18 clock cycle

L₁ miss rate = 2 × L₂ miss rate

Average memory access time = AMAT = 2 clock cycle

Let, L₂miss rate = a

∴ L₁ miss rate = 2a

Formula:

AMAT = (T₁ + 2a × T₂ + 2a × a × T₃)

Calculation:

2 = 1 + 2a × 8 + 2a × a × 18

2 = 1 + 16a + 36a²

36a² + 16a -1 = 0

36a² + 18a – 2a + 1 = 0

18a (2a + 1) – 1(2a + 1) = 0

$a = \frac{{ - 1}}{2},\frac{1}{{18}}$

So, miss rate of L₂ = 0.056 and Miss rate of L₁ = 0.111

Consider the recurrence function $T\left( n \right) = \left{ {\begin{array}{*{20}{c}} {2T\left( {\sqrt n } \right) + 1,;;;n > 2}\ {2,;;;0 < n \le 2} \end{array}} \right.$ Then T(n) in terms of Θ notation is

((a))
Θ (log log n)
((b))
Θ (log n)
((c))
Θ (√n)
((d))
Θ (n)

Show Answer

Answer: ((b))

Θ (log n)

$T\left( n \right) = 2;T\left( {\sqrt n } \right) + 1$

Put n= 2^m, m = log₂n

$T\left( {{2^m}} \right) = 2T\left( {{2^{\frac{m}{2}}}} \right) + 1$

$Put;T\left( {{2^m}} \right) = S\left( m \right)$

$S\left( m \right) = 2;S;\left( {\frac{m}{2}} \right) + 1$

Now, calculate ${n^{log_b^a}}$

${m^{log_b^a}} = m$

S (m) = m + 1

S(m) = m

Put the value of m

Therefore, T(n) in terms of Θ notation is Θ (logn).

For any discrete random variable X, with probability mass function P(X = j) = p_j, p_j ≥ 0, j ∈ {0,….,N}, and $\mathop \sum \limits_{j = 0}^N {p_j} = 1$, define the polynomial function ${g_x}\left( z \right) = ;\mathop \sum \limits_{j = 0}^N {p_j}{z^j}$. For a certain discrete random variable Y, there exists a scalar β ∈ [0, 1] such that g_γ (z) = (1 - β + β z)^N. The expectation of Y is

((a))
Nβ (1 – β)
((b))
Nβ
((c))
N (1 - β)
((d))
Not expressible in terms of N and β alone

Show Answer

Answer: ((b))

Nβ

Derivative of g_x (z) at z = 1 gives the expectation E (X).

When g_y(z) is expanded, it results in a binomial distribution form and mean of a binomial distribution is in the form of N *p.

${g_x}\left( z \right) = ;\mathop \sum \limits_{j = 0}^N {p_j}{z^j}$

${g'x}\left( z \right) = ;\mathop \sum \nolimits{j = 1}^N j{p_j}{z^{j - 1}} = ;\mathop \sum \nolimits_{j = 1}^N j{p_j} = E\left( X \right)$

Similarly, take the derivate of g_y(z) at z= 1.

$E\left( Y \right) = ;{\left. {{{g'}y}\left( z \right)} \right|{z = 1}} = ;{\left. {\left( {{{\left( {1 - ;\beta + \beta z} \right)}^N}} \right)'} \right|{z = 1}} = N\beta {\left. {{{\left( {1 - \beta + \beta z} \right)}^{N - 1}}} \right|{z = 1}} = N\beta {\left( {1 - \beta + \beta z} \right)^{N - 1}}$

$E\left( Y \right) = N\beta$

Consider the following expression grammar G:

E → E – T | T

T → T + F | F

F → (E) | id

Which of the following grammars is not left recursive, but is equivalent to G?

((a))
E → E – T | T

T → T + F | F

F → (E) | id
((b))
E → TE’

E’ → -TE’ | ϵ

T → T + F | F

F → (E) | id
((c))
E → TX

X → -TX | ϵ

T → FY

Y → +FY | ϵ

F → (E) | id
((d))
E → TX | (TX)

X → -TX | +TX | ϵ

T → id

Show Answer

Answer: ((c))

E → TX

X → -TX | ϵ

T → FY

Y → +FY | ϵ

F → (E) | id

Concept:

A production of grammar is said to have left recursion if its leftmost variable of its RHS is same as variable of LHS.

Consider grammar of type A → Aa | b

After removing left recursion, it becomes A → bA’, A’ → aA’| ϵ

Explanation:

Given grammar is:

E → E – T | T

T → T + F | F

F → (E) | id

After removing left recursion, it becomes:

E → TE’

E’ → -T E’ | ϵ

T → FT’

T’ → + FT’ | ϵ

F → (E) | id

Therefore option 3 is correct.

A system shares 9 tape drives. The current allocation and maximum requirement of tape drives for three processes are shown below:

Process	Current Allocation	Maximum Requirement
P1	3	7
P2	1	6
P3	3	5

Which of the following best describes current state of the system?

((a))
Safe, Deadlocked
((b))
Safe, Not Deadlocked
((c))
Note Safe, Deadlocked
((d))
Not Safe, Not Deadlocked

Show Answer

Answer: ((b))

Safe, Not Deadlocked

Resource allocation table:

Process	Current Allocation	Maximum Requirement	Need (Maximum-current)
P1	3	7	4
P2	1	6	5
P3	3	5	2

Available = 9 – ∑ (current allocation to process) = 9 – 7 = 2

Now, 2 resource will satisfy the need of P3.

After this available = 2 + 3 = 5

5 resource can satisfy need of P2 or P1

CASE 1:

If P2 is executed before P1,

Available = 5 + 1 =6

6 resource can satisfy the need of P1 easily.

CASE 2:

If P1 is executed before P2

Available = 5 + 3 = 8

8 resource can satisfy the need of P1 easily.

Safe sequence will be P3, P1, P2 and P3, P2, P1

System is safe and there is no deadlock in the system.

Consider a binary code that consists of only four valid code wards as given below:

00000, 01011, 10101, 11110

Let the minimum Hamming distance of the code be p and the maximum number of erroneous bits that can be corrected by the code be q. Then the values of p and q are

((a))
p = 3 and q = 1
((b))
p = 3 and q = 2
((c))
p = 4 and q = 1
((d))
p = 4 and q = 2

Show Answer

Answer: ((a))

p = 3 and q = 1

Concept:

Hamming distance is a metric for comparing two binary strings. While comparing two binary strings of equal length, hamming distance is the number of bit positions in which the two bits are different.

Explanation:

Given code words are: 00000, 01011, 10101, 11110

Code 1 = 00000

Code 2 = 01011

Code 3 = 10101

Code 4 = 11110

Hamming distance can also be calculated by taking XOR of two binary strings.

Here hamming distance between code1 and code2 is 3. Similarly, between code 1 and code 3, hamming distance is 3.

But between code 2 and code 3 hamming distance is 4. But we have to take minimum hamming distance which is 3.

So, p = 3

Now, maximum error bits that can be correct using hamming distance = $floor\left( {\frac{{d - 1}}{2}} \right) = \frac{{3 - 1}}{2} = 1$

So, q = 1

Consider two hosts X and Y, connected by a single direct link of rate 10⁶ bits/sec. The distance between the two hosts is 10,000 km and the propagation speed along the link is 2 × 10⁸ m/sec. Host X sends a file of 50,000 bytes as one large message to host Y continuously. Let the transmission and propagation delays be p milliseconds and q milliseconds, respectively. Then the values of p and q are

((a))
p = 50 and q = 100
((b))
p = 50 and q = 400
((c))
p = 100 and q = 50
((d))
p = 400 and q = 50

Show Answer

Answer: ((d))

p = 400 and q = 50

Data:

Transmission rate = bandwidth = 10⁶ bits/sec

Distance = 10,000 km

Propagation speed = 2 × 10⁸ m/sec

Frame size = 50,000 bytes

Formula:

Transmission time = $\rm \frac{{frame;length}}{{bandwidth}}$

Propagation time = $\rm \frac{{Distance}}{{propagation;speed}}$

Calculation:

$\rm Transmission;time = p = \frac{{50000\ \times\ 8}}{{{{10}^6}}} = \frac{{4\ \times ;{{10}^5}}}{{{{10}^6}}} = \frac{{4 ;\times; 100}}{{10 ;\times; 100}} = 400;msec$

$\rm Propagation;time = q = ;\frac{{10000; \times; 1000}}{{2; \times ;{{10}^8}}} = \frac{1}{{20}} = 50;msec$

∴ p = 400 and q = 500

The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:

((a))
2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
((b))
2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12
((c))
7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12
((d))
7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12

Show Answer

Answer: ((b))

2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12

Concept:

Inorder traversal of a binary search tree is the ascending order of the given values.

In pre- order first node is the root.

Pre-order Traversal = root, left, right

In-order = left, root, right

Post-order = left, right, root

Explanation:

Pre-order traversal is 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20.

In-order traversal is 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20

Now, anything which is in the left of root in in-order traversal will come to the left of root and other comes to the right of root.

Binary search tree using pre-order and in-order traversal is:

Diagram:

So, post order traversal of this binary search tree is 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12

Consider the C program fragment below which is meant to divide x by y using repeated subtraction. The variables x, y, q and r are all unsigned int.

While (r >= y) {

r = r – y;

q = q + 1;

}

Which of the following conditions on the variables x, y, q and r before the execution of the fragment will ensure that the loop terminates in a state satisfying the condition x == (y*q + r)?

((a))
(q == r) && (r == 0)
((b))
(x > 0) && (r == x) && (y > 0)
((c))
(q == 0) && (r == x) && (y > 0)
((d))
(q == 0) && (y > 0)

Show Answer

Answer: ((c))

(q == 0) && (r == x) && (y > 0)

Given condition is x == (y*q + r)

Here, x= result, y= multiplicand, q= quotient, r= remainder

As, the number is divided using repeated subtraction, So quotient must be 0 in that case.

When in above condition q= 0

Then, x = r.

It matches with option 3.

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

}

Time complexity of fun in terms of Θ notation is

((a))
Θ (n√n)
((b))
Θ (n²)
((c))
Θ (nlog n)
((d))
Θ (n²log n)

Show Answer

Answer: ((c))

Θ (nlog n)

We have to check how many times inner loop will be executed here.

For i=1,

j will run 1 + 2 + 3 + …………. (n times)

For i=2

j will run for 1,3,5, 7, 9, 11,………..(n/2 times)

For i=3

j will run for 1,4,7,10, 13…………… (n/3 times)

So, in this way,

$T\left( n \right) = n + \frac{n}{2} + \frac{n}{3} + \frac{n}{4} + \frac{n}{5} + \frac{n}{6} \ldots + \frac{n}{n}$

$= n\left( {1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} \ldots + \frac{1}{n}} \right);$

So, Time complexity of given program = Θ (n log n)

Let δ denote the transition function and $\hat \delta$ denote the extended transition function of the ϵ-NFA whose transition table is given below:

δ	ϵ	a	b
→ q0	{q2}	{q1}	{q0}
q1	{q2}	{q2}	{q3}
q2	{q0}	ϕ	ϕ
*q3	ϕ	ϕ	{q2}

Then $\hat \delta ;\left( {{q_2},;aba} \right)$ is

((a))
ϕ
((b))
{q₀, q₁, q₃}
((c))
{q₀, q₁, q₂}
((d))
{q₀, q₂, q₃}

Show Answer

Answer: ((c))

{q₀, q₁, q₂}

Concept:

Extended transition function means when we start from a state and follow a sequence of input.

In case of ϵ-NFA, epsilon moves are also considered.

Diagram: NFA for the given NFA table is:

Here, $\hat \delta ;\left( {{q_2},;aba} \right)$

Explanation:

When input a is applied on q₂ it will move to q₀, q₁ as there is null transition so it will also get to q₂.

Similarly, states after input b => {q₀, q₂, q₃}

States after input a = {q₀, q₁, q₂}

So, final answer is {q₀, q₁, q₂}

Consider the following languages

L₁ = {a^p | p is a prime number}

L₂ = {aⁿb^mc^2m | 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

((a))
I, II and IV only
((b))
II and III only
((c))
I and IV only
((d))
III and IV only

Show Answer

Answer: ((d))

III and IV only

Consider the options one by one:

Option 1:

L₁ = {a^p | p is a prime number}

Prime numbers do not have fixed pattern. So, it is not possible to solve it using pushdown

automaton. So, L₁ is not context free language.

Option 2:

L₂ = {aⁿb^mc^2m | n ≥ 0, m ≥ 0}

It can be solved easily using single stack. Comparison is done between b and c. We can make a pushdown automaton for this. So, L₂ is context free language.

Option 3:

L₃ = {aⁿbⁿc²ⁿ | n ≥ 0}

First comparison is between a and b, then between b and c, therefore two stacks are required.

So, it is context sensitive language. L₃ is recursive language.

Option 4:

L₄ = { aⁿbⁿ | n ≥ 1}

First push a into a stack then pop a for each b from the stack. The given language is accepted by

Deterministic Pushdown Automaton. Therefore, L₄ is deterministic context-free.

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

((a))
I and IV only
((b))
II and III only
((c))
II, III and IV only
((d))
III and IV only

Show Answer

Answer: ((d))

III and IV only

Decidable properties of Languages:

For decidable: D

For un-decidable: U

For grammar: G

	Membership Problem w ∈ L(R)	Emptiness L(G) = ϕ	Universality L(G) = ∑*	Equality	L(G)= Regular	L(G) = Finite
Regular Language	D	D	D	D	D	D
DCFL	D	D	D	D	D	D
CFL	D	D	UD	UD	UD	D
CSL	D	UD	UD	UD	UD	UD
Recursive language	D	UD	UD	UD	UD	UD
Recursive enumerable language	UD	UD	UD	UD	UD	UD

From the above table:

Membership property of regular grammar is decidable.

Emptiness problem of context free grammar is decidable.

Universality property for context free grammar is undecidable.

Membership problem of Turing machine is undecidable.

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

Q₁	Q₀	${Q_{1}^{+}}$	${Q_{0}^{+}}$
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

((a))
T₁ = Q₁Q₀, T₀ = Q̅₁Q̅₀
((b))
T₁ = Q̅₁Q₀, T₀ = Q̅₁ + Q̅₀
((c))
T₁ = Q₁ + Q₀, T₀ = Q̅₁ + Q̅₀
((d))
T₁ = Q̅₁Q₀, T₀ = Q₁ + Q₀

Show Answer

Answer: ((b))

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

Concept:

Output of T flip flop will change when T = 1 and remain same when T = 0

Excitation table for T flip flop

Q₁	Q₀	$Q_{1}^{+}$	$Q_{0}^{+}$	T₁	T₀
0	0	0	1	0	1
0	1	1	0	1	1
1	0	1	1	0	1
1	1	1	1	0	0

From this table,

T1 = Q̅1Q0

T0 = Q̅1 + Q̅0

Important Point:

T₀ → NAND Gate (function)

Tips:

If unable to write the function then construct the K- Map of two variable with Q1 and Q0 as input

Consider the following snippet of a C program. Assume that swap(&x, &y) exchanges the contents of x and y.

int main () {

int array [] = {3, 5, 1, 4, 6, 2};

int done = 0;

int i;

while (done == 0) {

done = 1;

for (i=0; i<=4; i++) {

if (array[i] < array [i+1]) {

swap (&array[i], &array[i+1]);

done = 0;

}

for (i=5; i>=1; i--) {

If (array[i] > array[i-1]) {

Swap (&array[i], &array[i-1]);

}

printf(‘’%d’’, array[3]);

}

The output of the program is ______.

Two transactions T₁ and T₂ are given as

T₁ : r₁ (X)w₁ (X)r₁(Y)w₁ (Y)

T₂ : r₂ (Y)w₂ (Y)r₂ (Z)w₂ (Z)

Where r_i(V) denotes a read operation by transaction T_i on a variable V and w_i(V) denotes a write operation by transaction T_i on a variable V. The total number of conflict serializable schedules that can be formed by T₁ and T₂ is _________.

The read access times and the hit ratios for different caches in a memory hierarchy are as given below:

Cache	Read access time (in nanoseconds)	Hit ratio
I-cache	2	0.8
D-cache	2	0.9
L2-cache	8	0.9

The read access time of main memory is 90 nanoseconds. Assume that the caches use the referred-word-first read policy and the write back policy. Assume that all the caches are direct mapped caches. Assume that the dirty bit is always 0 for all the blocks in the caches. In execution of a program, 60% of memory reads are for instruction fetch and 40% are for memory operand fetch. The average read access time in nanoseconds (up to 2 decimal places) is ______.

Consider the following database table named top_scorer.

Top_scorer

player	country	Goals
Klose	Germany	16
Ronaldo	Brazil	15
G miller	Germany	14
Fontaine	France	13
Pele	Brazil	12
Klinsmann	Germany	11
Kocsis	Hungary	11
Batistuta	Argentina	10
Cubillas	Peru	10
Lato	Poland	10
Lineker	England	10
T Miller	Germany	10
Rahn	Germany	10

Consider the following SQL query:

SELECT ta.player FROM top scorer AS ta

WHERE ta.goals >All (SELECT tb.goals

FROM top_scorer AS tb

WHERE tb.country = ‘Spain’)

AND ta.goals >Any (SELECT tc.goals

FROM top_scorer AS tc

WHERE tc.country = ‘Germany’)

The number of tuples returned by the above SQL query is ______.

If the ordinary generating function of a sequence $\left{ {{a_n}} \right}_{n = 0}^\infty$ is $\frac{{1 + z}}{{{{\left( {1 - z} \right)}^3}}}$ , then a₃ – a₀ is equal to ______.

If a random variable X has a Poisson distribution with mean 5, then the expectation E[(X + 2)²] equals ______.

In a B+ tree, if the search-key value is 8 bytes long the block size is 512 bytes and the block pointer size is 2 bytes, then the maximum order of the B+ tree is ______.

A message is made up entirely of characters from the set X = {P, Q, R, S, T}. The table of probabilities for each of the characters is shown below:

Character	Probability
P	0.22
Q	0.34
R	0.17
S	0.19
T	0.08
Total	1.00

If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is_____.

Consider the set of processes with arrival time (in milliseconds). CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes have I/O burst time

Process	Arrival Time	Burst Time	Priority
P₁	0	11	2
P₂	5	28	0
P₃	12	2	3
P₄	2	10	1
P₅	9	16	4

The average waiting time (in milliseconds) of all the processes using pre-emptive priority scheduling algorithm is ______.

If the characteristic polynomial of a 3 × 3 matrix M over R (the set of real numbers) is λ³ – 4λ² + aλ + 30, a ∈ R, and one eigenvalue of M is 2, then the largest among the absolute value of the eigenvalues of M is __________.

Consider a machine with a byte addressable main memory of 2³² bytes divided into blocks of size 32 bytes. Assume that a direct mapped cache having 512 cache lines is used with this machine. The size of the tag field in bits is ______.

Consider the following C Program

#include<stdio.h>

int main ( ) {

int m = 10;

int n, n1;

n = ++m;

n1 = m++;

n--;

--n1;

n -= n1;

printf(‘’%d’’, n) ;

return 0;

}

The output of the program is ______.

Consider the following C Program.

#include<stdio.h>

#include<string.h>

int main ( ) {

char* c = ‘’GATECSIT2017’’;

char* p = c;

printf (‘’%d’’, (int)strlen (c+2[p] – 6[p]-1) ) ;

return 0;

}

The output of the program is ______.

Attempt this paper under real exam conditions

Timed interface, section switching, instant scoring, and question-by-question analytics — free.

Start Timed Attempt