Download GATE (Graduate Aptitude Test in Engineering) GATE CSE Question Paper With Solutions
2
1.Ans. C
Sol. ?Breaks down? is a transitive
phrasal verb which means to divide
something such as a total amount into
separate parts.
Option (c) is most suitable.
2. Ans. A
Sol. The search engine business model
revolves around the fulcrum of trust.
Fulcrum is any thing that plays a central
or essential role in an activity, event, or
situation.
3.Ans. B
Sol. Speed of car A = 50 km/hr
Speed of car B = 60 km/hr
Since, both cars A and B are moving in same
direction, the relative speed = 60 ? 50 = 10
km/hr
Distance required between them = 20 km
4.Ans. C
Sol. Let share of each student = x
Total cost of gift = 10 ? x
x = 8(x + 150)
x = 600
Total cost = 10 ? 600 = 6000
5.Ans. D
Sol. A ?court? is for a ?judge? as a ?school? is for a
?teacher?.
Court is a place where a judge works.
Similarly, school is a place where a teacher
works.
6.Ans. B
Sol. Case I:
Criminals P Q R S
Assumption F T F F
Result QNC SC RC SC
S and R are criminal in the result is
impossible because only one person
committed the crime.
Case II:
Criminals P Q R S
Assumption T F F F
Result QC SNC RC SC
Q and R are criminal in the result is
impossible because only one person
committed the crime.
Case III:
Criminals P Q R S
Assumptio
n
F F T F
Result QNC SNC RNC SC
SNC and SC in the result which is
contradiction. [S committed crime and same
time not committed crime which is
contradiction]
Case IV:
Criminals P Q R S
Assumption F F F T
Result QNC SNC RC SNC
R is criminal in the result.
Hence this case satisfies only one person
committed the crime.
7.Ans. C
Sol. Percentage of Administrators
8.Ans. B
Sol. The passage states that the underlying
disease behind begging is the failure of the
state to protect citizens who fall through the
social security net.
option b can be concluded from the
above.
9.Ans. C
Sol.
Total number of students = 60 + 80 +
30 + 38 + 5 + 10 + 2 = 225
25% = 225
FirstRanker.com - FirstRanker's Choice
2
1.Ans. C
Sol. ?Breaks down? is a transitive
phrasal verb which means to divide
something such as a total amount into
separate parts.
Option (c) is most suitable.
2. Ans. A
Sol. The search engine business model
revolves around the fulcrum of trust.
Fulcrum is any thing that plays a central
or essential role in an activity, event, or
situation.
3.Ans. B
Sol. Speed of car A = 50 km/hr
Speed of car B = 60 km/hr
Since, both cars A and B are moving in same
direction, the relative speed = 60 ? 50 = 10
km/hr
Distance required between them = 20 km
4.Ans. C
Sol. Let share of each student = x
Total cost of gift = 10 ? x
x = 8(x + 150)
x = 600
Total cost = 10 ? 600 = 6000
5.Ans. D
Sol. A ?court? is for a ?judge? as a ?school? is for a
?teacher?.
Court is a place where a judge works.
Similarly, school is a place where a teacher
works.
6.Ans. B
Sol. Case I:
Criminals P Q R S
Assumption F T F F
Result QNC SC RC SC
S and R are criminal in the result is
impossible because only one person
committed the crime.
Case II:
Criminals P Q R S
Assumption T F F F
Result QC SNC RC SC
Q and R are criminal in the result is
impossible because only one person
committed the crime.
Case III:
Criminals P Q R S
Assumptio
n
F F T F
Result QNC SNC RNC SC
SNC and SC in the result which is
contradiction. [S committed crime and same
time not committed crime which is
contradiction]
Case IV:
Criminals P Q R S
Assumption F F F T
Result QNC SNC RC SNC
R is criminal in the result.
Hence this case satisfies only one person
committed the crime.
7.Ans. C
Sol. Percentage of Administrators
8.Ans. B
Sol. The passage states that the underlying
disease behind begging is the failure of the
state to protect citizens who fall through the
social security net.
option b can be concluded from the
above.
9.Ans. C
Sol.
Total number of students = 60 + 80 +
30 + 38 + 5 + 10 + 2 = 225
25% = 225
3
10.Ans. D
Sol. According to conditions mentioned in the
question ?D? is the best suited option.
11.Ans. D
Sol. Cache memory size = 16 kB
Block size = 16 B
Main memory address = 32 bit
Number of lines (N)
Fully associative cache memory (N-way)
So, number of sets (S)
? Address format:
So, TAG = 28 bit
Index = 0 bit (No address)
12.Ans. A
Sol.
13.Ans. D
Sol. LR parser is a bottom up parser.
Hence it uses right most derivation in
reverse order.
14.Ans. C
Sol. +28 ? 0000 0000 0001 1100
?28 ? 1111 1111 1110 0100 (2?s
complement form)
15.Ans. C
Sol. A = {(x, X), x ? X and X ? U}
The number of k element subsets of a
set U with n elements
The number of possible ordered pairs (x,
X) where x ? X is k ?
n
Ck for a given value of
k from 1 to n.
So total number of ordered pairs in A
So II is correct.
(Note that k = 0 is excluded since empty
set has no elements and cannot form an
order pair such as (x, X)).
But since by the combinational identity
So I is also correct.
So both I and II are correct.
16.Ans.B
Sol. (a) x ? y = (xy + x?y ?)?
= (xy )?
= x ? y, it is valid.
(b)
= ?m(1, 2, 4, 6)
= ?m(1, 2, 3, 4)
(x + y) ? z ? x ? (y + z)
So option (b) is invalid.
(c) (x ? y) ? z = x ? (y ? z)
Associativity is true on Ex-OR operator
so it valid.
(d)
= (x + y), so it is valid.
17.Ans. B
Sol. If L is regular, L ? L
R
is also regular by
closure property.
Suffix (L) and Prefix (L) are also regular
by closure property.
FirstRanker.com - FirstRanker's Choice
2
1.Ans. C
Sol. ?Breaks down? is a transitive
phrasal verb which means to divide
something such as a total amount into
separate parts.
Option (c) is most suitable.
2. Ans. A
Sol. The search engine business model
revolves around the fulcrum of trust.
Fulcrum is any thing that plays a central
or essential role in an activity, event, or
situation.
3.Ans. B
Sol. Speed of car A = 50 km/hr
Speed of car B = 60 km/hr
Since, both cars A and B are moving in same
direction, the relative speed = 60 ? 50 = 10
km/hr
Distance required between them = 20 km
4.Ans. C
Sol. Let share of each student = x
Total cost of gift = 10 ? x
x = 8(x + 150)
x = 600
Total cost = 10 ? 600 = 6000
5.Ans. D
Sol. A ?court? is for a ?judge? as a ?school? is for a
?teacher?.
Court is a place where a judge works.
Similarly, school is a place where a teacher
works.
6.Ans. B
Sol. Case I:
Criminals P Q R S
Assumption F T F F
Result QNC SC RC SC
S and R are criminal in the result is
impossible because only one person
committed the crime.
Case II:
Criminals P Q R S
Assumption T F F F
Result QC SNC RC SC
Q and R are criminal in the result is
impossible because only one person
committed the crime.
Case III:
Criminals P Q R S
Assumptio
n
F F T F
Result QNC SNC RNC SC
SNC and SC in the result which is
contradiction. [S committed crime and same
time not committed crime which is
contradiction]
Case IV:
Criminals P Q R S
Assumption F F F T
Result QNC SNC RC SNC
R is criminal in the result.
Hence this case satisfies only one person
committed the crime.
7.Ans. C
Sol. Percentage of Administrators
8.Ans. B
Sol. The passage states that the underlying
disease behind begging is the failure of the
state to protect citizens who fall through the
social security net.
option b can be concluded from the
above.
9.Ans. C
Sol.
Total number of students = 60 + 80 +
30 + 38 + 5 + 10 + 2 = 225
25% = 225
3
10.Ans. D
Sol. According to conditions mentioned in the
question ?D? is the best suited option.
11.Ans. D
Sol. Cache memory size = 16 kB
Block size = 16 B
Main memory address = 32 bit
Number of lines (N)
Fully associative cache memory (N-way)
So, number of sets (S)
? Address format:
So, TAG = 28 bit
Index = 0 bit (No address)
12.Ans. A
Sol.
13.Ans. D
Sol. LR parser is a bottom up parser.
Hence it uses right most derivation in
reverse order.
14.Ans. C
Sol. +28 ? 0000 0000 0001 1100
?28 ? 1111 1111 1110 0100 (2?s
complement form)
15.Ans. C
Sol. A = {(x, X), x ? X and X ? U}
The number of k element subsets of a
set U with n elements
The number of possible ordered pairs (x,
X) where x ? X is k ?
n
Ck for a given value of
k from 1 to n.
So total number of ordered pairs in A
So II is correct.
(Note that k = 0 is excluded since empty
set has no elements and cannot form an
order pair such as (x, X)).
But since by the combinational identity
So I is also correct.
So both I and II are correct.
16.Ans.B
Sol. (a) x ? y = (xy + x?y ?)?
= (xy )?
= x ? y, it is valid.
(b)
= ?m(1, 2, 4, 6)
= ?m(1, 2, 3, 4)
(x + y) ? z ? x ? (y + z)
So option (b) is invalid.
(c) (x ? y) ? z = x ? (y ? z)
Associativity is true on Ex-OR operator
so it valid.
(d)
= (x + y), so it is valid.
17.Ans. B
Sol. If L is regular, L ? L
R
is also regular by
closure property.
Suffix (L) and Prefix (L) are also regular
by closure property.
4
However option (b) {ww
R
|w ? L} need
not be regular since if L is an infinite regular
language, then {ww
R
|w ? L} will not only
be infinite, but also non-regular. Since it
involves string matching and we can
increase in length indefinitely and then finite
automata FA will run out of memory.
18.Ans. C
Sol. For example:
Let,
Hence,
Z = 11 which required 5 bits which is (n
+ 1) bits
19.Ans. D
Sol. Both I and II are equivalent statements.
20.Ans. B
Sol. R1 : ?a, b ? G, a R1 b if and only if ?g ?
G such that a = g
?1
bg
Reflexive: a = g
?1
ag can be satisfied by
putting g = e, identity ?e? always exists in a
group.
So reflexive
Symmetric: aRb ? a = g
?1
bg for some g
? b = gag
?1
= (g
?1
)
?1
ag
?1
g
?1
always exists for every g ? G.
So symmetric
Transitive: aRb and bRc ? a = g1
?1
bg1
and b = g2
?1
cg2 for some g1g2 ? G.
Now a = g1
?1
g2
?1
cg2g1 = (g2g1)
?1
cg2g1
g1 ? G and g2 ? G ? g2g1 ? G since group
is closed so aRb and aRb ? aRc hence
transitive
Clearly R1 is equivalence relation.
R2 is not equivalence it need not even
be reflexive, since aR2 a ? a = a
?1
?a which
not be true in a group.
R1 is equivalence relation is the correct
answer
21.Ans. C
Sol. I. Strict 2PL guaranteed conflict
serializable because of 2PL condition and
also strict recoverable.
II. Thomas Write timestamp ordering
ensures serializable. Thomas write rule
timestamp ordering allowed to execute
schedule which is view equal serial schedule
based on timestamp ordering.
22.Ans. D
Sol. In a complete graph we can traverse the n
vertices in any order and return to the
starting vertex and form a Hamiltonian
cycle. The number of such cycles will be n!
However, since circular rotations will have
to ignored. Since for example K4 with
vertices {1, 2, 3, 4}, the cycle 1-2-3-4 is
same as 2-3-4-1 is same as 3-4-1-2 etc. we
now get only (n ? 1)! distinct Hamiltonian
cycles. Further, the cycle 1-2-3-4 and 1-4-
3-2 are also same (clockwise and
anticlockwise).
So ignoring this orientation also we finally
get distinct Hamiltonian cycles.
23.Ans. C
Sol. form.
So apply L?H rule
24.Ans. B
Sol. B+ tree non leaf node have pointer to
data records is false statement.
B+ tree non leaf node consists of only
keys and tree pointers (node pointers).
Below is the structure of B+ tree non
leaf node
25.Ans. D
Sol. L = {a2 + 3k or b10 + 12k} for k ? 0
= a2 (a3)* or b10 (b12)*
= {a2, a5, a8, ..., b10, b22, b34 .....}
The pumping length is p, than for any
string w ? L with |w| ? p must have a repetition
i.e. such a string must be breakable into w = xyz
such that |y| ? 0 and y can be pumped
indefinitely, which is same as saying xyz ? L ?
xy *z ? L.
FirstRanker.com - FirstRanker's Choice
2
1.Ans. C
Sol. ?Breaks down? is a transitive
phrasal verb which means to divide
something such as a total amount into
separate parts.
Option (c) is most suitable.
2. Ans. A
Sol. The search engine business model
revolves around the fulcrum of trust.
Fulcrum is any thing that plays a central
or essential role in an activity, event, or
situation.
3.Ans. B
Sol. Speed of car A = 50 km/hr
Speed of car B = 60 km/hr
Since, both cars A and B are moving in same
direction, the relative speed = 60 ? 50 = 10
km/hr
Distance required between them = 20 km
4.Ans. C
Sol. Let share of each student = x
Total cost of gift = 10 ? x
x = 8(x + 150)
x = 600
Total cost = 10 ? 600 = 6000
5.Ans. D
Sol. A ?court? is for a ?judge? as a ?school? is for a
?teacher?.
Court is a place where a judge works.
Similarly, school is a place where a teacher
works.
6.Ans. B
Sol. Case I:
Criminals P Q R S
Assumption F T F F
Result QNC SC RC SC
S and R are criminal in the result is
impossible because only one person
committed the crime.
Case II:
Criminals P Q R S
Assumption T F F F
Result QC SNC RC SC
Q and R are criminal in the result is
impossible because only one person
committed the crime.
Case III:
Criminals P Q R S
Assumptio
n
F F T F
Result QNC SNC RNC SC
SNC and SC in the result which is
contradiction. [S committed crime and same
time not committed crime which is
contradiction]
Case IV:
Criminals P Q R S
Assumption F F F T
Result QNC SNC RC SNC
R is criminal in the result.
Hence this case satisfies only one person
committed the crime.
7.Ans. C
Sol. Percentage of Administrators
8.Ans. B
Sol. The passage states that the underlying
disease behind begging is the failure of the
state to protect citizens who fall through the
social security net.
option b can be concluded from the
above.
9.Ans. C
Sol.
Total number of students = 60 + 80 +
30 + 38 + 5 + 10 + 2 = 225
25% = 225
3
10.Ans. D
Sol. According to conditions mentioned in the
question ?D? is the best suited option.
11.Ans. D
Sol. Cache memory size = 16 kB
Block size = 16 B
Main memory address = 32 bit
Number of lines (N)
Fully associative cache memory (N-way)
So, number of sets (S)
? Address format:
So, TAG = 28 bit
Index = 0 bit (No address)
12.Ans. A
Sol.
13.Ans. D
Sol. LR parser is a bottom up parser.
Hence it uses right most derivation in
reverse order.
14.Ans. C
Sol. +28 ? 0000 0000 0001 1100
?28 ? 1111 1111 1110 0100 (2?s
complement form)
15.Ans. C
Sol. A = {(x, X), x ? X and X ? U}
The number of k element subsets of a
set U with n elements
The number of possible ordered pairs (x,
X) where x ? X is k ?
n
Ck for a given value of
k from 1 to n.
So total number of ordered pairs in A
So II is correct.
(Note that k = 0 is excluded since empty
set has no elements and cannot form an
order pair such as (x, X)).
But since by the combinational identity
So I is also correct.
So both I and II are correct.
16.Ans.B
Sol. (a) x ? y = (xy + x?y ?)?
= (xy )?
= x ? y, it is valid.
(b)
= ?m(1, 2, 4, 6)
= ?m(1, 2, 3, 4)
(x + y) ? z ? x ? (y + z)
So option (b) is invalid.
(c) (x ? y) ? z = x ? (y ? z)
Associativity is true on Ex-OR operator
so it valid.
(d)
= (x + y), so it is valid.
17.Ans. B
Sol. If L is regular, L ? L
R
is also regular by
closure property.
Suffix (L) and Prefix (L) are also regular
by closure property.
4
However option (b) {ww
R
|w ? L} need
not be regular since if L is an infinite regular
language, then {ww
R
|w ? L} will not only
be infinite, but also non-regular. Since it
involves string matching and we can
increase in length indefinitely and then finite
automata FA will run out of memory.
18.Ans. C
Sol. For example:
Let,
Hence,
Z = 11 which required 5 bits which is (n
+ 1) bits
19.Ans. D
Sol. Both I and II are equivalent statements.
20.Ans. B
Sol. R1 : ?a, b ? G, a R1 b if and only if ?g ?
G such that a = g
?1
bg
Reflexive: a = g
?1
ag can be satisfied by
putting g = e, identity ?e? always exists in a
group.
So reflexive
Symmetric: aRb ? a = g
?1
bg for some g
? b = gag
?1
= (g
?1
)
?1
ag
?1
g
?1
always exists for every g ? G.
So symmetric
Transitive: aRb and bRc ? a = g1
?1
bg1
and b = g2
?1
cg2 for some g1g2 ? G.
Now a = g1
?1
g2
?1
cg2g1 = (g2g1)
?1
cg2g1
g1 ? G and g2 ? G ? g2g1 ? G since group
is closed so aRb and aRb ? aRc hence
transitive
Clearly R1 is equivalence relation.
R2 is not equivalence it need not even
be reflexive, since aR2 a ? a = a
?1
?a which
not be true in a group.
R1 is equivalence relation is the correct
answer
21.Ans. C
Sol. I. Strict 2PL guaranteed conflict
serializable because of 2PL condition and
also strict recoverable.
II. Thomas Write timestamp ordering
ensures serializable. Thomas write rule
timestamp ordering allowed to execute
schedule which is view equal serial schedule
based on timestamp ordering.
22.Ans. D
Sol. In a complete graph we can traverse the n
vertices in any order and return to the
starting vertex and form a Hamiltonian
cycle. The number of such cycles will be n!
However, since circular rotations will have
to ignored. Since for example K4 with
vertices {1, 2, 3, 4}, the cycle 1-2-3-4 is
same as 2-3-4-1 is same as 3-4-1-2 etc. we
now get only (n ? 1)! distinct Hamiltonian
cycles. Further, the cycle 1-2-3-4 and 1-4-
3-2 are also same (clockwise and
anticlockwise).
So ignoring this orientation also we finally
get distinct Hamiltonian cycles.
23.Ans. C
Sol. form.
So apply L?H rule
24.Ans. B
Sol. B+ tree non leaf node have pointer to
data records is false statement.
B+ tree non leaf node consists of only
keys and tree pointers (node pointers).
Below is the structure of B+ tree non
leaf node
25.Ans. D
Sol. L = {a2 + 3k or b10 + 12k} for k ? 0
= a2 (a3)* or b10 (b12)*
= {a2, a5, a8, ..., b10, b22, b34 .....}
The pumping length is p, than for any
string w ? L with |w| ? p must have a repetition
i.e. such a string must be breakable into w = xyz
such that |y| ? 0 and y can be pumped
indefinitely, which is same as saying xyz ? L ?
xy *z ? L.
5
The minimum pumping length in this
language is clearly 11, since b10 is a string
which has no repetition number, so upto 10
no number can serve as a pumping length.
Minimum pumping length is 11. Any number
at or above minimum pumping length can
serve as a pumping length. The only number
at or above 11, in the choice given is 24.
26.Ans. B
Sol. SMTP is push protocol and to send email
and POP3 is pull protocol i.e. to retrieve
email.
27.Ans. (31)
28.Ans. (26)
29.Ans. (31)
Sol. S ? Aa
A ? BD
B ? b | ?
D ? d | ?
Follow (B) = {d, a}
Hence their index in descending order is 31.
30.Ans. (0.08)
31.Ans. (2)
Sol. By Fermat?s theorem
3
(5 ? 1)
mod 5 = 1
3
4
mod 5 = 1
3
51
mod 5 = (3
4
)
12
. 3
3
mod 5
= 3
3
mod 5
= 2
32.Ans. (0.502 to 0.504)
33.Ans. (80)
34.Ans. (6)
35.Ans. (29)
36.Ans. D
It will not print anything and will not
terminate
37.Ans. B
38.Ans. C
Sol.
N and P belongs to same subnet.
Hence, C is correct answer.
39.Ans. C
X sends an ARP request packet with
broadcast MAC address in its local
subnet
40.Ans. A
Sol. f1 . f2 = ?(2, 8, 14)
f1 = f3 ? (f1 . f2)
= ?(7, 8, 11)
41.Ans. C
Sol. (a) {ww
R
|w ? {a, b}* } is a CFL
(b) {wa
n
b
n
w
R
|w ? {a, b}*, n ? 0} is
a CFL, since we can first push w, then a?s,
b?s pop with a?s and w
R
pops with the w.
So PDA can accept the language.
(c) {wa
n
w
R
b
n
|w ? {a, b}*, n ? 0} is a not
CFL because after pushing w, we need to push a?s into
stack which will stop the w from being matched with
w
R
. If we don?t push a?s after w, than later we
cannot match with bn. So this language is not
acceptable by a PDA and hence not a CFL.
(d) {a
n
b
i
|i ? {n, 3n, 5n}, n ? 0}
= a
n
b
n
? a
n
b
3n
? a
n
b
5n
is CFL since
each of the three parts is a CFL and
closure under union guarantees that
result also is a CFL.
42.Ans. C
FirstRanker.com - FirstRanker's Choice
2
1.Ans. C
Sol. ?Breaks down? is a transitive
phrasal verb which means to divide
something such as a total amount into
separate parts.
Option (c) is most suitable.
2. Ans. A
Sol. The search engine business model
revolves around the fulcrum of trust.
Fulcrum is any thing that plays a central
or essential role in an activity, event, or
situation.
3.Ans. B
Sol. Speed of car A = 50 km/hr
Speed of car B = 60 km/hr
Since, both cars A and B are moving in same
direction, the relative speed = 60 ? 50 = 10
km/hr
Distance required between them = 20 km
4.Ans. C
Sol. Let share of each student = x
Total cost of gift = 10 ? x
x = 8(x + 150)
x = 600
Total cost = 10 ? 600 = 6000
5.Ans. D
Sol. A ?court? is for a ?judge? as a ?school? is for a
?teacher?.
Court is a place where a judge works.
Similarly, school is a place where a teacher
works.
6.Ans. B
Sol. Case I:
Criminals P Q R S
Assumption F T F F
Result QNC SC RC SC
S and R are criminal in the result is
impossible because only one person
committed the crime.
Case II:
Criminals P Q R S
Assumption T F F F
Result QC SNC RC SC
Q and R are criminal in the result is
impossible because only one person
committed the crime.
Case III:
Criminals P Q R S
Assumptio
n
F F T F
Result QNC SNC RNC SC
SNC and SC in the result which is
contradiction. [S committed crime and same
time not committed crime which is
contradiction]
Case IV:
Criminals P Q R S
Assumption F F F T
Result QNC SNC RC SNC
R is criminal in the result.
Hence this case satisfies only one person
committed the crime.
7.Ans. C
Sol. Percentage of Administrators
8.Ans. B
Sol. The passage states that the underlying
disease behind begging is the failure of the
state to protect citizens who fall through the
social security net.
option b can be concluded from the
above.
9.Ans. C
Sol.
Total number of students = 60 + 80 +
30 + 38 + 5 + 10 + 2 = 225
25% = 225
3
10.Ans. D
Sol. According to conditions mentioned in the
question ?D? is the best suited option.
11.Ans. D
Sol. Cache memory size = 16 kB
Block size = 16 B
Main memory address = 32 bit
Number of lines (N)
Fully associative cache memory (N-way)
So, number of sets (S)
? Address format:
So, TAG = 28 bit
Index = 0 bit (No address)
12.Ans. A
Sol.
13.Ans. D
Sol. LR parser is a bottom up parser.
Hence it uses right most derivation in
reverse order.
14.Ans. C
Sol. +28 ? 0000 0000 0001 1100
?28 ? 1111 1111 1110 0100 (2?s
complement form)
15.Ans. C
Sol. A = {(x, X), x ? X and X ? U}
The number of k element subsets of a
set U with n elements
The number of possible ordered pairs (x,
X) where x ? X is k ?
n
Ck for a given value of
k from 1 to n.
So total number of ordered pairs in A
So II is correct.
(Note that k = 0 is excluded since empty
set has no elements and cannot form an
order pair such as (x, X)).
But since by the combinational identity
So I is also correct.
So both I and II are correct.
16.Ans.B
Sol. (a) x ? y = (xy + x?y ?)?
= (xy )?
= x ? y, it is valid.
(b)
= ?m(1, 2, 4, 6)
= ?m(1, 2, 3, 4)
(x + y) ? z ? x ? (y + z)
So option (b) is invalid.
(c) (x ? y) ? z = x ? (y ? z)
Associativity is true on Ex-OR operator
so it valid.
(d)
= (x + y), so it is valid.
17.Ans. B
Sol. If L is regular, L ? L
R
is also regular by
closure property.
Suffix (L) and Prefix (L) are also regular
by closure property.
4
However option (b) {ww
R
|w ? L} need
not be regular since if L is an infinite regular
language, then {ww
R
|w ? L} will not only
be infinite, but also non-regular. Since it
involves string matching and we can
increase in length indefinitely and then finite
automata FA will run out of memory.
18.Ans. C
Sol. For example:
Let,
Hence,
Z = 11 which required 5 bits which is (n
+ 1) bits
19.Ans. D
Sol. Both I and II are equivalent statements.
20.Ans. B
Sol. R1 : ?a, b ? G, a R1 b if and only if ?g ?
G such that a = g
?1
bg
Reflexive: a = g
?1
ag can be satisfied by
putting g = e, identity ?e? always exists in a
group.
So reflexive
Symmetric: aRb ? a = g
?1
bg for some g
? b = gag
?1
= (g
?1
)
?1
ag
?1
g
?1
always exists for every g ? G.
So symmetric
Transitive: aRb and bRc ? a = g1
?1
bg1
and b = g2
?1
cg2 for some g1g2 ? G.
Now a = g1
?1
g2
?1
cg2g1 = (g2g1)
?1
cg2g1
g1 ? G and g2 ? G ? g2g1 ? G since group
is closed so aRb and aRb ? aRc hence
transitive
Clearly R1 is equivalence relation.
R2 is not equivalence it need not even
be reflexive, since aR2 a ? a = a
?1
?a which
not be true in a group.
R1 is equivalence relation is the correct
answer
21.Ans. C
Sol. I. Strict 2PL guaranteed conflict
serializable because of 2PL condition and
also strict recoverable.
II. Thomas Write timestamp ordering
ensures serializable. Thomas write rule
timestamp ordering allowed to execute
schedule which is view equal serial schedule
based on timestamp ordering.
22.Ans. D
Sol. In a complete graph we can traverse the n
vertices in any order and return to the
starting vertex and form a Hamiltonian
cycle. The number of such cycles will be n!
However, since circular rotations will have
to ignored. Since for example K4 with
vertices {1, 2, 3, 4}, the cycle 1-2-3-4 is
same as 2-3-4-1 is same as 3-4-1-2 etc. we
now get only (n ? 1)! distinct Hamiltonian
cycles. Further, the cycle 1-2-3-4 and 1-4-
3-2 are also same (clockwise and
anticlockwise).
So ignoring this orientation also we finally
get distinct Hamiltonian cycles.
23.Ans. C
Sol. form.
So apply L?H rule
24.Ans. B
Sol. B+ tree non leaf node have pointer to
data records is false statement.
B+ tree non leaf node consists of only
keys and tree pointers (node pointers).
Below is the structure of B+ tree non
leaf node
25.Ans. D
Sol. L = {a2 + 3k or b10 + 12k} for k ? 0
= a2 (a3)* or b10 (b12)*
= {a2, a5, a8, ..., b10, b22, b34 .....}
The pumping length is p, than for any
string w ? L with |w| ? p must have a repetition
i.e. such a string must be breakable into w = xyz
such that |y| ? 0 and y can be pumped
indefinitely, which is same as saying xyz ? L ?
xy *z ? L.
5
The minimum pumping length in this
language is clearly 11, since b10 is a string
which has no repetition number, so upto 10
no number can serve as a pumping length.
Minimum pumping length is 11. Any number
at or above minimum pumping length can
serve as a pumping length. The only number
at or above 11, in the choice given is 24.
26.Ans. B
Sol. SMTP is push protocol and to send email
and POP3 is pull protocol i.e. to retrieve
email.
27.Ans. (31)
28.Ans. (26)
29.Ans. (31)
Sol. S ? Aa
A ? BD
B ? b | ?
D ? d | ?
Follow (B) = {d, a}
Hence their index in descending order is 31.
30.Ans. (0.08)
31.Ans. (2)
Sol. By Fermat?s theorem
3
(5 ? 1)
mod 5 = 1
3
4
mod 5 = 1
3
51
mod 5 = (3
4
)
12
. 3
3
mod 5
= 3
3
mod 5
= 2
32.Ans. (0.502 to 0.504)
33.Ans. (80)
34.Ans. (6)
35.Ans. (29)
36.Ans. D
It will not print anything and will not
terminate
37.Ans. B
38.Ans. C
Sol.
N and P belongs to same subnet.
Hence, C is correct answer.
39.Ans. C
X sends an ARP request packet with
broadcast MAC address in its local
subnet
40.Ans. A
Sol. f1 . f2 = ?(2, 8, 14)
f1 = f3 ? (f1 . f2)
= ?(7, 8, 11)
41.Ans. C
Sol. (a) {ww
R
|w ? {a, b}* } is a CFL
(b) {wa
n
b
n
w
R
|w ? {a, b}*, n ? 0} is
a CFL, since we can first push w, then a?s,
b?s pop with a?s and w
R
pops with the w.
So PDA can accept the language.
(c) {wa
n
w
R
b
n
|w ? {a, b}*, n ? 0} is a not
CFL because after pushing w, we need to push a?s into
stack which will stop the w from being matched with
w
R
. If we don?t push a?s after w, than later we
cannot match with bn. So this language is not
acceptable by a PDA and hence not a CFL.
(d) {a
n
b
i
|i ? {n, 3n, 5n}, n ? 0}
= a
n
b
n
? a
n
b
3n
? a
n
b
5n
is CFL since
each of the three parts is a CFL and
closure under union guarantees that
result also is a CFL.
42.Ans. C
6
Sol. X(PQRS) {QR ? S, R ? P, S ? Q}
decomposed into
Y(PR) Z(QRS)
{R ? P} {QR ? S, S ? Q}
Candidate key : R Candidate key : QR,
RS
Relation Y in BCNF Relation Z in 3NF but
not BCNF
Common attribute between Y and Z
relations is R which is key for relation Y.
So that given decomposition is lossless
join decomposition.
R ? P in Y
are in Z
and dependency preserving decomposition.
Hence , C is the correct answer.
43.Ans. B
Sol. 1 word = 4 bytes
Page size = 8 kB = 213 B
Number of words in 1 page
TLB can hold 128 valid entries so, at
most 128 ? 2
11
memory address can be
addressed without TLB miss.
128 ? 2
11
= 256 ? 2
10
44.Ans. B
Sol. S1: The set LRE is known to be countably
infinite since it corresponds with set of
turing machines.
S2: Since syntactically valid C programs
surely run on Turing machines, this set is
also a subset of set of Turing machines,
which is countable.
S3: Set of all languages = 2
?
which is
known to be uncountable. ?
*
countably
infinite
? 2
?
is uncountable.
S4: Set of all non-regular languages
includes set LNOT RE which is uncountable
infinite and hence is uncountable.
So, S3 and S4 are uncountable.
Hence, B is the correct answer.
45.Ans. C
Sol. ?x[?z?x ? ((z = x) ? (z = 1)) ? ?w (w
> x) ? (?z z?w ? ((w = z) ? (z = 1)))]
The predicate ? simply says that if z is a
prime number in the set then there exists
another prime number is the set which is
larger.
Clearly ? is true in S2 and S3 since in set
of all integers as well as all positive integers,
there is a prime number greater than any
given prime number.
However, in S1 : {1, 2, 3, .....100} ? is
false since for prime number 97 ? S1 there
exists no prime number in the set which is
greater.
So correct answer is C.
46.Ans. A
Sol. SDT for inserting type information in the
symbol table
D ? TL {L.idtype = T.stype}
T ? int {T.stype = int}
T ? float {T.stype = float}
L ? L1, id {L1.itype = L.itype}
addtype(id.entry, L.itype)
L ? id addtype(id.entry, L.itype)
47. Ans. C
Answer is O(n^2)
48.Ans. C
Sol. If no two edges of G have same weight
surely G will have unique spanning tree is
true.
So I is true
Also if, for every cut of G, there is a
unique minimum weight edge crossing the
cut then G will have unique spanning tree is
also true. So II is true
[Note: The converse of II is not true, but
that is not relevant to this question]
So both I and II are true.
Option (d) is correct.
49.Ans. A
50.Ans. A
FirstRanker.com - FirstRanker's Choice
2
1.Ans. C
Sol. ?Breaks down? is a transitive
phrasal verb which means to divide
something such as a total amount into
separate parts.
Option (c) is most suitable.
2. Ans. A
Sol. The search engine business model
revolves around the fulcrum of trust.
Fulcrum is any thing that plays a central
or essential role in an activity, event, or
situation.
3.Ans. B
Sol. Speed of car A = 50 km/hr
Speed of car B = 60 km/hr
Since, both cars A and B are moving in same
direction, the relative speed = 60 ? 50 = 10
km/hr
Distance required between them = 20 km
4.Ans. C
Sol. Let share of each student = x
Total cost of gift = 10 ? x
x = 8(x + 150)
x = 600
Total cost = 10 ? 600 = 6000
5.Ans. D
Sol. A ?court? is for a ?judge? as a ?school? is for a
?teacher?.
Court is a place where a judge works.
Similarly, school is a place where a teacher
works.
6.Ans. B
Sol. Case I:
Criminals P Q R S
Assumption F T F F
Result QNC SC RC SC
S and R are criminal in the result is
impossible because only one person
committed the crime.
Case II:
Criminals P Q R S
Assumption T F F F
Result QC SNC RC SC
Q and R are criminal in the result is
impossible because only one person
committed the crime.
Case III:
Criminals P Q R S
Assumptio
n
F F T F
Result QNC SNC RNC SC
SNC and SC in the result which is
contradiction. [S committed crime and same
time not committed crime which is
contradiction]
Case IV:
Criminals P Q R S
Assumption F F F T
Result QNC SNC RC SNC
R is criminal in the result.
Hence this case satisfies only one person
committed the crime.
7.Ans. C
Sol. Percentage of Administrators
8.Ans. B
Sol. The passage states that the underlying
disease behind begging is the failure of the
state to protect citizens who fall through the
social security net.
option b can be concluded from the
above.
9.Ans. C
Sol.
Total number of students = 60 + 80 +
30 + 38 + 5 + 10 + 2 = 225
25% = 225
3
10.Ans. D
Sol. According to conditions mentioned in the
question ?D? is the best suited option.
11.Ans. D
Sol. Cache memory size = 16 kB
Block size = 16 B
Main memory address = 32 bit
Number of lines (N)
Fully associative cache memory (N-way)
So, number of sets (S)
? Address format:
So, TAG = 28 bit
Index = 0 bit (No address)
12.Ans. A
Sol.
13.Ans. D
Sol. LR parser is a bottom up parser.
Hence it uses right most derivation in
reverse order.
14.Ans. C
Sol. +28 ? 0000 0000 0001 1100
?28 ? 1111 1111 1110 0100 (2?s
complement form)
15.Ans. C
Sol. A = {(x, X), x ? X and X ? U}
The number of k element subsets of a
set U with n elements
The number of possible ordered pairs (x,
X) where x ? X is k ?
n
Ck for a given value of
k from 1 to n.
So total number of ordered pairs in A
So II is correct.
(Note that k = 0 is excluded since empty
set has no elements and cannot form an
order pair such as (x, X)).
But since by the combinational identity
So I is also correct.
So both I and II are correct.
16.Ans.B
Sol. (a) x ? y = (xy + x?y ?)?
= (xy )?
= x ? y, it is valid.
(b)
= ?m(1, 2, 4, 6)
= ?m(1, 2, 3, 4)
(x + y) ? z ? x ? (y + z)
So option (b) is invalid.
(c) (x ? y) ? z = x ? (y ? z)
Associativity is true on Ex-OR operator
so it valid.
(d)
= (x + y), so it is valid.
17.Ans. B
Sol. If L is regular, L ? L
R
is also regular by
closure property.
Suffix (L) and Prefix (L) are also regular
by closure property.
4
However option (b) {ww
R
|w ? L} need
not be regular since if L is an infinite regular
language, then {ww
R
|w ? L} will not only
be infinite, but also non-regular. Since it
involves string matching and we can
increase in length indefinitely and then finite
automata FA will run out of memory.
18.Ans. C
Sol. For example:
Let,
Hence,
Z = 11 which required 5 bits which is (n
+ 1) bits
19.Ans. D
Sol. Both I and II are equivalent statements.
20.Ans. B
Sol. R1 : ?a, b ? G, a R1 b if and only if ?g ?
G such that a = g
?1
bg
Reflexive: a = g
?1
ag can be satisfied by
putting g = e, identity ?e? always exists in a
group.
So reflexive
Symmetric: aRb ? a = g
?1
bg for some g
? b = gag
?1
= (g
?1
)
?1
ag
?1
g
?1
always exists for every g ? G.
So symmetric
Transitive: aRb and bRc ? a = g1
?1
bg1
and b = g2
?1
cg2 for some g1g2 ? G.
Now a = g1
?1
g2
?1
cg2g1 = (g2g1)
?1
cg2g1
g1 ? G and g2 ? G ? g2g1 ? G since group
is closed so aRb and aRb ? aRc hence
transitive
Clearly R1 is equivalence relation.
R2 is not equivalence it need not even
be reflexive, since aR2 a ? a = a
?1
?a which
not be true in a group.
R1 is equivalence relation is the correct
answer
21.Ans. C
Sol. I. Strict 2PL guaranteed conflict
serializable because of 2PL condition and
also strict recoverable.
II. Thomas Write timestamp ordering
ensures serializable. Thomas write rule
timestamp ordering allowed to execute
schedule which is view equal serial schedule
based on timestamp ordering.
22.Ans. D
Sol. In a complete graph we can traverse the n
vertices in any order and return to the
starting vertex and form a Hamiltonian
cycle. The number of such cycles will be n!
However, since circular rotations will have
to ignored. Since for example K4 with
vertices {1, 2, 3, 4}, the cycle 1-2-3-4 is
same as 2-3-4-1 is same as 3-4-1-2 etc. we
now get only (n ? 1)! distinct Hamiltonian
cycles. Further, the cycle 1-2-3-4 and 1-4-
3-2 are also same (clockwise and
anticlockwise).
So ignoring this orientation also we finally
get distinct Hamiltonian cycles.
23.Ans. C
Sol. form.
So apply L?H rule
24.Ans. B
Sol. B+ tree non leaf node have pointer to
data records is false statement.
B+ tree non leaf node consists of only
keys and tree pointers (node pointers).
Below is the structure of B+ tree non
leaf node
25.Ans. D
Sol. L = {a2 + 3k or b10 + 12k} for k ? 0
= a2 (a3)* or b10 (b12)*
= {a2, a5, a8, ..., b10, b22, b34 .....}
The pumping length is p, than for any
string w ? L with |w| ? p must have a repetition
i.e. such a string must be breakable into w = xyz
such that |y| ? 0 and y can be pumped
indefinitely, which is same as saying xyz ? L ?
xy *z ? L.
5
The minimum pumping length in this
language is clearly 11, since b10 is a string
which has no repetition number, so upto 10
no number can serve as a pumping length.
Minimum pumping length is 11. Any number
at or above minimum pumping length can
serve as a pumping length. The only number
at or above 11, in the choice given is 24.
26.Ans. B
Sol. SMTP is push protocol and to send email
and POP3 is pull protocol i.e. to retrieve
email.
27.Ans. (31)
28.Ans. (26)
29.Ans. (31)
Sol. S ? Aa
A ? BD
B ? b | ?
D ? d | ?
Follow (B) = {d, a}
Hence their index in descending order is 31.
30.Ans. (0.08)
31.Ans. (2)
Sol. By Fermat?s theorem
3
(5 ? 1)
mod 5 = 1
3
4
mod 5 = 1
3
51
mod 5 = (3
4
)
12
. 3
3
mod 5
= 3
3
mod 5
= 2
32.Ans. (0.502 to 0.504)
33.Ans. (80)
34.Ans. (6)
35.Ans. (29)
36.Ans. D
It will not print anything and will not
terminate
37.Ans. B
38.Ans. C
Sol.
N and P belongs to same subnet.
Hence, C is correct answer.
39.Ans. C
X sends an ARP request packet with
broadcast MAC address in its local
subnet
40.Ans. A
Sol. f1 . f2 = ?(2, 8, 14)
f1 = f3 ? (f1 . f2)
= ?(7, 8, 11)
41.Ans. C
Sol. (a) {ww
R
|w ? {a, b}* } is a CFL
(b) {wa
n
b
n
w
R
|w ? {a, b}*, n ? 0} is
a CFL, since we can first push w, then a?s,
b?s pop with a?s and w
R
pops with the w.
So PDA can accept the language.
(c) {wa
n
w
R
b
n
|w ? {a, b}*, n ? 0} is a not
CFL because after pushing w, we need to push a?s into
stack which will stop the w from being matched with
w
R
. If we don?t push a?s after w, than later we
cannot match with bn. So this language is not
acceptable by a PDA and hence not a CFL.
(d) {a
n
b
i
|i ? {n, 3n, 5n}, n ? 0}
= a
n
b
n
? a
n
b
3n
? a
n
b
5n
is CFL since
each of the three parts is a CFL and
closure under union guarantees that
result also is a CFL.
42.Ans. C
6
Sol. X(PQRS) {QR ? S, R ? P, S ? Q}
decomposed into
Y(PR) Z(QRS)
{R ? P} {QR ? S, S ? Q}
Candidate key : R Candidate key : QR,
RS
Relation Y in BCNF Relation Z in 3NF but
not BCNF
Common attribute between Y and Z
relations is R which is key for relation Y.
So that given decomposition is lossless
join decomposition.
R ? P in Y
are in Z
and dependency preserving decomposition.
Hence , C is the correct answer.
43.Ans. B
Sol. 1 word = 4 bytes
Page size = 8 kB = 213 B
Number of words in 1 page
TLB can hold 128 valid entries so, at
most 128 ? 2
11
memory address can be
addressed without TLB miss.
128 ? 2
11
= 256 ? 2
10
44.Ans. B
Sol. S1: The set LRE is known to be countably
infinite since it corresponds with set of
turing machines.
S2: Since syntactically valid C programs
surely run on Turing machines, this set is
also a subset of set of Turing machines,
which is countable.
S3: Set of all languages = 2
?
which is
known to be uncountable. ?
*
countably
infinite
? 2
?
is uncountable.
S4: Set of all non-regular languages
includes set LNOT RE which is uncountable
infinite and hence is uncountable.
So, S3 and S4 are uncountable.
Hence, B is the correct answer.
45.Ans. C
Sol. ?x[?z?x ? ((z = x) ? (z = 1)) ? ?w (w
> x) ? (?z z?w ? ((w = z) ? (z = 1)))]
The predicate ? simply says that if z is a
prime number in the set then there exists
another prime number is the set which is
larger.
Clearly ? is true in S2 and S3 since in set
of all integers as well as all positive integers,
there is a prime number greater than any
given prime number.
However, in S1 : {1, 2, 3, .....100} ? is
false since for prime number 97 ? S1 there
exists no prime number in the set which is
greater.
So correct answer is C.
46.Ans. A
Sol. SDT for inserting type information in the
symbol table
D ? TL {L.idtype = T.stype}
T ? int {T.stype = int}
T ? float {T.stype = float}
L ? L1, id {L1.itype = L.itype}
addtype(id.entry, L.itype)
L ? id addtype(id.entry, L.itype)
47. Ans. C
Answer is O(n^2)
48.Ans. C
Sol. If no two edges of G have same weight
surely G will have unique spanning tree is
true.
So I is true
Also if, for every cut of G, there is a
unique minimum weight edge crossing the
cut then G will have unique spanning tree is
also true. So II is true
[Note: The converse of II is not true, but
that is not relevant to this question]
So both I and II are true.
Option (d) is correct.
49.Ans. A
50.Ans. A
7
51.Ans. (2)
Let?s assume , Z = 2
Average waiting time (WT)
Hence, Z = 2
52.Ans. (4.0 to 4.1)
53.Ans. 5
Sol.
Total number of items in the set GOTO
(I0, ? ) is 5.
54.Ans. (12)
Sol. Product of eigenvalues is same as the
determinant of a matrix.
55.Ans. (160)
Sol. Total time to transfer a cache block = 1
+ 3 + 8 = 12 cycles
8 W _____________ 12 cycles
8 ? 4 bytes ________________ 12
cycles
? B _____________ 1 sec
56.Ans. 4.25
No. of pairs with path length 0=8.0=8.
No. of pairs with path length 1=0.1=0.
No. of pairs with path length 2=8.2=8.
No. of pairs with path length 3=0.3=0.
No. of pairs with path length 4=16.4=16.
No. of pairs with path length 5=0.5=0.
No. of pairs with path length 6=32.6=32.
Total number of possible pairs
=8?8=64=8?8=64
So, expected path length,E(x),
=0?864+2?864+4?1664+6?3264=27264
=4.25
57.Ans. (0.8)
Sol. It is given that, Polynomial 3x
2
+ 6xY +
3Y + 6 has only real roots
b
2
? 4ax ? 0
(6Y)
2
? 4(3) (3Y+ 6) ? 0
Y
2
? Y + 2 ? 0
Y ? (??, ? 1] ? [2, ?)
? Y ? [2, 6)
Since y is uniformly distributed in (1, 6)
Probability distributed function,
58.Ans. (120)
FirstRanker.com - FirstRanker's Choice
2
1.Ans. C
Sol. ?Breaks down? is a transitive
phrasal verb which means to divide
something such as a total amount into
separate parts.
Option (c) is most suitable.
2. Ans. A
Sol. The search engine business model
revolves around the fulcrum of trust.
Fulcrum is any thing that plays a central
or essential role in an activity, event, or
situation.
3.Ans. B
Sol. Speed of car A = 50 km/hr
Speed of car B = 60 km/hr
Since, both cars A and B are moving in same
direction, the relative speed = 60 ? 50 = 10
km/hr
Distance required between them = 20 km
4.Ans. C
Sol. Let share of each student = x
Total cost of gift = 10 ? x
x = 8(x + 150)
x = 600
Total cost = 10 ? 600 = 6000
5.Ans. D
Sol. A ?court? is for a ?judge? as a ?school? is for a
?teacher?.
Court is a place where a judge works.
Similarly, school is a place where a teacher
works.
6.Ans. B
Sol. Case I:
Criminals P Q R S
Assumption F T F F
Result QNC SC RC SC
S and R are criminal in the result is
impossible because only one person
committed the crime.
Case II:
Criminals P Q R S
Assumption T F F F
Result QC SNC RC SC
Q and R are criminal in the result is
impossible because only one person
committed the crime.
Case III:
Criminals P Q R S
Assumptio
n
F F T F
Result QNC SNC RNC SC
SNC and SC in the result which is
contradiction. [S committed crime and same
time not committed crime which is
contradiction]
Case IV:
Criminals P Q R S
Assumption F F F T
Result QNC SNC RC SNC
R is criminal in the result.
Hence this case satisfies only one person
committed the crime.
7.Ans. C
Sol. Percentage of Administrators
8.Ans. B
Sol. The passage states that the underlying
disease behind begging is the failure of the
state to protect citizens who fall through the
social security net.
option b can be concluded from the
above.
9.Ans. C
Sol.
Total number of students = 60 + 80 +
30 + 38 + 5 + 10 + 2 = 225
25% = 225
3
10.Ans. D
Sol. According to conditions mentioned in the
question ?D? is the best suited option.
11.Ans. D
Sol. Cache memory size = 16 kB
Block size = 16 B
Main memory address = 32 bit
Number of lines (N)
Fully associative cache memory (N-way)
So, number of sets (S)
? Address format:
So, TAG = 28 bit
Index = 0 bit (No address)
12.Ans. A
Sol.
13.Ans. D
Sol. LR parser is a bottom up parser.
Hence it uses right most derivation in
reverse order.
14.Ans. C
Sol. +28 ? 0000 0000 0001 1100
?28 ? 1111 1111 1110 0100 (2?s
complement form)
15.Ans. C
Sol. A = {(x, X), x ? X and X ? U}
The number of k element subsets of a
set U with n elements
The number of possible ordered pairs (x,
X) where x ? X is k ?
n
Ck for a given value of
k from 1 to n.
So total number of ordered pairs in A
So II is correct.
(Note that k = 0 is excluded since empty
set has no elements and cannot form an
order pair such as (x, X)).
But since by the combinational identity
So I is also correct.
So both I and II are correct.
16.Ans.B
Sol. (a) x ? y = (xy + x?y ?)?
= (xy )?
= x ? y, it is valid.
(b)
= ?m(1, 2, 4, 6)
= ?m(1, 2, 3, 4)
(x + y) ? z ? x ? (y + z)
So option (b) is invalid.
(c) (x ? y) ? z = x ? (y ? z)
Associativity is true on Ex-OR operator
so it valid.
(d)
= (x + y), so it is valid.
17.Ans. B
Sol. If L is regular, L ? L
R
is also regular by
closure property.
Suffix (L) and Prefix (L) are also regular
by closure property.
4
However option (b) {ww
R
|w ? L} need
not be regular since if L is an infinite regular
language, then {ww
R
|w ? L} will not only
be infinite, but also non-regular. Since it
involves string matching and we can
increase in length indefinitely and then finite
automata FA will run out of memory.
18.Ans. C
Sol. For example:
Let,
Hence,
Z = 11 which required 5 bits which is (n
+ 1) bits
19.Ans. D
Sol. Both I and II are equivalent statements.
20.Ans. B
Sol. R1 : ?a, b ? G, a R1 b if and only if ?g ?
G such that a = g
?1
bg
Reflexive: a = g
?1
ag can be satisfied by
putting g = e, identity ?e? always exists in a
group.
So reflexive
Symmetric: aRb ? a = g
?1
bg for some g
? b = gag
?1
= (g
?1
)
?1
ag
?1
g
?1
always exists for every g ? G.
So symmetric
Transitive: aRb and bRc ? a = g1
?1
bg1
and b = g2
?1
cg2 for some g1g2 ? G.
Now a = g1
?1
g2
?1
cg2g1 = (g2g1)
?1
cg2g1
g1 ? G and g2 ? G ? g2g1 ? G since group
is closed so aRb and aRb ? aRc hence
transitive
Clearly R1 is equivalence relation.
R2 is not equivalence it need not even
be reflexive, since aR2 a ? a = a
?1
?a which
not be true in a group.
R1 is equivalence relation is the correct
answer
21.Ans. C
Sol. I. Strict 2PL guaranteed conflict
serializable because of 2PL condition and
also strict recoverable.
II. Thomas Write timestamp ordering
ensures serializable. Thomas write rule
timestamp ordering allowed to execute
schedule which is view equal serial schedule
based on timestamp ordering.
22.Ans. D
Sol. In a complete graph we can traverse the n
vertices in any order and return to the
starting vertex and form a Hamiltonian
cycle. The number of such cycles will be n!
However, since circular rotations will have
to ignored. Since for example K4 with
vertices {1, 2, 3, 4}, the cycle 1-2-3-4 is
same as 2-3-4-1 is same as 3-4-1-2 etc. we
now get only (n ? 1)! distinct Hamiltonian
cycles. Further, the cycle 1-2-3-4 and 1-4-
3-2 are also same (clockwise and
anticlockwise).
So ignoring this orientation also we finally
get distinct Hamiltonian cycles.
23.Ans. C
Sol. form.
So apply L?H rule
24.Ans. B
Sol. B+ tree non leaf node have pointer to
data records is false statement.
B+ tree non leaf node consists of only
keys and tree pointers (node pointers).
Below is the structure of B+ tree non
leaf node
25.Ans. D
Sol. L = {a2 + 3k or b10 + 12k} for k ? 0
= a2 (a3)* or b10 (b12)*
= {a2, a5, a8, ..., b10, b22, b34 .....}
The pumping length is p, than for any
string w ? L with |w| ? p must have a repetition
i.e. such a string must be breakable into w = xyz
such that |y| ? 0 and y can be pumped
indefinitely, which is same as saying xyz ? L ?
xy *z ? L.
5
The minimum pumping length in this
language is clearly 11, since b10 is a string
which has no repetition number, so upto 10
no number can serve as a pumping length.
Minimum pumping length is 11. Any number
at or above minimum pumping length can
serve as a pumping length. The only number
at or above 11, in the choice given is 24.
26.Ans. B
Sol. SMTP is push protocol and to send email
and POP3 is pull protocol i.e. to retrieve
email.
27.Ans. (31)
28.Ans. (26)
29.Ans. (31)
Sol. S ? Aa
A ? BD
B ? b | ?
D ? d | ?
Follow (B) = {d, a}
Hence their index in descending order is 31.
30.Ans. (0.08)
31.Ans. (2)
Sol. By Fermat?s theorem
3
(5 ? 1)
mod 5 = 1
3
4
mod 5 = 1
3
51
mod 5 = (3
4
)
12
. 3
3
mod 5
= 3
3
mod 5
= 2
32.Ans. (0.502 to 0.504)
33.Ans. (80)
34.Ans. (6)
35.Ans. (29)
36.Ans. D
It will not print anything and will not
terminate
37.Ans. B
38.Ans. C
Sol.
N and P belongs to same subnet.
Hence, C is correct answer.
39.Ans. C
X sends an ARP request packet with
broadcast MAC address in its local
subnet
40.Ans. A
Sol. f1 . f2 = ?(2, 8, 14)
f1 = f3 ? (f1 . f2)
= ?(7, 8, 11)
41.Ans. C
Sol. (a) {ww
R
|w ? {a, b}* } is a CFL
(b) {wa
n
b
n
w
R
|w ? {a, b}*, n ? 0} is
a CFL, since we can first push w, then a?s,
b?s pop with a?s and w
R
pops with the w.
So PDA can accept the language.
(c) {wa
n
w
R
b
n
|w ? {a, b}*, n ? 0} is a not
CFL because after pushing w, we need to push a?s into
stack which will stop the w from being matched with
w
R
. If we don?t push a?s after w, than later we
cannot match with bn. So this language is not
acceptable by a PDA and hence not a CFL.
(d) {a
n
b
i
|i ? {n, 3n, 5n}, n ? 0}
= a
n
b
n
? a
n
b
3n
? a
n
b
5n
is CFL since
each of the three parts is a CFL and
closure under union guarantees that
result also is a CFL.
42.Ans. C
6
Sol. X(PQRS) {QR ? S, R ? P, S ? Q}
decomposed into
Y(PR) Z(QRS)
{R ? P} {QR ? S, S ? Q}
Candidate key : R Candidate key : QR,
RS
Relation Y in BCNF Relation Z in 3NF but
not BCNF
Common attribute between Y and Z
relations is R which is key for relation Y.
So that given decomposition is lossless
join decomposition.
R ? P in Y
are in Z
and dependency preserving decomposition.
Hence , C is the correct answer.
43.Ans. B
Sol. 1 word = 4 bytes
Page size = 8 kB = 213 B
Number of words in 1 page
TLB can hold 128 valid entries so, at
most 128 ? 2
11
memory address can be
addressed without TLB miss.
128 ? 2
11
= 256 ? 2
10
44.Ans. B
Sol. S1: The set LRE is known to be countably
infinite since it corresponds with set of
turing machines.
S2: Since syntactically valid C programs
surely run on Turing machines, this set is
also a subset of set of Turing machines,
which is countable.
S3: Set of all languages = 2
?
which is
known to be uncountable. ?
*
countably
infinite
? 2
?
is uncountable.
S4: Set of all non-regular languages
includes set LNOT RE which is uncountable
infinite and hence is uncountable.
So, S3 and S4 are uncountable.
Hence, B is the correct answer.
45.Ans. C
Sol. ?x[?z?x ? ((z = x) ? (z = 1)) ? ?w (w
> x) ? (?z z?w ? ((w = z) ? (z = 1)))]
The predicate ? simply says that if z is a
prime number in the set then there exists
another prime number is the set which is
larger.
Clearly ? is true in S2 and S3 since in set
of all integers as well as all positive integers,
there is a prime number greater than any
given prime number.
However, in S1 : {1, 2, 3, .....100} ? is
false since for prime number 97 ? S1 there
exists no prime number in the set which is
greater.
So correct answer is C.
46.Ans. A
Sol. SDT for inserting type information in the
symbol table
D ? TL {L.idtype = T.stype}
T ? int {T.stype = int}
T ? float {T.stype = float}
L ? L1, id {L1.itype = L.itype}
addtype(id.entry, L.itype)
L ? id addtype(id.entry, L.itype)
47. Ans. C
Answer is O(n^2)
48.Ans. C
Sol. If no two edges of G have same weight
surely G will have unique spanning tree is
true.
So I is true
Also if, for every cut of G, there is a
unique minimum weight edge crossing the
cut then G will have unique spanning tree is
also true. So II is true
[Note: The converse of II is not true, but
that is not relevant to this question]
So both I and II are true.
Option (d) is correct.
49.Ans. A
50.Ans. A
7
51.Ans. (2)
Let?s assume , Z = 2
Average waiting time (WT)
Hence, Z = 2
52.Ans. (4.0 to 4.1)
53.Ans. 5
Sol.
Total number of items in the set GOTO
(I0, ? ) is 5.
54.Ans. (12)
Sol. Product of eigenvalues is same as the
determinant of a matrix.
55.Ans. (160)
Sol. Total time to transfer a cache block = 1
+ 3 + 8 = 12 cycles
8 W _____________ 12 cycles
8 ? 4 bytes ________________ 12
cycles
? B _____________ 1 sec
56.Ans. 4.25
No. of pairs with path length 0=8.0=8.
No. of pairs with path length 1=0.1=0.
No. of pairs with path length 2=8.2=8.
No. of pairs with path length 3=0.3=0.
No. of pairs with path length 4=16.4=16.
No. of pairs with path length 5=0.5=0.
No. of pairs with path length 6=32.6=32.
Total number of possible pairs
=8?8=64=8?8=64
So, expected path length,E(x),
=0?864+2?864+4?1664+6?3264=27264
=4.25
57.Ans. (0.8)
Sol. It is given that, Polynomial 3x
2
+ 6xY +
3Y + 6 has only real roots
b
2
? 4ax ? 0
(6Y)
2
? 4(3) (3Y+ 6) ? 0
Y
2
? Y + 2 ? 0
Y ? (??, ? 1] ? [2, ?)
? Y ? [2, 6)
Since y is uniformly distributed in (1, 6)
Probability distributed function,
58.Ans. (120)
8
Sol. The DFA for accepting L will have 5! =
120 states, since we need one state for
every possible permutation function on 5
elements. The starting state will be ?id?
state, named as and from there
n! arrows will go the n! states each named
with a distinct permutation of the set {1, 2,
3, 4, 5}. Since composition of permutation
function is closed every arrow has to go to
some permutation and hence some state.
Since the language only has those
strings where ?(x) = id only the starting
state (?id? state) will be the final state.
Sample machine with only 2 states is shown
below
59.Ans. (3)
Sol. 3 switches of ethernet are required to
connect 15 computers.
Hence, 3 is correct answer.
60.Ans. (3)
Sol. f = ?m(0, 2, 5, 7, 8, 10, 13, 15)
f = ?M(1, 3, 4, 6, 9, 11, 12, 14)
.
61.Ans. (5)
Sol.
Total 5 different student names all 5
group records in result.(In where condition
no condition over Roll_no so query produces
all groups.)
62.Ans. (5)
63.Ans. (10)
64.Ans. (97)
Sol. n = p ? q = 3007
?(n) = (p ? 1) (q ? 1) = 2880
By RSA algorithm, n = 31 ? 97 in which 97
is prime factor which greater than 50.
65.Ans. (1)
Sol.
?(I)
?(II)
one record in result.
FirstRanker.com - FirstRanker's Choice
This post was last modified on 18 December 2019