Download GATE (Graduate Aptitude Test in Engineering) GATE CS 2019 Question Paper With Solution And Answer Key
2
1. The expenditure on the project _________
as follows: equipment Rs.20 lakhs, salaries
Rs.12 lakhs, and contingency Rs.3 lakhs.
A. break down B. break
C. breaks down D. breaks
2. The search engine?s business model
___________ around the fulcrum of trust.
A. revolves B. plays
C. sinks D. bursts
3. Two cars start at the same time from the
same location and go in the same direction.
The speed of the first car is 50 km/h and the
speed of the second car is 60 km/h. The
number of hours it takes for the distance
between the two cars to be 20 km is
____________.
A. 1 B. 2
C. 3 D. 6
4. Ten friends planned to share equally the
cost of buying a gift for their teacher. When
two of them decided not to contribute, each
of the other friends had to pay Rs 150 more.
The cost of the gift was Rs. ___________.
A. 666 B. 3000
C. 6000 D. 12000
5. A court is to a judge as ___________ is to
a teacher.
A. a student B. a punishment
C. a syllabus D. a school
Q. 6 ? Q. 10 carry two marks each.
6. The police arrested four criminals ? P, Q, R
and S. The criminals knew each other. They
made the following statements:
P says ?Q committed the crime.?
Q says ?S committed the crime.?
R says ?I did not do it.?
S says ?What Q said about me is false.?
Assume only one of the arrested four
committed the crime and only one of the
statements made above is true. Who
committed the crime?
A. P B. R
C. S D. Q
7. In the given diagram, teachers are
represented in the triangle, researchers in
the circle and administrators in the
rectangle. Out of the total number of the
people, the percentage of administrators
shall be in the range of ___________.
A. 0 to 15 B. 16 to 30
C. 31 to 45 D. 46 to 60
8. ?A recent High Court judgement has sought
to dispel the idea of begging as a disease ?
which leads to its stigmatization and
criminalization ? and to regard it as a
symptom. The underlying disease is the
failure of the state to protect citizens who
fall through the social security net.?
Which one of the following statements can
be inferred from the given passage?
A. Beggars are lazy people who beg
because they are unwilling to work
B. Beggars are created because of the lack
of social welfare schemes
C. Begging is an offence that has to be
dealt with firmly
D. Begging has to be banned because it
adversely affects the welfare of the
state
9. In a college, there are three student clubs.
Sixty students are only in the Drama club,
80 students are only in the Dance club, 30
students are only in the Maths club, 40
students are in both Drama and Dance
clubs, 12 students are in both Dance and
Maths clubs, 7 students are in both Drama
and Maths clubs, and 2 students are in all
the clubs. If 75% of the students in the
college are not in any of these clubs, then
the total number of students in the college
is ___________.
A. 1000 B. 975
C. 900 D. 225
10. Three of the five students allocated to a
hostel put in special requests to the warden.
Given the floor plan of the vacant rooms,
select the allocation plan that will
accommodate all their requests.
Request by X: Due to pollen allergy, I want
to avoid a wing next to the garden.
FirstRanker.com - FirstRanker's Choice
2
1. The expenditure on the project _________
as follows: equipment Rs.20 lakhs, salaries
Rs.12 lakhs, and contingency Rs.3 lakhs.
A. break down B. break
C. breaks down D. breaks
2. The search engine?s business model
___________ around the fulcrum of trust.
A. revolves B. plays
C. sinks D. bursts
3. Two cars start at the same time from the
same location and go in the same direction.
The speed of the first car is 50 km/h and the
speed of the second car is 60 km/h. The
number of hours it takes for the distance
between the two cars to be 20 km is
____________.
A. 1 B. 2
C. 3 D. 6
4. Ten friends planned to share equally the
cost of buying a gift for their teacher. When
two of them decided not to contribute, each
of the other friends had to pay Rs 150 more.
The cost of the gift was Rs. ___________.
A. 666 B. 3000
C. 6000 D. 12000
5. A court is to a judge as ___________ is to
a teacher.
A. a student B. a punishment
C. a syllabus D. a school
Q. 6 ? Q. 10 carry two marks each.
6. The police arrested four criminals ? P, Q, R
and S. The criminals knew each other. They
made the following statements:
P says ?Q committed the crime.?
Q says ?S committed the crime.?
R says ?I did not do it.?
S says ?What Q said about me is false.?
Assume only one of the arrested four
committed the crime and only one of the
statements made above is true. Who
committed the crime?
A. P B. R
C. S D. Q
7. In the given diagram, teachers are
represented in the triangle, researchers in
the circle and administrators in the
rectangle. Out of the total number of the
people, the percentage of administrators
shall be in the range of ___________.
A. 0 to 15 B. 16 to 30
C. 31 to 45 D. 46 to 60
8. ?A recent High Court judgement has sought
to dispel the idea of begging as a disease ?
which leads to its stigmatization and
criminalization ? and to regard it as a
symptom. The underlying disease is the
failure of the state to protect citizens who
fall through the social security net.?
Which one of the following statements can
be inferred from the given passage?
A. Beggars are lazy people who beg
because they are unwilling to work
B. Beggars are created because of the lack
of social welfare schemes
C. Begging is an offence that has to be
dealt with firmly
D. Begging has to be banned because it
adversely affects the welfare of the
state
9. In a college, there are three student clubs.
Sixty students are only in the Drama club,
80 students are only in the Dance club, 30
students are only in the Maths club, 40
students are in both Drama and Dance
clubs, 12 students are in both Dance and
Maths clubs, 7 students are in both Drama
and Maths clubs, and 2 students are in all
the clubs. If 75% of the students in the
college are not in any of these clubs, then
the total number of students in the college
is ___________.
A. 1000 B. 975
C. 900 D. 225
10. Three of the five students allocated to a
hostel put in special requests to the warden.
Given the floor plan of the vacant rooms,
select the allocation plan that will
accommodate all their requests.
Request by X: Due to pollen allergy, I want
to avoid a wing next to the garden.
3
Request by Y: I want to live as far from the
washrooms as possible, since I am very
sensitive to smell.
Request by Z: I believe in Vaastu and so
want to stay in the South-west wing.
The shaded rooms are already occupied. WR
is washroom.
A.
B.
C.
D.
11. A certain processor uses a fully associative
cache of size 16 kB. The cache block size is
16 bytes. Assume that the main memory is
byte addressable and uses a 32-bit address.
How many bits are required for the Tag and
the Index fields respectively in the
addresses generated by the processor?
A. 24 bits and 0 bits
B. 28 bits and 4 bits
C. 24 bits and 4 bits
D. 28 bits and 0 bits
12. The chip select logic for a certain DRAM chip
in a memory system design is shown below.
Assume that the memory system has 16
address lines denoted by A15 to A0. What is
the range of addresses (in hexadecimal) of
the memory system that can get enabled by
the chip select (CS) signal?
A. C800 to CFFF B. CA00 to CAFF
C. C800 to C8FF D. DA00 to DFFF
13. Which one of the following kinds of
derivation is used by LR parsers?
A. Leftmost
B. Leftmost in reverse
C. Rightmost
D. Rightmost in reverse
14. In 16-bit 2?s complement representation, the
decimal number ?28 is:
A. 1111 1111 0001 1100
B. 0000 0000 1110 0100
C. 1111 1111 1110 0100
D. 1000 0000 1110 0100
15. Let U = {1,2,?,?? }. Let ?? ={(?? , ?? )| ?? ? ?? , ?? ?
?? }. Consider the following two statements
on |?? |.
I. |?? | = ?? 2
?? ?1
II.
Which of the above statements is/are TRUE?
A. Only I B. Only II
C. Both I and II D. Neither I nor II
16. Which one of the following is NOT a valid
identity?
A. (x ? y) ? z = x ? (y ? z)
FirstRanker.com - FirstRanker's Choice
2
1. The expenditure on the project _________
as follows: equipment Rs.20 lakhs, salaries
Rs.12 lakhs, and contingency Rs.3 lakhs.
A. break down B. break
C. breaks down D. breaks
2. The search engine?s business model
___________ around the fulcrum of trust.
A. revolves B. plays
C. sinks D. bursts
3. Two cars start at the same time from the
same location and go in the same direction.
The speed of the first car is 50 km/h and the
speed of the second car is 60 km/h. The
number of hours it takes for the distance
between the two cars to be 20 km is
____________.
A. 1 B. 2
C. 3 D. 6
4. Ten friends planned to share equally the
cost of buying a gift for their teacher. When
two of them decided not to contribute, each
of the other friends had to pay Rs 150 more.
The cost of the gift was Rs. ___________.
A. 666 B. 3000
C. 6000 D. 12000
5. A court is to a judge as ___________ is to
a teacher.
A. a student B. a punishment
C. a syllabus D. a school
Q. 6 ? Q. 10 carry two marks each.
6. The police arrested four criminals ? P, Q, R
and S. The criminals knew each other. They
made the following statements:
P says ?Q committed the crime.?
Q says ?S committed the crime.?
R says ?I did not do it.?
S says ?What Q said about me is false.?
Assume only one of the arrested four
committed the crime and only one of the
statements made above is true. Who
committed the crime?
A. P B. R
C. S D. Q
7. In the given diagram, teachers are
represented in the triangle, researchers in
the circle and administrators in the
rectangle. Out of the total number of the
people, the percentage of administrators
shall be in the range of ___________.
A. 0 to 15 B. 16 to 30
C. 31 to 45 D. 46 to 60
8. ?A recent High Court judgement has sought
to dispel the idea of begging as a disease ?
which leads to its stigmatization and
criminalization ? and to regard it as a
symptom. The underlying disease is the
failure of the state to protect citizens who
fall through the social security net.?
Which one of the following statements can
be inferred from the given passage?
A. Beggars are lazy people who beg
because they are unwilling to work
B. Beggars are created because of the lack
of social welfare schemes
C. Begging is an offence that has to be
dealt with firmly
D. Begging has to be banned because it
adversely affects the welfare of the
state
9. In a college, there are three student clubs.
Sixty students are only in the Drama club,
80 students are only in the Dance club, 30
students are only in the Maths club, 40
students are in both Drama and Dance
clubs, 12 students are in both Dance and
Maths clubs, 7 students are in both Drama
and Maths clubs, and 2 students are in all
the clubs. If 75% of the students in the
college are not in any of these clubs, then
the total number of students in the college
is ___________.
A. 1000 B. 975
C. 900 D. 225
10. Three of the five students allocated to a
hostel put in special requests to the warden.
Given the floor plan of the vacant rooms,
select the allocation plan that will
accommodate all their requests.
Request by X: Due to pollen allergy, I want
to avoid a wing next to the garden.
3
Request by Y: I want to live as far from the
washrooms as possible, since I am very
sensitive to smell.
Request by Z: I believe in Vaastu and so
want to stay in the South-west wing.
The shaded rooms are already occupied. WR
is washroom.
A.
B.
C.
D.
11. A certain processor uses a fully associative
cache of size 16 kB. The cache block size is
16 bytes. Assume that the main memory is
byte addressable and uses a 32-bit address.
How many bits are required for the Tag and
the Index fields respectively in the
addresses generated by the processor?
A. 24 bits and 0 bits
B. 28 bits and 4 bits
C. 24 bits and 4 bits
D. 28 bits and 0 bits
12. The chip select logic for a certain DRAM chip
in a memory system design is shown below.
Assume that the memory system has 16
address lines denoted by A15 to A0. What is
the range of addresses (in hexadecimal) of
the memory system that can get enabled by
the chip select (CS) signal?
A. C800 to CFFF B. CA00 to CAFF
C. C800 to C8FF D. DA00 to DFFF
13. Which one of the following kinds of
derivation is used by LR parsers?
A. Leftmost
B. Leftmost in reverse
C. Rightmost
D. Rightmost in reverse
14. In 16-bit 2?s complement representation, the
decimal number ?28 is:
A. 1111 1111 0001 1100
B. 0000 0000 1110 0100
C. 1111 1111 1110 0100
D. 1000 0000 1110 0100
15. Let U = {1,2,?,?? }. Let ?? ={(?? , ?? )| ?? ? ?? , ?? ?
?? }. Consider the following two statements
on |?? |.
I. |?? | = ?? 2
?? ?1
II.
Which of the above statements is/are TRUE?
A. Only I B. Only II
C. Both I and II D. Neither I nor II
16. Which one of the following is NOT a valid
identity?
A. (x ? y) ? z = x ? (y ? z)
4
B. (x + y) ? z = x ? (y + z)
C. x ? y = x + y, if xy = 0
D. x ? y = (xy + x?y?)?
17. If ?? is a regular language over ? = {?? ,},
which one of the following languages is NOT
regular?
A. ?? ? ?? ?? = {???? | ?? ??? , ?? ?? ? ?? }
B. {????
?? | ?? ? ?? }
C. Prefix (?? ) = {?? ? ?? ?
|??? ? ?? ? such that ????
? ?? }
D. Suffix (?? ) = {?? ? ?? ?
|??? ? ?? ? such that ????
? ?? }
18. Consider Z = X ? Y, where X, Y and Z are all
in sign-magnitude form. X and Y are each
represented in ?? bits. To avoid overflow, the
representation of Z would require a
minimum of:
A. n bits B. n - 1 bits
C. n + 1 bits D. n + 2 bits
19. Let X be a square matrix. Consider the
following two statements on X.
I. X is invertible.
II. Determinant of X is non-zero.
Which one of the following is TRUE?
A. I implies II; II does not imply I.
B. II implies I; I does not imply II.
C. I does not imply II; II does not imply I.
D. I and II are equivalent statements.
20. Let G be an arbitrary group. Consider the
following relations on G:
R1: ??? ,b ? ?? , ?? ?? 1 ?? if and only if ??? ? ?? such
that a = g
-1
bg
R2: ??? ,b ? ?? , ?? ?? 2?? if and only if a = b
-1
Which of the above is/are equivalence
relation/relations?
A. R1 and R2
B. R1 only
C. R2 only
D. Neither R1 and R2
21. Consider the following two statements
about database transaction schedules:
I. Strict two-phase locking protocol
generates conflict serializable schedules
that are also recoverable.
II. Timestamp-ordering concurrency
control protocol with Thomas? Write Rule
can generate view serializable schedules
that are not conflict serializable.
Which of the above statements is/are TRUE?
A. I only B. II only
C. Both I and II D. Neither I nor II
22. Let G be an undirected complete graph on ??
vertices, where n > 2. Then, the number of
different Hamiltonian cycles in G is equal to
A. n! B. (n ? 1)!
C. 1 D.
23. Compute
A. 1
B. 53/12
C. 108/7
D. Limit does not exist
24. Which one of the following statements is
NOT correct about the B+ tree data
structure used for creating an index of a
relational database table?
A. B+ Tree is a height-balanced tree
B. Non-leaf nodes have pointers to data
records
C. Key values in each node are kept in
sorted order
D. Each leaf node has a pointer to the next
leaf node
25. For ? = {a, b}, let us consider the regular
language L = {x |x = a
2+3k
or x = b
10 + 12k
, k
? 0}. Which one of the following can be a
pumping length (the constant guaranteed by the
pumping lemma) for L?
A. 3 B. 5
C. 9 D. 24
26. Which of the following protocol pairs can be
used to send and retrieve e-mails (in that
order)?
A. IMAP, POP3 B. SMTP, POP3
C. SMTP, MIME D. IMAP, SMTP
27. The following C program is executed on a
Unix/Linux system:
#include
int main()
{
int i;
for (i=0; i<10; i++)
if (i%2 == 0) fork();
return 0;
}
The total number of child processes created
is ________.
28. Consider the following C program:
#include
FirstRanker.com - FirstRanker's Choice
2
1. The expenditure on the project _________
as follows: equipment Rs.20 lakhs, salaries
Rs.12 lakhs, and contingency Rs.3 lakhs.
A. break down B. break
C. breaks down D. breaks
2. The search engine?s business model
___________ around the fulcrum of trust.
A. revolves B. plays
C. sinks D. bursts
3. Two cars start at the same time from the
same location and go in the same direction.
The speed of the first car is 50 km/h and the
speed of the second car is 60 km/h. The
number of hours it takes for the distance
between the two cars to be 20 km is
____________.
A. 1 B. 2
C. 3 D. 6
4. Ten friends planned to share equally the
cost of buying a gift for their teacher. When
two of them decided not to contribute, each
of the other friends had to pay Rs 150 more.
The cost of the gift was Rs. ___________.
A. 666 B. 3000
C. 6000 D. 12000
5. A court is to a judge as ___________ is to
a teacher.
A. a student B. a punishment
C. a syllabus D. a school
Q. 6 ? Q. 10 carry two marks each.
6. The police arrested four criminals ? P, Q, R
and S. The criminals knew each other. They
made the following statements:
P says ?Q committed the crime.?
Q says ?S committed the crime.?
R says ?I did not do it.?
S says ?What Q said about me is false.?
Assume only one of the arrested four
committed the crime and only one of the
statements made above is true. Who
committed the crime?
A. P B. R
C. S D. Q
7. In the given diagram, teachers are
represented in the triangle, researchers in
the circle and administrators in the
rectangle. Out of the total number of the
people, the percentage of administrators
shall be in the range of ___________.
A. 0 to 15 B. 16 to 30
C. 31 to 45 D. 46 to 60
8. ?A recent High Court judgement has sought
to dispel the idea of begging as a disease ?
which leads to its stigmatization and
criminalization ? and to regard it as a
symptom. The underlying disease is the
failure of the state to protect citizens who
fall through the social security net.?
Which one of the following statements can
be inferred from the given passage?
A. Beggars are lazy people who beg
because they are unwilling to work
B. Beggars are created because of the lack
of social welfare schemes
C. Begging is an offence that has to be
dealt with firmly
D. Begging has to be banned because it
adversely affects the welfare of the
state
9. In a college, there are three student clubs.
Sixty students are only in the Drama club,
80 students are only in the Dance club, 30
students are only in the Maths club, 40
students are in both Drama and Dance
clubs, 12 students are in both Dance and
Maths clubs, 7 students are in both Drama
and Maths clubs, and 2 students are in all
the clubs. If 75% of the students in the
college are not in any of these clubs, then
the total number of students in the college
is ___________.
A. 1000 B. 975
C. 900 D. 225
10. Three of the five students allocated to a
hostel put in special requests to the warden.
Given the floor plan of the vacant rooms,
select the allocation plan that will
accommodate all their requests.
Request by X: Due to pollen allergy, I want
to avoid a wing next to the garden.
3
Request by Y: I want to live as far from the
washrooms as possible, since I am very
sensitive to smell.
Request by Z: I believe in Vaastu and so
want to stay in the South-west wing.
The shaded rooms are already occupied. WR
is washroom.
A.
B.
C.
D.
11. A certain processor uses a fully associative
cache of size 16 kB. The cache block size is
16 bytes. Assume that the main memory is
byte addressable and uses a 32-bit address.
How many bits are required for the Tag and
the Index fields respectively in the
addresses generated by the processor?
A. 24 bits and 0 bits
B. 28 bits and 4 bits
C. 24 bits and 4 bits
D. 28 bits and 0 bits
12. The chip select logic for a certain DRAM chip
in a memory system design is shown below.
Assume that the memory system has 16
address lines denoted by A15 to A0. What is
the range of addresses (in hexadecimal) of
the memory system that can get enabled by
the chip select (CS) signal?
A. C800 to CFFF B. CA00 to CAFF
C. C800 to C8FF D. DA00 to DFFF
13. Which one of the following kinds of
derivation is used by LR parsers?
A. Leftmost
B. Leftmost in reverse
C. Rightmost
D. Rightmost in reverse
14. In 16-bit 2?s complement representation, the
decimal number ?28 is:
A. 1111 1111 0001 1100
B. 0000 0000 1110 0100
C. 1111 1111 1110 0100
D. 1000 0000 1110 0100
15. Let U = {1,2,?,?? }. Let ?? ={(?? , ?? )| ?? ? ?? , ?? ?
?? }. Consider the following two statements
on |?? |.
I. |?? | = ?? 2
?? ?1
II.
Which of the above statements is/are TRUE?
A. Only I B. Only II
C. Both I and II D. Neither I nor II
16. Which one of the following is NOT a valid
identity?
A. (x ? y) ? z = x ? (y ? z)
4
B. (x + y) ? z = x ? (y + z)
C. x ? y = x + y, if xy = 0
D. x ? y = (xy + x?y?)?
17. If ?? is a regular language over ? = {?? ,},
which one of the following languages is NOT
regular?
A. ?? ? ?? ?? = {???? | ?? ??? , ?? ?? ? ?? }
B. {????
?? | ?? ? ?? }
C. Prefix (?? ) = {?? ? ?? ?
|??? ? ?? ? such that ????
? ?? }
D. Suffix (?? ) = {?? ? ?? ?
|??? ? ?? ? such that ????
? ?? }
18. Consider Z = X ? Y, where X, Y and Z are all
in sign-magnitude form. X and Y are each
represented in ?? bits. To avoid overflow, the
representation of Z would require a
minimum of:
A. n bits B. n - 1 bits
C. n + 1 bits D. n + 2 bits
19. Let X be a square matrix. Consider the
following two statements on X.
I. X is invertible.
II. Determinant of X is non-zero.
Which one of the following is TRUE?
A. I implies II; II does not imply I.
B. II implies I; I does not imply II.
C. I does not imply II; II does not imply I.
D. I and II are equivalent statements.
20. Let G be an arbitrary group. Consider the
following relations on G:
R1: ??? ,b ? ?? , ?? ?? 1 ?? if and only if ??? ? ?? such
that a = g
-1
bg
R2: ??? ,b ? ?? , ?? ?? 2?? if and only if a = b
-1
Which of the above is/are equivalence
relation/relations?
A. R1 and R2
B. R1 only
C. R2 only
D. Neither R1 and R2
21. Consider the following two statements
about database transaction schedules:
I. Strict two-phase locking protocol
generates conflict serializable schedules
that are also recoverable.
II. Timestamp-ordering concurrency
control protocol with Thomas? Write Rule
can generate view serializable schedules
that are not conflict serializable.
Which of the above statements is/are TRUE?
A. I only B. II only
C. Both I and II D. Neither I nor II
22. Let G be an undirected complete graph on ??
vertices, where n > 2. Then, the number of
different Hamiltonian cycles in G is equal to
A. n! B. (n ? 1)!
C. 1 D.
23. Compute
A. 1
B. 53/12
C. 108/7
D. Limit does not exist
24. Which one of the following statements is
NOT correct about the B+ tree data
structure used for creating an index of a
relational database table?
A. B+ Tree is a height-balanced tree
B. Non-leaf nodes have pointers to data
records
C. Key values in each node are kept in
sorted order
D. Each leaf node has a pointer to the next
leaf node
25. For ? = {a, b}, let us consider the regular
language L = {x |x = a
2+3k
or x = b
10 + 12k
, k
? 0}. Which one of the following can be a
pumping length (the constant guaranteed by the
pumping lemma) for L?
A. 3 B. 5
C. 9 D. 24
26. Which of the following protocol pairs can be
used to send and retrieve e-mails (in that
order)?
A. IMAP, POP3 B. SMTP, POP3
C. SMTP, MIME D. IMAP, SMTP
27. The following C program is executed on a
Unix/Linux system:
#include
int main()
{
int i;
for (i=0; i<10; i++)
if (i%2 == 0) fork();
return 0;
}
The total number of child processes created
is ________.
28. Consider the following C program:
#include
5
int jumble(int x, int y){
x=2*x+y;
return x;
}
int main(){
int x=2, y=5;
y=jumble(y,x);
x=jumble(y,x);
printf(?%d \n?, x);
return 0;
}
The value printed by the program is
_______.
29. Consider the grammar given below:
S ? Aa
A ? BD
B ? b | ?
D ? d | ?
Let a, b, d, and $ be indexed as follows:
a b d $
3 2 1 0
Compute the FOLLOW set of the non-
terminal B and write the index values for the
symbols in the FOLLOW set in the
descending order. (For example, if the
FOLLOW set is {a, b, d, $}, then the answer
should be 3210)
Answer: ________.
30. An array of 25 distinct elements is to be
sorted using quicksort. Assume that the
pivot element is chosen uniformly at
random. The probability that the pivot
element gets placed in the worst possible
location in the first round of partitioning
(rounded off to 2 decimal places) is
________.
31. The value of 3^51 mod 5 is ________.
32. Two numbers are chosen independently and
uniformly at random from the set
{1, 2,...,13}. The probability (rounded off to
3 decimal places) that their 4-bit (unsigned)
binary representations have the same most
significant bit is ___________.
33. Consider three concurrent processes P1, P2
and P3 as shown below, which access a
shared variable D that has been initialized
to 100.
The processes are executed on a
uniprocessor system running a time-shared
operating system. If the minimum and
maximum possible values of D after the
three processes have completed execution
are X and Y respectively, then the value of
Y ? X is _____________.
34. Consider the following C program:
#include
int main(){
int arr[]={1,2,3,4,5,6,7,8,9,0,1,2,5},
*ip=arr+4;
printf(?%d\n?, ip[1]);
return 0;
}
The number that will be displayed on
execution of the program is ___________ .
35. Consider a sequence of 14 elements: A = [?5,
?10, 6, 3, ?1, ?2, 13, 4, ?9, ?1, 4, 12, ?3, 0].
The subsequence sum
Determine the maximum of S(i, j), where 0 ? i ?
j < 14. Divide and conquer approach may be
used.)
Answer: ________.
36. Consider the following C function.
void convert(int n){
if(n<0)
printf(?%d?,n);
else {
convert(n/2);
printf(?%d?,n%2);
}
}
Which one of the following will happen when
the function convert is called with any
positive integer n as argument?
A. It will print the binary representation of
n and terminate
B. It will print the binary representation of
n in the reverse order and terminate
C. It will print the binary representation of
n but will not terminate
D. It will not print anything and will not
terminate
FirstRanker.com - FirstRanker's Choice
2
1. The expenditure on the project _________
as follows: equipment Rs.20 lakhs, salaries
Rs.12 lakhs, and contingency Rs.3 lakhs.
A. break down B. break
C. breaks down D. breaks
2. The search engine?s business model
___________ around the fulcrum of trust.
A. revolves B. plays
C. sinks D. bursts
3. Two cars start at the same time from the
same location and go in the same direction.
The speed of the first car is 50 km/h and the
speed of the second car is 60 km/h. The
number of hours it takes for the distance
between the two cars to be 20 km is
____________.
A. 1 B. 2
C. 3 D. 6
4. Ten friends planned to share equally the
cost of buying a gift for their teacher. When
two of them decided not to contribute, each
of the other friends had to pay Rs 150 more.
The cost of the gift was Rs. ___________.
A. 666 B. 3000
C. 6000 D. 12000
5. A court is to a judge as ___________ is to
a teacher.
A. a student B. a punishment
C. a syllabus D. a school
Q. 6 ? Q. 10 carry two marks each.
6. The police arrested four criminals ? P, Q, R
and S. The criminals knew each other. They
made the following statements:
P says ?Q committed the crime.?
Q says ?S committed the crime.?
R says ?I did not do it.?
S says ?What Q said about me is false.?
Assume only one of the arrested four
committed the crime and only one of the
statements made above is true. Who
committed the crime?
A. P B. R
C. S D. Q
7. In the given diagram, teachers are
represented in the triangle, researchers in
the circle and administrators in the
rectangle. Out of the total number of the
people, the percentage of administrators
shall be in the range of ___________.
A. 0 to 15 B. 16 to 30
C. 31 to 45 D. 46 to 60
8. ?A recent High Court judgement has sought
to dispel the idea of begging as a disease ?
which leads to its stigmatization and
criminalization ? and to regard it as a
symptom. The underlying disease is the
failure of the state to protect citizens who
fall through the social security net.?
Which one of the following statements can
be inferred from the given passage?
A. Beggars are lazy people who beg
because they are unwilling to work
B. Beggars are created because of the lack
of social welfare schemes
C. Begging is an offence that has to be
dealt with firmly
D. Begging has to be banned because it
adversely affects the welfare of the
state
9. In a college, there are three student clubs.
Sixty students are only in the Drama club,
80 students are only in the Dance club, 30
students are only in the Maths club, 40
students are in both Drama and Dance
clubs, 12 students are in both Dance and
Maths clubs, 7 students are in both Drama
and Maths clubs, and 2 students are in all
the clubs. If 75% of the students in the
college are not in any of these clubs, then
the total number of students in the college
is ___________.
A. 1000 B. 975
C. 900 D. 225
10. Three of the five students allocated to a
hostel put in special requests to the warden.
Given the floor plan of the vacant rooms,
select the allocation plan that will
accommodate all their requests.
Request by X: Due to pollen allergy, I want
to avoid a wing next to the garden.
3
Request by Y: I want to live as far from the
washrooms as possible, since I am very
sensitive to smell.
Request by Z: I believe in Vaastu and so
want to stay in the South-west wing.
The shaded rooms are already occupied. WR
is washroom.
A.
B.
C.
D.
11. A certain processor uses a fully associative
cache of size 16 kB. The cache block size is
16 bytes. Assume that the main memory is
byte addressable and uses a 32-bit address.
How many bits are required for the Tag and
the Index fields respectively in the
addresses generated by the processor?
A. 24 bits and 0 bits
B. 28 bits and 4 bits
C. 24 bits and 4 bits
D. 28 bits and 0 bits
12. The chip select logic for a certain DRAM chip
in a memory system design is shown below.
Assume that the memory system has 16
address lines denoted by A15 to A0. What is
the range of addresses (in hexadecimal) of
the memory system that can get enabled by
the chip select (CS) signal?
A. C800 to CFFF B. CA00 to CAFF
C. C800 to C8FF D. DA00 to DFFF
13. Which one of the following kinds of
derivation is used by LR parsers?
A. Leftmost
B. Leftmost in reverse
C. Rightmost
D. Rightmost in reverse
14. In 16-bit 2?s complement representation, the
decimal number ?28 is:
A. 1111 1111 0001 1100
B. 0000 0000 1110 0100
C. 1111 1111 1110 0100
D. 1000 0000 1110 0100
15. Let U = {1,2,?,?? }. Let ?? ={(?? , ?? )| ?? ? ?? , ?? ?
?? }. Consider the following two statements
on |?? |.
I. |?? | = ?? 2
?? ?1
II.
Which of the above statements is/are TRUE?
A. Only I B. Only II
C. Both I and II D. Neither I nor II
16. Which one of the following is NOT a valid
identity?
A. (x ? y) ? z = x ? (y ? z)
4
B. (x + y) ? z = x ? (y + z)
C. x ? y = x + y, if xy = 0
D. x ? y = (xy + x?y?)?
17. If ?? is a regular language over ? = {?? ,},
which one of the following languages is NOT
regular?
A. ?? ? ?? ?? = {???? | ?? ??? , ?? ?? ? ?? }
B. {????
?? | ?? ? ?? }
C. Prefix (?? ) = {?? ? ?? ?
|??? ? ?? ? such that ????
? ?? }
D. Suffix (?? ) = {?? ? ?? ?
|??? ? ?? ? such that ????
? ?? }
18. Consider Z = X ? Y, where X, Y and Z are all
in sign-magnitude form. X and Y are each
represented in ?? bits. To avoid overflow, the
representation of Z would require a
minimum of:
A. n bits B. n - 1 bits
C. n + 1 bits D. n + 2 bits
19. Let X be a square matrix. Consider the
following two statements on X.
I. X is invertible.
II. Determinant of X is non-zero.
Which one of the following is TRUE?
A. I implies II; II does not imply I.
B. II implies I; I does not imply II.
C. I does not imply II; II does not imply I.
D. I and II are equivalent statements.
20. Let G be an arbitrary group. Consider the
following relations on G:
R1: ??? ,b ? ?? , ?? ?? 1 ?? if and only if ??? ? ?? such
that a = g
-1
bg
R2: ??? ,b ? ?? , ?? ?? 2?? if and only if a = b
-1
Which of the above is/are equivalence
relation/relations?
A. R1 and R2
B. R1 only
C. R2 only
D. Neither R1 and R2
21. Consider the following two statements
about database transaction schedules:
I. Strict two-phase locking protocol
generates conflict serializable schedules
that are also recoverable.
II. Timestamp-ordering concurrency
control protocol with Thomas? Write Rule
can generate view serializable schedules
that are not conflict serializable.
Which of the above statements is/are TRUE?
A. I only B. II only
C. Both I and II D. Neither I nor II
22. Let G be an undirected complete graph on ??
vertices, where n > 2. Then, the number of
different Hamiltonian cycles in G is equal to
A. n! B. (n ? 1)!
C. 1 D.
23. Compute
A. 1
B. 53/12
C. 108/7
D. Limit does not exist
24. Which one of the following statements is
NOT correct about the B+ tree data
structure used for creating an index of a
relational database table?
A. B+ Tree is a height-balanced tree
B. Non-leaf nodes have pointers to data
records
C. Key values in each node are kept in
sorted order
D. Each leaf node has a pointer to the next
leaf node
25. For ? = {a, b}, let us consider the regular
language L = {x |x = a
2+3k
or x = b
10 + 12k
, k
? 0}. Which one of the following can be a
pumping length (the constant guaranteed by the
pumping lemma) for L?
A. 3 B. 5
C. 9 D. 24
26. Which of the following protocol pairs can be
used to send and retrieve e-mails (in that
order)?
A. IMAP, POP3 B. SMTP, POP3
C. SMTP, MIME D. IMAP, SMTP
27. The following C program is executed on a
Unix/Linux system:
#include
int main()
{
int i;
for (i=0; i<10; i++)
if (i%2 == 0) fork();
return 0;
}
The total number of child processes created
is ________.
28. Consider the following C program:
#include
5
int jumble(int x, int y){
x=2*x+y;
return x;
}
int main(){
int x=2, y=5;
y=jumble(y,x);
x=jumble(y,x);
printf(?%d \n?, x);
return 0;
}
The value printed by the program is
_______.
29. Consider the grammar given below:
S ? Aa
A ? BD
B ? b | ?
D ? d | ?
Let a, b, d, and $ be indexed as follows:
a b d $
3 2 1 0
Compute the FOLLOW set of the non-
terminal B and write the index values for the
symbols in the FOLLOW set in the
descending order. (For example, if the
FOLLOW set is {a, b, d, $}, then the answer
should be 3210)
Answer: ________.
30. An array of 25 distinct elements is to be
sorted using quicksort. Assume that the
pivot element is chosen uniformly at
random. The probability that the pivot
element gets placed in the worst possible
location in the first round of partitioning
(rounded off to 2 decimal places) is
________.
31. The value of 3^51 mod 5 is ________.
32. Two numbers are chosen independently and
uniformly at random from the set
{1, 2,...,13}. The probability (rounded off to
3 decimal places) that their 4-bit (unsigned)
binary representations have the same most
significant bit is ___________.
33. Consider three concurrent processes P1, P2
and P3 as shown below, which access a
shared variable D that has been initialized
to 100.
The processes are executed on a
uniprocessor system running a time-shared
operating system. If the minimum and
maximum possible values of D after the
three processes have completed execution
are X and Y respectively, then the value of
Y ? X is _____________.
34. Consider the following C program:
#include
int main(){
int arr[]={1,2,3,4,5,6,7,8,9,0,1,2,5},
*ip=arr+4;
printf(?%d\n?, ip[1]);
return 0;
}
The number that will be displayed on
execution of the program is ___________ .
35. Consider a sequence of 14 elements: A = [?5,
?10, 6, 3, ?1, ?2, 13, 4, ?9, ?1, 4, 12, ?3, 0].
The subsequence sum
Determine the maximum of S(i, j), where 0 ? i ?
j < 14. Divide and conquer approach may be
used.)
Answer: ________.
36. Consider the following C function.
void convert(int n){
if(n<0)
printf(?%d?,n);
else {
convert(n/2);
printf(?%d?,n%2);
}
}
Which one of the following will happen when
the function convert is called with any
positive integer n as argument?
A. It will print the binary representation of
n and terminate
B. It will print the binary representation of
n in the reverse order and terminate
C. It will print the binary representation of
n but will not terminate
D. It will not print anything and will not
terminate
6
37. Consider the following C program:
#include
int r(){
static int num=7;
return num--;
}
int main(){
for (r();r();r())
printf(?%d?,r());
return 0;
}
Which one of the following values will be
displayed on execution of the programs?
A. 41 B. 52
C. 63 D. 630
38. Consider three machines M, N, and P with IP
addresses 100.10.5.2, 100.10.5.5, and
100.10.5.6 respectively. The subnet mask is
set to 255.255.255.252 for all the three
machines. Which one of the following is
true?
A. M, N, and P all belong to the same
subnet
B. Only M and N belong to the same subnet
C. Only N and P belong to the same subnet
D. M, N, and P belong to three different
subnets
39. Suppose that in an IP-over-Ethernet
network, a machine X wishes to find the
MAC address of another machine Y in its
subnet. Which one of the following
techniques can be used for this?
A. X sends an ARP request packet to the
local gateway?s IP address which then
finds the MAC address of Y and sends to
X
B. X sends an ARP request packet to the
local gateway?s MAC address which then
finds the MAC address of Y and sends to
X
C. X sends an ARP request packet with
broadcast MAC address in its local
subnet
D. X sends an ARP request packet with
broadcast IP address in its local subnet
40. Consider three 4-variable functions f1, f2,
and f3, which are expressed in sum-of-
minterms as
f1 = ?(0, 2, 5, 8, 14), f2 = ?(2, 3, 6, 8, 14,
15), f3 = ? (2, 7, 11, 14)
For the following circuit with one AND gate
and one XOR gate, the output function f can
be expressed as:
A. ? (7, 8, 11)
B. ? (2, 7, 8, 11, 14)
C. ? (2, 14)
D. ? (0, 2, 3, 5, 6, 7, 8, 11, 14, 15)
41. Which one of the following languages over ?
= {a, b}is NOT context-free?
A. {ww
R
|w ? {a,b}
*
}
B. {wa
n
b
n
w
R
|w {a, b}
*
, n ? 0}
C. {wa
n
w
R
b
n
|w {a,b}
*
, n ? 0}
D. {anbi |i ? |n, 3n, 5n}, n ? 0}
42. Let the set of functional dependencies F =
{QR ? S, R ? P, S ? Q} hold on a relation
schema X = (PQRS). X is not in BCNF.
Suppose X is decomposed into two schemas
Y and Z, where Y = (PR) and Z = (QRS).
Consider the two statements given below.
I. Both Y and Z are in BCNF
II. Decomposition of X into Y and Z is
dependency preserving and lossless
Which of the above statements is/are
correct?
A. Both I and II B. I only
C. II only D. Neither I nor II
43. Assume that in a certain computer, the
virtual addresses are 64 bits long and the
physical addresses are 48 bits long. The
memory is word addressible. The page size
is 8 kB and the word size is 4 bytes. The
Translation Look-aside Buffer (TLB) in the
address translation path has 128 valid
entries. At most how many distinct virtual
addresses can be translated without any
TLB miss?
A. 16 ? 2
10
B. 256 ? 2
10
C. 4 ? 2
20
D. 8 ? 2
20
44. Consider the following sets:
S1. Set of all recursively enumerable
languages over the alphabet {0,1}
S2. Set of all syntactically valid C programs
S3. Set of all languages over the alphabet
{0,1}
FirstRanker.com - FirstRanker's Choice
2
1. The expenditure on the project _________
as follows: equipment Rs.20 lakhs, salaries
Rs.12 lakhs, and contingency Rs.3 lakhs.
A. break down B. break
C. breaks down D. breaks
2. The search engine?s business model
___________ around the fulcrum of trust.
A. revolves B. plays
C. sinks D. bursts
3. Two cars start at the same time from the
same location and go in the same direction.
The speed of the first car is 50 km/h and the
speed of the second car is 60 km/h. The
number of hours it takes for the distance
between the two cars to be 20 km is
____________.
A. 1 B. 2
C. 3 D. 6
4. Ten friends planned to share equally the
cost of buying a gift for their teacher. When
two of them decided not to contribute, each
of the other friends had to pay Rs 150 more.
The cost of the gift was Rs. ___________.
A. 666 B. 3000
C. 6000 D. 12000
5. A court is to a judge as ___________ is to
a teacher.
A. a student B. a punishment
C. a syllabus D. a school
Q. 6 ? Q. 10 carry two marks each.
6. The police arrested four criminals ? P, Q, R
and S. The criminals knew each other. They
made the following statements:
P says ?Q committed the crime.?
Q says ?S committed the crime.?
R says ?I did not do it.?
S says ?What Q said about me is false.?
Assume only one of the arrested four
committed the crime and only one of the
statements made above is true. Who
committed the crime?
A. P B. R
C. S D. Q
7. In the given diagram, teachers are
represented in the triangle, researchers in
the circle and administrators in the
rectangle. Out of the total number of the
people, the percentage of administrators
shall be in the range of ___________.
A. 0 to 15 B. 16 to 30
C. 31 to 45 D. 46 to 60
8. ?A recent High Court judgement has sought
to dispel the idea of begging as a disease ?
which leads to its stigmatization and
criminalization ? and to regard it as a
symptom. The underlying disease is the
failure of the state to protect citizens who
fall through the social security net.?
Which one of the following statements can
be inferred from the given passage?
A. Beggars are lazy people who beg
because they are unwilling to work
B. Beggars are created because of the lack
of social welfare schemes
C. Begging is an offence that has to be
dealt with firmly
D. Begging has to be banned because it
adversely affects the welfare of the
state
9. In a college, there are three student clubs.
Sixty students are only in the Drama club,
80 students are only in the Dance club, 30
students are only in the Maths club, 40
students are in both Drama and Dance
clubs, 12 students are in both Dance and
Maths clubs, 7 students are in both Drama
and Maths clubs, and 2 students are in all
the clubs. If 75% of the students in the
college are not in any of these clubs, then
the total number of students in the college
is ___________.
A. 1000 B. 975
C. 900 D. 225
10. Three of the five students allocated to a
hostel put in special requests to the warden.
Given the floor plan of the vacant rooms,
select the allocation plan that will
accommodate all their requests.
Request by X: Due to pollen allergy, I want
to avoid a wing next to the garden.
3
Request by Y: I want to live as far from the
washrooms as possible, since I am very
sensitive to smell.
Request by Z: I believe in Vaastu and so
want to stay in the South-west wing.
The shaded rooms are already occupied. WR
is washroom.
A.
B.
C.
D.
11. A certain processor uses a fully associative
cache of size 16 kB. The cache block size is
16 bytes. Assume that the main memory is
byte addressable and uses a 32-bit address.
How many bits are required for the Tag and
the Index fields respectively in the
addresses generated by the processor?
A. 24 bits and 0 bits
B. 28 bits and 4 bits
C. 24 bits and 4 bits
D. 28 bits and 0 bits
12. The chip select logic for a certain DRAM chip
in a memory system design is shown below.
Assume that the memory system has 16
address lines denoted by A15 to A0. What is
the range of addresses (in hexadecimal) of
the memory system that can get enabled by
the chip select (CS) signal?
A. C800 to CFFF B. CA00 to CAFF
C. C800 to C8FF D. DA00 to DFFF
13. Which one of the following kinds of
derivation is used by LR parsers?
A. Leftmost
B. Leftmost in reverse
C. Rightmost
D. Rightmost in reverse
14. In 16-bit 2?s complement representation, the
decimal number ?28 is:
A. 1111 1111 0001 1100
B. 0000 0000 1110 0100
C. 1111 1111 1110 0100
D. 1000 0000 1110 0100
15. Let U = {1,2,?,?? }. Let ?? ={(?? , ?? )| ?? ? ?? , ?? ?
?? }. Consider the following two statements
on |?? |.
I. |?? | = ?? 2
?? ?1
II.
Which of the above statements is/are TRUE?
A. Only I B. Only II
C. Both I and II D. Neither I nor II
16. Which one of the following is NOT a valid
identity?
A. (x ? y) ? z = x ? (y ? z)
4
B. (x + y) ? z = x ? (y + z)
C. x ? y = x + y, if xy = 0
D. x ? y = (xy + x?y?)?
17. If ?? is a regular language over ? = {?? ,},
which one of the following languages is NOT
regular?
A. ?? ? ?? ?? = {???? | ?? ??? , ?? ?? ? ?? }
B. {????
?? | ?? ? ?? }
C. Prefix (?? ) = {?? ? ?? ?
|??? ? ?? ? such that ????
? ?? }
D. Suffix (?? ) = {?? ? ?? ?
|??? ? ?? ? such that ????
? ?? }
18. Consider Z = X ? Y, where X, Y and Z are all
in sign-magnitude form. X and Y are each
represented in ?? bits. To avoid overflow, the
representation of Z would require a
minimum of:
A. n bits B. n - 1 bits
C. n + 1 bits D. n + 2 bits
19. Let X be a square matrix. Consider the
following two statements on X.
I. X is invertible.
II. Determinant of X is non-zero.
Which one of the following is TRUE?
A. I implies II; II does not imply I.
B. II implies I; I does not imply II.
C. I does not imply II; II does not imply I.
D. I and II are equivalent statements.
20. Let G be an arbitrary group. Consider the
following relations on G:
R1: ??? ,b ? ?? , ?? ?? 1 ?? if and only if ??? ? ?? such
that a = g
-1
bg
R2: ??? ,b ? ?? , ?? ?? 2?? if and only if a = b
-1
Which of the above is/are equivalence
relation/relations?
A. R1 and R2
B. R1 only
C. R2 only
D. Neither R1 and R2
21. Consider the following two statements
about database transaction schedules:
I. Strict two-phase locking protocol
generates conflict serializable schedules
that are also recoverable.
II. Timestamp-ordering concurrency
control protocol with Thomas? Write Rule
can generate view serializable schedules
that are not conflict serializable.
Which of the above statements is/are TRUE?
A. I only B. II only
C. Both I and II D. Neither I nor II
22. Let G be an undirected complete graph on ??
vertices, where n > 2. Then, the number of
different Hamiltonian cycles in G is equal to
A. n! B. (n ? 1)!
C. 1 D.
23. Compute
A. 1
B. 53/12
C. 108/7
D. Limit does not exist
24. Which one of the following statements is
NOT correct about the B+ tree data
structure used for creating an index of a
relational database table?
A. B+ Tree is a height-balanced tree
B. Non-leaf nodes have pointers to data
records
C. Key values in each node are kept in
sorted order
D. Each leaf node has a pointer to the next
leaf node
25. For ? = {a, b}, let us consider the regular
language L = {x |x = a
2+3k
or x = b
10 + 12k
, k
? 0}. Which one of the following can be a
pumping length (the constant guaranteed by the
pumping lemma) for L?
A. 3 B. 5
C. 9 D. 24
26. Which of the following protocol pairs can be
used to send and retrieve e-mails (in that
order)?
A. IMAP, POP3 B. SMTP, POP3
C. SMTP, MIME D. IMAP, SMTP
27. The following C program is executed on a
Unix/Linux system:
#include
int main()
{
int i;
for (i=0; i<10; i++)
if (i%2 == 0) fork();
return 0;
}
The total number of child processes created
is ________.
28. Consider the following C program:
#include
5
int jumble(int x, int y){
x=2*x+y;
return x;
}
int main(){
int x=2, y=5;
y=jumble(y,x);
x=jumble(y,x);
printf(?%d \n?, x);
return 0;
}
The value printed by the program is
_______.
29. Consider the grammar given below:
S ? Aa
A ? BD
B ? b | ?
D ? d | ?
Let a, b, d, and $ be indexed as follows:
a b d $
3 2 1 0
Compute the FOLLOW set of the non-
terminal B and write the index values for the
symbols in the FOLLOW set in the
descending order. (For example, if the
FOLLOW set is {a, b, d, $}, then the answer
should be 3210)
Answer: ________.
30. An array of 25 distinct elements is to be
sorted using quicksort. Assume that the
pivot element is chosen uniformly at
random. The probability that the pivot
element gets placed in the worst possible
location in the first round of partitioning
(rounded off to 2 decimal places) is
________.
31. The value of 3^51 mod 5 is ________.
32. Two numbers are chosen independently and
uniformly at random from the set
{1, 2,...,13}. The probability (rounded off to
3 decimal places) that their 4-bit (unsigned)
binary representations have the same most
significant bit is ___________.
33. Consider three concurrent processes P1, P2
and P3 as shown below, which access a
shared variable D that has been initialized
to 100.
The processes are executed on a
uniprocessor system running a time-shared
operating system. If the minimum and
maximum possible values of D after the
three processes have completed execution
are X and Y respectively, then the value of
Y ? X is _____________.
34. Consider the following C program:
#include
int main(){
int arr[]={1,2,3,4,5,6,7,8,9,0,1,2,5},
*ip=arr+4;
printf(?%d\n?, ip[1]);
return 0;
}
The number that will be displayed on
execution of the program is ___________ .
35. Consider a sequence of 14 elements: A = [?5,
?10, 6, 3, ?1, ?2, 13, 4, ?9, ?1, 4, 12, ?3, 0].
The subsequence sum
Determine the maximum of S(i, j), where 0 ? i ?
j < 14. Divide and conquer approach may be
used.)
Answer: ________.
36. Consider the following C function.
void convert(int n){
if(n<0)
printf(?%d?,n);
else {
convert(n/2);
printf(?%d?,n%2);
}
}
Which one of the following will happen when
the function convert is called with any
positive integer n as argument?
A. It will print the binary representation of
n and terminate
B. It will print the binary representation of
n in the reverse order and terminate
C. It will print the binary representation of
n but will not terminate
D. It will not print anything and will not
terminate
6
37. Consider the following C program:
#include
int r(){
static int num=7;
return num--;
}
int main(){
for (r();r();r())
printf(?%d?,r());
return 0;
}
Which one of the following values will be
displayed on execution of the programs?
A. 41 B. 52
C. 63 D. 630
38. Consider three machines M, N, and P with IP
addresses 100.10.5.2, 100.10.5.5, and
100.10.5.6 respectively. The subnet mask is
set to 255.255.255.252 for all the three
machines. Which one of the following is
true?
A. M, N, and P all belong to the same
subnet
B. Only M and N belong to the same subnet
C. Only N and P belong to the same subnet
D. M, N, and P belong to three different
subnets
39. Suppose that in an IP-over-Ethernet
network, a machine X wishes to find the
MAC address of another machine Y in its
subnet. Which one of the following
techniques can be used for this?
A. X sends an ARP request packet to the
local gateway?s IP address which then
finds the MAC address of Y and sends to
X
B. X sends an ARP request packet to the
local gateway?s MAC address which then
finds the MAC address of Y and sends to
X
C. X sends an ARP request packet with
broadcast MAC address in its local
subnet
D. X sends an ARP request packet with
broadcast IP address in its local subnet
40. Consider three 4-variable functions f1, f2,
and f3, which are expressed in sum-of-
minterms as
f1 = ?(0, 2, 5, 8, 14), f2 = ?(2, 3, 6, 8, 14,
15), f3 = ? (2, 7, 11, 14)
For the following circuit with one AND gate
and one XOR gate, the output function f can
be expressed as:
A. ? (7, 8, 11)
B. ? (2, 7, 8, 11, 14)
C. ? (2, 14)
D. ? (0, 2, 3, 5, 6, 7, 8, 11, 14, 15)
41. Which one of the following languages over ?
= {a, b}is NOT context-free?
A. {ww
R
|w ? {a,b}
*
}
B. {wa
n
b
n
w
R
|w {a, b}
*
, n ? 0}
C. {wa
n
w
R
b
n
|w {a,b}
*
, n ? 0}
D. {anbi |i ? |n, 3n, 5n}, n ? 0}
42. Let the set of functional dependencies F =
{QR ? S, R ? P, S ? Q} hold on a relation
schema X = (PQRS). X is not in BCNF.
Suppose X is decomposed into two schemas
Y and Z, where Y = (PR) and Z = (QRS).
Consider the two statements given below.
I. Both Y and Z are in BCNF
II. Decomposition of X into Y and Z is
dependency preserving and lossless
Which of the above statements is/are
correct?
A. Both I and II B. I only
C. II only D. Neither I nor II
43. Assume that in a certain computer, the
virtual addresses are 64 bits long and the
physical addresses are 48 bits long. The
memory is word addressible. The page size
is 8 kB and the word size is 4 bytes. The
Translation Look-aside Buffer (TLB) in the
address translation path has 128 valid
entries. At most how many distinct virtual
addresses can be translated without any
TLB miss?
A. 16 ? 2
10
B. 256 ? 2
10
C. 4 ? 2
20
D. 8 ? 2
20
44. Consider the following sets:
S1. Set of all recursively enumerable
languages over the alphabet {0,1}
S2. Set of all syntactically valid C programs
S3. Set of all languages over the alphabet
{0,1}
7
S4. Set of all non-regular languages over
the alphabet {0,1}
Which of the above sets are uncountable?
A. S1 and S2 B. S3 and S4
C. S2 and S3 D. S1 and S4
45. Consider the first order predicate formula ?? :
??? [(??? ?? |?? ?((?? =?? )?(?? =1)))???? (?? >?? )?(???
?? |?? ?((?? =?? )?(?? =1)))]
Here ?a|b? denotes that ?a divides b?, where
a and b are integers. Consider the following
sets:
S1. {1,2,3,?,100}
S2. Set of all positive integers
S3. Set of all integers
Which of the above sets satisfy ?? ?
A. S1 and S2 B. S1 and S3
C. S2 and S3 D. S1, S2 and S3
46. Consider the following grammar and the
semantic actions to support the inherited
type declaration attributes. Let X1, X2, X3,
X4, X5, and X6 be the placeholders for the
non-terminals D, T, L or L1 in the following
table:
Production rule Semantic action
D ? T L
?? 1.type = ?? 2.type
T ? int
T.type = int
T.type = int t.type = float
L ? L1 , id
X3.type = X4.type and
Type (id.type, X5.type)
L ? id
addType(id.entry,
?? 6.type)
Which one of the following are the
appropriate choices for ?? 1, ?? 2, ?? 3 and ?? 4?
A. ?? 1 = L, ?? 2 = ?? , ?? 3 = ?? 1, ?? 4 = ??
B. ?? 1 = L, ?? 2 = ?? , ?? 3 = ?? 1, ?? 4 = ??
C. ?? 1 = L, ?? 2 = ?? , ?? 3 = ?? 1, ?? 4 = ??
D. ?? 1 = L, ?? 2 = ?? , ?? 3 = ?? , ?? 4 = ?? 1
47. There are n unsorted arrays: A1, A2, ?, An.
Assume that n is odd. Each of A1, A2, ?, An
contains n distinct elements. There are no
common elements between any two arrays.
The worst-case time complexity of
computing the median of the medians of A1,
A2, ?, An is
A. O(n) B. O(n log n)
C. O(n
2
) D. ?(n
2
log n)
48. Let G be any connected, weighted,
undirected graph.
I. G has a unique minimum spanning tree,
if no two edges of G have the same
weight.
II. G has a unique minimum spanning tree,
if, for every cut of G, there is a unique
minimum-weight edge crossing the cut.
Which of the above two statements is/are
TRUE?
A. I only B. II only
C. Both I and II D. Neither I nor II
49. Consider the following snapshot of a system
running ?? concurrent processes. Process ?? is
holding ???? instances of a resource R, 1 ? ?? ? ?? .
Assume that all instances of R are currently
in use. Further, for all ?? , process ?? can place
a request for at most ???? additional instances
of R while holding the ???? instances it already
has. Of the ?? processes, there are exactly
two processes ?? and ?? such that ???? = ???? =
0. Which one of the following conditions
guarantees that no other process apart from
?? and ?? can complete execution?
A. ?? ?? + ?? ?? < Min {?? ?? | 1 ? ?? ? ,k ? p,
k ? q}
B. ?? ?? + ?? ?? < Max {?? ?? | 1 ? ?? ? ,k ? p,
k ? q}
C. Min (?? p, X?? ) ? Min {?? ?? | 1 ? ?? ? ?? ,
k ? p, k ? q}
D. Min (?? ?? , X?? ) ? Max {?? ?? | 1 ? ?? ? ?? ,
k ? p, k ? q}
50. Consider the following statements:
I. The smallest element in a max-heap is
always at a leaf node
II. The second largest element in a max-
heap is always a child of the root node
III. A max-heap can be constructed from a
binary search tree in ?(?? ) time
IV. A binary search tree can be constructed
from a max-heap in ?(?? ) time
Which of the above statements are TRUE?
A. I, II and III B. I, II and IV
C. I, III and IV D. II, III and IV
51. Consider the following four processes with
arrival times (in milliseconds) and their
length of CPU bursts (in milliseconds) as
shown below:
Process P1 P2 P3 P4
Arrival time 0 1 3 4
FirstRanker.com - FirstRanker's Choice
2
1. The expenditure on the project _________
as follows: equipment Rs.20 lakhs, salaries
Rs.12 lakhs, and contingency Rs.3 lakhs.
A. break down B. break
C. breaks down D. breaks
2. The search engine?s business model
___________ around the fulcrum of trust.
A. revolves B. plays
C. sinks D. bursts
3. Two cars start at the same time from the
same location and go in the same direction.
The speed of the first car is 50 km/h and the
speed of the second car is 60 km/h. The
number of hours it takes for the distance
between the two cars to be 20 km is
____________.
A. 1 B. 2
C. 3 D. 6
4. Ten friends planned to share equally the
cost of buying a gift for their teacher. When
two of them decided not to contribute, each
of the other friends had to pay Rs 150 more.
The cost of the gift was Rs. ___________.
A. 666 B. 3000
C. 6000 D. 12000
5. A court is to a judge as ___________ is to
a teacher.
A. a student B. a punishment
C. a syllabus D. a school
Q. 6 ? Q. 10 carry two marks each.
6. The police arrested four criminals ? P, Q, R
and S. The criminals knew each other. They
made the following statements:
P says ?Q committed the crime.?
Q says ?S committed the crime.?
R says ?I did not do it.?
S says ?What Q said about me is false.?
Assume only one of the arrested four
committed the crime and only one of the
statements made above is true. Who
committed the crime?
A. P B. R
C. S D. Q
7. In the given diagram, teachers are
represented in the triangle, researchers in
the circle and administrators in the
rectangle. Out of the total number of the
people, the percentage of administrators
shall be in the range of ___________.
A. 0 to 15 B. 16 to 30
C. 31 to 45 D. 46 to 60
8. ?A recent High Court judgement has sought
to dispel the idea of begging as a disease ?
which leads to its stigmatization and
criminalization ? and to regard it as a
symptom. The underlying disease is the
failure of the state to protect citizens who
fall through the social security net.?
Which one of the following statements can
be inferred from the given passage?
A. Beggars are lazy people who beg
because they are unwilling to work
B. Beggars are created because of the lack
of social welfare schemes
C. Begging is an offence that has to be
dealt with firmly
D. Begging has to be banned because it
adversely affects the welfare of the
state
9. In a college, there are three student clubs.
Sixty students are only in the Drama club,
80 students are only in the Dance club, 30
students are only in the Maths club, 40
students are in both Drama and Dance
clubs, 12 students are in both Dance and
Maths clubs, 7 students are in both Drama
and Maths clubs, and 2 students are in all
the clubs. If 75% of the students in the
college are not in any of these clubs, then
the total number of students in the college
is ___________.
A. 1000 B. 975
C. 900 D. 225
10. Three of the five students allocated to a
hostel put in special requests to the warden.
Given the floor plan of the vacant rooms,
select the allocation plan that will
accommodate all their requests.
Request by X: Due to pollen allergy, I want
to avoid a wing next to the garden.
3
Request by Y: I want to live as far from the
washrooms as possible, since I am very
sensitive to smell.
Request by Z: I believe in Vaastu and so
want to stay in the South-west wing.
The shaded rooms are already occupied. WR
is washroom.
A.
B.
C.
D.
11. A certain processor uses a fully associative
cache of size 16 kB. The cache block size is
16 bytes. Assume that the main memory is
byte addressable and uses a 32-bit address.
How many bits are required for the Tag and
the Index fields respectively in the
addresses generated by the processor?
A. 24 bits and 0 bits
B. 28 bits and 4 bits
C. 24 bits and 4 bits
D. 28 bits and 0 bits
12. The chip select logic for a certain DRAM chip
in a memory system design is shown below.
Assume that the memory system has 16
address lines denoted by A15 to A0. What is
the range of addresses (in hexadecimal) of
the memory system that can get enabled by
the chip select (CS) signal?
A. C800 to CFFF B. CA00 to CAFF
C. C800 to C8FF D. DA00 to DFFF
13. Which one of the following kinds of
derivation is used by LR parsers?
A. Leftmost
B. Leftmost in reverse
C. Rightmost
D. Rightmost in reverse
14. In 16-bit 2?s complement representation, the
decimal number ?28 is:
A. 1111 1111 0001 1100
B. 0000 0000 1110 0100
C. 1111 1111 1110 0100
D. 1000 0000 1110 0100
15. Let U = {1,2,?,?? }. Let ?? ={(?? , ?? )| ?? ? ?? , ?? ?
?? }. Consider the following two statements
on |?? |.
I. |?? | = ?? 2
?? ?1
II.
Which of the above statements is/are TRUE?
A. Only I B. Only II
C. Both I and II D. Neither I nor II
16. Which one of the following is NOT a valid
identity?
A. (x ? y) ? z = x ? (y ? z)
4
B. (x + y) ? z = x ? (y + z)
C. x ? y = x + y, if xy = 0
D. x ? y = (xy + x?y?)?
17. If ?? is a regular language over ? = {?? ,},
which one of the following languages is NOT
regular?
A. ?? ? ?? ?? = {???? | ?? ??? , ?? ?? ? ?? }
B. {????
?? | ?? ? ?? }
C. Prefix (?? ) = {?? ? ?? ?
|??? ? ?? ? such that ????
? ?? }
D. Suffix (?? ) = {?? ? ?? ?
|??? ? ?? ? such that ????
? ?? }
18. Consider Z = X ? Y, where X, Y and Z are all
in sign-magnitude form. X and Y are each
represented in ?? bits. To avoid overflow, the
representation of Z would require a
minimum of:
A. n bits B. n - 1 bits
C. n + 1 bits D. n + 2 bits
19. Let X be a square matrix. Consider the
following two statements on X.
I. X is invertible.
II. Determinant of X is non-zero.
Which one of the following is TRUE?
A. I implies II; II does not imply I.
B. II implies I; I does not imply II.
C. I does not imply II; II does not imply I.
D. I and II are equivalent statements.
20. Let G be an arbitrary group. Consider the
following relations on G:
R1: ??? ,b ? ?? , ?? ?? 1 ?? if and only if ??? ? ?? such
that a = g
-1
bg
R2: ??? ,b ? ?? , ?? ?? 2?? if and only if a = b
-1
Which of the above is/are equivalence
relation/relations?
A. R1 and R2
B. R1 only
C. R2 only
D. Neither R1 and R2
21. Consider the following two statements
about database transaction schedules:
I. Strict two-phase locking protocol
generates conflict serializable schedules
that are also recoverable.
II. Timestamp-ordering concurrency
control protocol with Thomas? Write Rule
can generate view serializable schedules
that are not conflict serializable.
Which of the above statements is/are TRUE?
A. I only B. II only
C. Both I and II D. Neither I nor II
22. Let G be an undirected complete graph on ??
vertices, where n > 2. Then, the number of
different Hamiltonian cycles in G is equal to
A. n! B. (n ? 1)!
C. 1 D.
23. Compute
A. 1
B. 53/12
C. 108/7
D. Limit does not exist
24. Which one of the following statements is
NOT correct about the B+ tree data
structure used for creating an index of a
relational database table?
A. B+ Tree is a height-balanced tree
B. Non-leaf nodes have pointers to data
records
C. Key values in each node are kept in
sorted order
D. Each leaf node has a pointer to the next
leaf node
25. For ? = {a, b}, let us consider the regular
language L = {x |x = a
2+3k
or x = b
10 + 12k
, k
? 0}. Which one of the following can be a
pumping length (the constant guaranteed by the
pumping lemma) for L?
A. 3 B. 5
C. 9 D. 24
26. Which of the following protocol pairs can be
used to send and retrieve e-mails (in that
order)?
A. IMAP, POP3 B. SMTP, POP3
C. SMTP, MIME D. IMAP, SMTP
27. The following C program is executed on a
Unix/Linux system:
#include
int main()
{
int i;
for (i=0; i<10; i++)
if (i%2 == 0) fork();
return 0;
}
The total number of child processes created
is ________.
28. Consider the following C program:
#include
5
int jumble(int x, int y){
x=2*x+y;
return x;
}
int main(){
int x=2, y=5;
y=jumble(y,x);
x=jumble(y,x);
printf(?%d \n?, x);
return 0;
}
The value printed by the program is
_______.
29. Consider the grammar given below:
S ? Aa
A ? BD
B ? b | ?
D ? d | ?
Let a, b, d, and $ be indexed as follows:
a b d $
3 2 1 0
Compute the FOLLOW set of the non-
terminal B and write the index values for the
symbols in the FOLLOW set in the
descending order. (For example, if the
FOLLOW set is {a, b, d, $}, then the answer
should be 3210)
Answer: ________.
30. An array of 25 distinct elements is to be
sorted using quicksort. Assume that the
pivot element is chosen uniformly at
random. The probability that the pivot
element gets placed in the worst possible
location in the first round of partitioning
(rounded off to 2 decimal places) is
________.
31. The value of 3^51 mod 5 is ________.
32. Two numbers are chosen independently and
uniformly at random from the set
{1, 2,...,13}. The probability (rounded off to
3 decimal places) that their 4-bit (unsigned)
binary representations have the same most
significant bit is ___________.
33. Consider three concurrent processes P1, P2
and P3 as shown below, which access a
shared variable D that has been initialized
to 100.
The processes are executed on a
uniprocessor system running a time-shared
operating system. If the minimum and
maximum possible values of D after the
three processes have completed execution
are X and Y respectively, then the value of
Y ? X is _____________.
34. Consider the following C program:
#include
int main(){
int arr[]={1,2,3,4,5,6,7,8,9,0,1,2,5},
*ip=arr+4;
printf(?%d\n?, ip[1]);
return 0;
}
The number that will be displayed on
execution of the program is ___________ .
35. Consider a sequence of 14 elements: A = [?5,
?10, 6, 3, ?1, ?2, 13, 4, ?9, ?1, 4, 12, ?3, 0].
The subsequence sum
Determine the maximum of S(i, j), where 0 ? i ?
j < 14. Divide and conquer approach may be
used.)
Answer: ________.
36. Consider the following C function.
void convert(int n){
if(n<0)
printf(?%d?,n);
else {
convert(n/2);
printf(?%d?,n%2);
}
}
Which one of the following will happen when
the function convert is called with any
positive integer n as argument?
A. It will print the binary representation of
n and terminate
B. It will print the binary representation of
n in the reverse order and terminate
C. It will print the binary representation of
n but will not terminate
D. It will not print anything and will not
terminate
6
37. Consider the following C program:
#include
int r(){
static int num=7;
return num--;
}
int main(){
for (r();r();r())
printf(?%d?,r());
return 0;
}
Which one of the following values will be
displayed on execution of the programs?
A. 41 B. 52
C. 63 D. 630
38. Consider three machines M, N, and P with IP
addresses 100.10.5.2, 100.10.5.5, and
100.10.5.6 respectively. The subnet mask is
set to 255.255.255.252 for all the three
machines. Which one of the following is
true?
A. M, N, and P all belong to the same
subnet
B. Only M and N belong to the same subnet
C. Only N and P belong to the same subnet
D. M, N, and P belong to three different
subnets
39. Suppose that in an IP-over-Ethernet
network, a machine X wishes to find the
MAC address of another machine Y in its
subnet. Which one of the following
techniques can be used for this?
A. X sends an ARP request packet to the
local gateway?s IP address which then
finds the MAC address of Y and sends to
X
B. X sends an ARP request packet to the
local gateway?s MAC address which then
finds the MAC address of Y and sends to
X
C. X sends an ARP request packet with
broadcast MAC address in its local
subnet
D. X sends an ARP request packet with
broadcast IP address in its local subnet
40. Consider three 4-variable functions f1, f2,
and f3, which are expressed in sum-of-
minterms as
f1 = ?(0, 2, 5, 8, 14), f2 = ?(2, 3, 6, 8, 14,
15), f3 = ? (2, 7, 11, 14)
For the following circuit with one AND gate
and one XOR gate, the output function f can
be expressed as:
A. ? (7, 8, 11)
B. ? (2, 7, 8, 11, 14)
C. ? (2, 14)
D. ? (0, 2, 3, 5, 6, 7, 8, 11, 14, 15)
41. Which one of the following languages over ?
= {a, b}is NOT context-free?
A. {ww
R
|w ? {a,b}
*
}
B. {wa
n
b
n
w
R
|w {a, b}
*
, n ? 0}
C. {wa
n
w
R
b
n
|w {a,b}
*
, n ? 0}
D. {anbi |i ? |n, 3n, 5n}, n ? 0}
42. Let the set of functional dependencies F =
{QR ? S, R ? P, S ? Q} hold on a relation
schema X = (PQRS). X is not in BCNF.
Suppose X is decomposed into two schemas
Y and Z, where Y = (PR) and Z = (QRS).
Consider the two statements given below.
I. Both Y and Z are in BCNF
II. Decomposition of X into Y and Z is
dependency preserving and lossless
Which of the above statements is/are
correct?
A. Both I and II B. I only
C. II only D. Neither I nor II
43. Assume that in a certain computer, the
virtual addresses are 64 bits long and the
physical addresses are 48 bits long. The
memory is word addressible. The page size
is 8 kB and the word size is 4 bytes. The
Translation Look-aside Buffer (TLB) in the
address translation path has 128 valid
entries. At most how many distinct virtual
addresses can be translated without any
TLB miss?
A. 16 ? 2
10
B. 256 ? 2
10
C. 4 ? 2
20
D. 8 ? 2
20
44. Consider the following sets:
S1. Set of all recursively enumerable
languages over the alphabet {0,1}
S2. Set of all syntactically valid C programs
S3. Set of all languages over the alphabet
{0,1}
7
S4. Set of all non-regular languages over
the alphabet {0,1}
Which of the above sets are uncountable?
A. S1 and S2 B. S3 and S4
C. S2 and S3 D. S1 and S4
45. Consider the first order predicate formula ?? :
??? [(??? ?? |?? ?((?? =?? )?(?? =1)))???? (?? >?? )?(???
?? |?? ?((?? =?? )?(?? =1)))]
Here ?a|b? denotes that ?a divides b?, where
a and b are integers. Consider the following
sets:
S1. {1,2,3,?,100}
S2. Set of all positive integers
S3. Set of all integers
Which of the above sets satisfy ?? ?
A. S1 and S2 B. S1 and S3
C. S2 and S3 D. S1, S2 and S3
46. Consider the following grammar and the
semantic actions to support the inherited
type declaration attributes. Let X1, X2, X3,
X4, X5, and X6 be the placeholders for the
non-terminals D, T, L or L1 in the following
table:
Production rule Semantic action
D ? T L
?? 1.type = ?? 2.type
T ? int
T.type = int
T.type = int t.type = float
L ? L1 , id
X3.type = X4.type and
Type (id.type, X5.type)
L ? id
addType(id.entry,
?? 6.type)
Which one of the following are the
appropriate choices for ?? 1, ?? 2, ?? 3 and ?? 4?
A. ?? 1 = L, ?? 2 = ?? , ?? 3 = ?? 1, ?? 4 = ??
B. ?? 1 = L, ?? 2 = ?? , ?? 3 = ?? 1, ?? 4 = ??
C. ?? 1 = L, ?? 2 = ?? , ?? 3 = ?? 1, ?? 4 = ??
D. ?? 1 = L, ?? 2 = ?? , ?? 3 = ?? , ?? 4 = ?? 1
47. There are n unsorted arrays: A1, A2, ?, An.
Assume that n is odd. Each of A1, A2, ?, An
contains n distinct elements. There are no
common elements between any two arrays.
The worst-case time complexity of
computing the median of the medians of A1,
A2, ?, An is
A. O(n) B. O(n log n)
C. O(n
2
) D. ?(n
2
log n)
48. Let G be any connected, weighted,
undirected graph.
I. G has a unique minimum spanning tree,
if no two edges of G have the same
weight.
II. G has a unique minimum spanning tree,
if, for every cut of G, there is a unique
minimum-weight edge crossing the cut.
Which of the above two statements is/are
TRUE?
A. I only B. II only
C. Both I and II D. Neither I nor II
49. Consider the following snapshot of a system
running ?? concurrent processes. Process ?? is
holding ???? instances of a resource R, 1 ? ?? ? ?? .
Assume that all instances of R are currently
in use. Further, for all ?? , process ?? can place
a request for at most ???? additional instances
of R while holding the ???? instances it already
has. Of the ?? processes, there are exactly
two processes ?? and ?? such that ???? = ???? =
0. Which one of the following conditions
guarantees that no other process apart from
?? and ?? can complete execution?
A. ?? ?? + ?? ?? < Min {?? ?? | 1 ? ?? ? ,k ? p,
k ? q}
B. ?? ?? + ?? ?? < Max {?? ?? | 1 ? ?? ? ,k ? p,
k ? q}
C. Min (?? p, X?? ) ? Min {?? ?? | 1 ? ?? ? ?? ,
k ? p, k ? q}
D. Min (?? ?? , X?? ) ? Max {?? ?? | 1 ? ?? ? ?? ,
k ? p, k ? q}
50. Consider the following statements:
I. The smallest element in a max-heap is
always at a leaf node
II. The second largest element in a max-
heap is always a child of the root node
III. A max-heap can be constructed from a
binary search tree in ?(?? ) time
IV. A binary search tree can be constructed
from a max-heap in ?(?? ) time
Which of the above statements are TRUE?
A. I, II and III B. I, II and IV
C. I, III and IV D. II, III and IV
51. Consider the following four processes with
arrival times (in milliseconds) and their
length of CPU bursts (in milliseconds) as
shown below:
Process P1 P2 P3 P4
Arrival time 0 1 3 4
8
CPU burst time 3 1 3 Z
These processes are run on a single
processor using preemptive Shortest
Remaining Time First scheduling algorithm.
If the average waiting time of the processes
is 1 millisecond, then the value of Z
is________.
52. The index node (inode) of a Unix-like file
system has 12 direct, one single-indirect
and one double-indirect pointers. The disk
block size is 4 kB, and the disk block address
is 32-bits long. The maximum possible file
size is (rounded off to 1 decimal place)
_________ GB.
53. Consider the augmented grammar given
below:
S' ? S
S ? ?L? | id
L ? L,S | S
Let I0 = CLOSURE ({[S' ? ?S]}). The
number of items in the set GOTO (I0 , ? ) is:
________.
54. Consider the following matrix:
The absolute value of the product of Eigen
values of R is ____________.
55. A certain processor deploys a single-level
cache. The cache block size is 8 words and
the word size is 4 bytes. The memory
system uses a 60-MHz clock. To service a
cache miss, the memory controller first
takes 1 cycle to accept the starting address
of the block, it then takes 3 cycles to fetch
all the eight words of the block, and finally
transmits the words of the requested block
at the rate of 1 word per cycle. The
maximum bandwidth for the memory
system when the program running on the
processor issues a series of read operations
is __________? 10
6
bytes/sec.
56. Let T be a full binary tree with 8 leaves. (A
full binary tree has every level full.)
Suppose two leaves a and b of T are chosen
uniformly and independently at random.
The expected value of the distance between
a and b in T (i.e., the number of edges in
the unique path between a and b) is
(rounded off to 2 decimal places)
___________.
57. Suppose Y is distributed uniformly in the
open interval (1, 6). The probability that the
polynomial 3x
2
+ 6xy + 3Y + 6 has only real
roots is (rounded off to 1 decimal place)
________.
58. Let ? be the set of all bijections from
{1,?,5} to {1,?,5}, where ???? denotes the
identity function, i.e. id(?? ) = ?? ,??? . Let ?
denote composition on functions. For a
string ?? = ?? 1 ?? 2 ? ?? ?? ? ?
?? , ?? ? 0, let (?? ) = ?? 1 ?
?? 2 ? ? ? ?? ?? .
Consider the language ?? = {?? ? ??| (?? ) = ???? }.
The minimum number of states in any DFA
accepting L is _________.
59. Consider that 15 machines need to be
connected in a LAN using 8-port Ethernet
switches. Assume that these switches do
not have any separate uplink ports. The
minimum number of switches needed
is__________.
60. What is the minimum number of 2-input
NOR gates required to implement a 4-
variable function expressed in sum-of-
minterms form as f = (0, 2, 5, 7, 8, 10,
13, 15)? Assume that all the inputs and their
complements are available. Answer:
_______________.
61. A relational database contains two tables
Student and Performance as shown below:
Student
Roll_no. Student_nam
e
1 Amit
2 Priya
3 Vinit
4 Rohan
5 Smita
Performance
Roll_no Subject_code Marks
1 A 86
1 B 95
1 C 90
2 A 89
2 C 92
3 C 80
The primary key of the Student table is
Roll_no. For the Performance table, the
columns Roll_no. and Subject_code
FirstRanker.com - FirstRanker's Choice
2
1. The expenditure on the project _________
as follows: equipment Rs.20 lakhs, salaries
Rs.12 lakhs, and contingency Rs.3 lakhs.
A. break down B. break
C. breaks down D. breaks
2. The search engine?s business model
___________ around the fulcrum of trust.
A. revolves B. plays
C. sinks D. bursts
3. Two cars start at the same time from the
same location and go in the same direction.
The speed of the first car is 50 km/h and the
speed of the second car is 60 km/h. The
number of hours it takes for the distance
between the two cars to be 20 km is
____________.
A. 1 B. 2
C. 3 D. 6
4. Ten friends planned to share equally the
cost of buying a gift for their teacher. When
two of them decided not to contribute, each
of the other friends had to pay Rs 150 more.
The cost of the gift was Rs. ___________.
A. 666 B. 3000
C. 6000 D. 12000
5. A court is to a judge as ___________ is to
a teacher.
A. a student B. a punishment
C. a syllabus D. a school
Q. 6 ? Q. 10 carry two marks each.
6. The police arrested four criminals ? P, Q, R
and S. The criminals knew each other. They
made the following statements:
P says ?Q committed the crime.?
Q says ?S committed the crime.?
R says ?I did not do it.?
S says ?What Q said about me is false.?
Assume only one of the arrested four
committed the crime and only one of the
statements made above is true. Who
committed the crime?
A. P B. R
C. S D. Q
7. In the given diagram, teachers are
represented in the triangle, researchers in
the circle and administrators in the
rectangle. Out of the total number of the
people, the percentage of administrators
shall be in the range of ___________.
A. 0 to 15 B. 16 to 30
C. 31 to 45 D. 46 to 60
8. ?A recent High Court judgement has sought
to dispel the idea of begging as a disease ?
which leads to its stigmatization and
criminalization ? and to regard it as a
symptom. The underlying disease is the
failure of the state to protect citizens who
fall through the social security net.?
Which one of the following statements can
be inferred from the given passage?
A. Beggars are lazy people who beg
because they are unwilling to work
B. Beggars are created because of the lack
of social welfare schemes
C. Begging is an offence that has to be
dealt with firmly
D. Begging has to be banned because it
adversely affects the welfare of the
state
9. In a college, there are three student clubs.
Sixty students are only in the Drama club,
80 students are only in the Dance club, 30
students are only in the Maths club, 40
students are in both Drama and Dance
clubs, 12 students are in both Dance and
Maths clubs, 7 students are in both Drama
and Maths clubs, and 2 students are in all
the clubs. If 75% of the students in the
college are not in any of these clubs, then
the total number of students in the college
is ___________.
A. 1000 B. 975
C. 900 D. 225
10. Three of the five students allocated to a
hostel put in special requests to the warden.
Given the floor plan of the vacant rooms,
select the allocation plan that will
accommodate all their requests.
Request by X: Due to pollen allergy, I want
to avoid a wing next to the garden.
3
Request by Y: I want to live as far from the
washrooms as possible, since I am very
sensitive to smell.
Request by Z: I believe in Vaastu and so
want to stay in the South-west wing.
The shaded rooms are already occupied. WR
is washroom.
A.
B.
C.
D.
11. A certain processor uses a fully associative
cache of size 16 kB. The cache block size is
16 bytes. Assume that the main memory is
byte addressable and uses a 32-bit address.
How many bits are required for the Tag and
the Index fields respectively in the
addresses generated by the processor?
A. 24 bits and 0 bits
B. 28 bits and 4 bits
C. 24 bits and 4 bits
D. 28 bits and 0 bits
12. The chip select logic for a certain DRAM chip
in a memory system design is shown below.
Assume that the memory system has 16
address lines denoted by A15 to A0. What is
the range of addresses (in hexadecimal) of
the memory system that can get enabled by
the chip select (CS) signal?
A. C800 to CFFF B. CA00 to CAFF
C. C800 to C8FF D. DA00 to DFFF
13. Which one of the following kinds of
derivation is used by LR parsers?
A. Leftmost
B. Leftmost in reverse
C. Rightmost
D. Rightmost in reverse
14. In 16-bit 2?s complement representation, the
decimal number ?28 is:
A. 1111 1111 0001 1100
B. 0000 0000 1110 0100
C. 1111 1111 1110 0100
D. 1000 0000 1110 0100
15. Let U = {1,2,?,?? }. Let ?? ={(?? , ?? )| ?? ? ?? , ?? ?
?? }. Consider the following two statements
on |?? |.
I. |?? | = ?? 2
?? ?1
II.
Which of the above statements is/are TRUE?
A. Only I B. Only II
C. Both I and II D. Neither I nor II
16. Which one of the following is NOT a valid
identity?
A. (x ? y) ? z = x ? (y ? z)
4
B. (x + y) ? z = x ? (y + z)
C. x ? y = x + y, if xy = 0
D. x ? y = (xy + x?y?)?
17. If ?? is a regular language over ? = {?? ,},
which one of the following languages is NOT
regular?
A. ?? ? ?? ?? = {???? | ?? ??? , ?? ?? ? ?? }
B. {????
?? | ?? ? ?? }
C. Prefix (?? ) = {?? ? ?? ?
|??? ? ?? ? such that ????
? ?? }
D. Suffix (?? ) = {?? ? ?? ?
|??? ? ?? ? such that ????
? ?? }
18. Consider Z = X ? Y, where X, Y and Z are all
in sign-magnitude form. X and Y are each
represented in ?? bits. To avoid overflow, the
representation of Z would require a
minimum of:
A. n bits B. n - 1 bits
C. n + 1 bits D. n + 2 bits
19. Let X be a square matrix. Consider the
following two statements on X.
I. X is invertible.
II. Determinant of X is non-zero.
Which one of the following is TRUE?
A. I implies II; II does not imply I.
B. II implies I; I does not imply II.
C. I does not imply II; II does not imply I.
D. I and II are equivalent statements.
20. Let G be an arbitrary group. Consider the
following relations on G:
R1: ??? ,b ? ?? , ?? ?? 1 ?? if and only if ??? ? ?? such
that a = g
-1
bg
R2: ??? ,b ? ?? , ?? ?? 2?? if and only if a = b
-1
Which of the above is/are equivalence
relation/relations?
A. R1 and R2
B. R1 only
C. R2 only
D. Neither R1 and R2
21. Consider the following two statements
about database transaction schedules:
I. Strict two-phase locking protocol
generates conflict serializable schedules
that are also recoverable.
II. Timestamp-ordering concurrency
control protocol with Thomas? Write Rule
can generate view serializable schedules
that are not conflict serializable.
Which of the above statements is/are TRUE?
A. I only B. II only
C. Both I and II D. Neither I nor II
22. Let G be an undirected complete graph on ??
vertices, where n > 2. Then, the number of
different Hamiltonian cycles in G is equal to
A. n! B. (n ? 1)!
C. 1 D.
23. Compute
A. 1
B. 53/12
C. 108/7
D. Limit does not exist
24. Which one of the following statements is
NOT correct about the B+ tree data
structure used for creating an index of a
relational database table?
A. B+ Tree is a height-balanced tree
B. Non-leaf nodes have pointers to data
records
C. Key values in each node are kept in
sorted order
D. Each leaf node has a pointer to the next
leaf node
25. For ? = {a, b}, let us consider the regular
language L = {x |x = a
2+3k
or x = b
10 + 12k
, k
? 0}. Which one of the following can be a
pumping length (the constant guaranteed by the
pumping lemma) for L?
A. 3 B. 5
C. 9 D. 24
26. Which of the following protocol pairs can be
used to send and retrieve e-mails (in that
order)?
A. IMAP, POP3 B. SMTP, POP3
C. SMTP, MIME D. IMAP, SMTP
27. The following C program is executed on a
Unix/Linux system:
#include
int main()
{
int i;
for (i=0; i<10; i++)
if (i%2 == 0) fork();
return 0;
}
The total number of child processes created
is ________.
28. Consider the following C program:
#include
5
int jumble(int x, int y){
x=2*x+y;
return x;
}
int main(){
int x=2, y=5;
y=jumble(y,x);
x=jumble(y,x);
printf(?%d \n?, x);
return 0;
}
The value printed by the program is
_______.
29. Consider the grammar given below:
S ? Aa
A ? BD
B ? b | ?
D ? d | ?
Let a, b, d, and $ be indexed as follows:
a b d $
3 2 1 0
Compute the FOLLOW set of the non-
terminal B and write the index values for the
symbols in the FOLLOW set in the
descending order. (For example, if the
FOLLOW set is {a, b, d, $}, then the answer
should be 3210)
Answer: ________.
30. An array of 25 distinct elements is to be
sorted using quicksort. Assume that the
pivot element is chosen uniformly at
random. The probability that the pivot
element gets placed in the worst possible
location in the first round of partitioning
(rounded off to 2 decimal places) is
________.
31. The value of 3^51 mod 5 is ________.
32. Two numbers are chosen independently and
uniformly at random from the set
{1, 2,...,13}. The probability (rounded off to
3 decimal places) that their 4-bit (unsigned)
binary representations have the same most
significant bit is ___________.
33. Consider three concurrent processes P1, P2
and P3 as shown below, which access a
shared variable D that has been initialized
to 100.
The processes are executed on a
uniprocessor system running a time-shared
operating system. If the minimum and
maximum possible values of D after the
three processes have completed execution
are X and Y respectively, then the value of
Y ? X is _____________.
34. Consider the following C program:
#include
int main(){
int arr[]={1,2,3,4,5,6,7,8,9,0,1,2,5},
*ip=arr+4;
printf(?%d\n?, ip[1]);
return 0;
}
The number that will be displayed on
execution of the program is ___________ .
35. Consider a sequence of 14 elements: A = [?5,
?10, 6, 3, ?1, ?2, 13, 4, ?9, ?1, 4, 12, ?3, 0].
The subsequence sum
Determine the maximum of S(i, j), where 0 ? i ?
j < 14. Divide and conquer approach may be
used.)
Answer: ________.
36. Consider the following C function.
void convert(int n){
if(n<0)
printf(?%d?,n);
else {
convert(n/2);
printf(?%d?,n%2);
}
}
Which one of the following will happen when
the function convert is called with any
positive integer n as argument?
A. It will print the binary representation of
n and terminate
B. It will print the binary representation of
n in the reverse order and terminate
C. It will print the binary representation of
n but will not terminate
D. It will not print anything and will not
terminate
6
37. Consider the following C program:
#include
int r(){
static int num=7;
return num--;
}
int main(){
for (r();r();r())
printf(?%d?,r());
return 0;
}
Which one of the following values will be
displayed on execution of the programs?
A. 41 B. 52
C. 63 D. 630
38. Consider three machines M, N, and P with IP
addresses 100.10.5.2, 100.10.5.5, and
100.10.5.6 respectively. The subnet mask is
set to 255.255.255.252 for all the three
machines. Which one of the following is
true?
A. M, N, and P all belong to the same
subnet
B. Only M and N belong to the same subnet
C. Only N and P belong to the same subnet
D. M, N, and P belong to three different
subnets
39. Suppose that in an IP-over-Ethernet
network, a machine X wishes to find the
MAC address of another machine Y in its
subnet. Which one of the following
techniques can be used for this?
A. X sends an ARP request packet to the
local gateway?s IP address which then
finds the MAC address of Y and sends to
X
B. X sends an ARP request packet to the
local gateway?s MAC address which then
finds the MAC address of Y and sends to
X
C. X sends an ARP request packet with
broadcast MAC address in its local
subnet
D. X sends an ARP request packet with
broadcast IP address in its local subnet
40. Consider three 4-variable functions f1, f2,
and f3, which are expressed in sum-of-
minterms as
f1 = ?(0, 2, 5, 8, 14), f2 = ?(2, 3, 6, 8, 14,
15), f3 = ? (2, 7, 11, 14)
For the following circuit with one AND gate
and one XOR gate, the output function f can
be expressed as:
A. ? (7, 8, 11)
B. ? (2, 7, 8, 11, 14)
C. ? (2, 14)
D. ? (0, 2, 3, 5, 6, 7, 8, 11, 14, 15)
41. Which one of the following languages over ?
= {a, b}is NOT context-free?
A. {ww
R
|w ? {a,b}
*
}
B. {wa
n
b
n
w
R
|w {a, b}
*
, n ? 0}
C. {wa
n
w
R
b
n
|w {a,b}
*
, n ? 0}
D. {anbi |i ? |n, 3n, 5n}, n ? 0}
42. Let the set of functional dependencies F =
{QR ? S, R ? P, S ? Q} hold on a relation
schema X = (PQRS). X is not in BCNF.
Suppose X is decomposed into two schemas
Y and Z, where Y = (PR) and Z = (QRS).
Consider the two statements given below.
I. Both Y and Z are in BCNF
II. Decomposition of X into Y and Z is
dependency preserving and lossless
Which of the above statements is/are
correct?
A. Both I and II B. I only
C. II only D. Neither I nor II
43. Assume that in a certain computer, the
virtual addresses are 64 bits long and the
physical addresses are 48 bits long. The
memory is word addressible. The page size
is 8 kB and the word size is 4 bytes. The
Translation Look-aside Buffer (TLB) in the
address translation path has 128 valid
entries. At most how many distinct virtual
addresses can be translated without any
TLB miss?
A. 16 ? 2
10
B. 256 ? 2
10
C. 4 ? 2
20
D. 8 ? 2
20
44. Consider the following sets:
S1. Set of all recursively enumerable
languages over the alphabet {0,1}
S2. Set of all syntactically valid C programs
S3. Set of all languages over the alphabet
{0,1}
7
S4. Set of all non-regular languages over
the alphabet {0,1}
Which of the above sets are uncountable?
A. S1 and S2 B. S3 and S4
C. S2 and S3 D. S1 and S4
45. Consider the first order predicate formula ?? :
??? [(??? ?? |?? ?((?? =?? )?(?? =1)))???? (?? >?? )?(???
?? |?? ?((?? =?? )?(?? =1)))]
Here ?a|b? denotes that ?a divides b?, where
a and b are integers. Consider the following
sets:
S1. {1,2,3,?,100}
S2. Set of all positive integers
S3. Set of all integers
Which of the above sets satisfy ?? ?
A. S1 and S2 B. S1 and S3
C. S2 and S3 D. S1, S2 and S3
46. Consider the following grammar and the
semantic actions to support the inherited
type declaration attributes. Let X1, X2, X3,
X4, X5, and X6 be the placeholders for the
non-terminals D, T, L or L1 in the following
table:
Production rule Semantic action
D ? T L
?? 1.type = ?? 2.type
T ? int
T.type = int
T.type = int t.type = float
L ? L1 , id
X3.type = X4.type and
Type (id.type, X5.type)
L ? id
addType(id.entry,
?? 6.type)
Which one of the following are the
appropriate choices for ?? 1, ?? 2, ?? 3 and ?? 4?
A. ?? 1 = L, ?? 2 = ?? , ?? 3 = ?? 1, ?? 4 = ??
B. ?? 1 = L, ?? 2 = ?? , ?? 3 = ?? 1, ?? 4 = ??
C. ?? 1 = L, ?? 2 = ?? , ?? 3 = ?? 1, ?? 4 = ??
D. ?? 1 = L, ?? 2 = ?? , ?? 3 = ?? , ?? 4 = ?? 1
47. There are n unsorted arrays: A1, A2, ?, An.
Assume that n is odd. Each of A1, A2, ?, An
contains n distinct elements. There are no
common elements between any two arrays.
The worst-case time complexity of
computing the median of the medians of A1,
A2, ?, An is
A. O(n) B. O(n log n)
C. O(n
2
) D. ?(n
2
log n)
48. Let G be any connected, weighted,
undirected graph.
I. G has a unique minimum spanning tree,
if no two edges of G have the same
weight.
II. G has a unique minimum spanning tree,
if, for every cut of G, there is a unique
minimum-weight edge crossing the cut.
Which of the above two statements is/are
TRUE?
A. I only B. II only
C. Both I and II D. Neither I nor II
49. Consider the following snapshot of a system
running ?? concurrent processes. Process ?? is
holding ???? instances of a resource R, 1 ? ?? ? ?? .
Assume that all instances of R are currently
in use. Further, for all ?? , process ?? can place
a request for at most ???? additional instances
of R while holding the ???? instances it already
has. Of the ?? processes, there are exactly
two processes ?? and ?? such that ???? = ???? =
0. Which one of the following conditions
guarantees that no other process apart from
?? and ?? can complete execution?
A. ?? ?? + ?? ?? < Min {?? ?? | 1 ? ?? ? ,k ? p,
k ? q}
B. ?? ?? + ?? ?? < Max {?? ?? | 1 ? ?? ? ,k ? p,
k ? q}
C. Min (?? p, X?? ) ? Min {?? ?? | 1 ? ?? ? ?? ,
k ? p, k ? q}
D. Min (?? ?? , X?? ) ? Max {?? ?? | 1 ? ?? ? ?? ,
k ? p, k ? q}
50. Consider the following statements:
I. The smallest element in a max-heap is
always at a leaf node
II. The second largest element in a max-
heap is always a child of the root node
III. A max-heap can be constructed from a
binary search tree in ?(?? ) time
IV. A binary search tree can be constructed
from a max-heap in ?(?? ) time
Which of the above statements are TRUE?
A. I, II and III B. I, II and IV
C. I, III and IV D. II, III and IV
51. Consider the following four processes with
arrival times (in milliseconds) and their
length of CPU bursts (in milliseconds) as
shown below:
Process P1 P2 P3 P4
Arrival time 0 1 3 4
8
CPU burst time 3 1 3 Z
These processes are run on a single
processor using preemptive Shortest
Remaining Time First scheduling algorithm.
If the average waiting time of the processes
is 1 millisecond, then the value of Z
is________.
52. The index node (inode) of a Unix-like file
system has 12 direct, one single-indirect
and one double-indirect pointers. The disk
block size is 4 kB, and the disk block address
is 32-bits long. The maximum possible file
size is (rounded off to 1 decimal place)
_________ GB.
53. Consider the augmented grammar given
below:
S' ? S
S ? ?L? | id
L ? L,S | S
Let I0 = CLOSURE ({[S' ? ?S]}). The
number of items in the set GOTO (I0 , ? ) is:
________.
54. Consider the following matrix:
The absolute value of the product of Eigen
values of R is ____________.
55. A certain processor deploys a single-level
cache. The cache block size is 8 words and
the word size is 4 bytes. The memory
system uses a 60-MHz clock. To service a
cache miss, the memory controller first
takes 1 cycle to accept the starting address
of the block, it then takes 3 cycles to fetch
all the eight words of the block, and finally
transmits the words of the requested block
at the rate of 1 word per cycle. The
maximum bandwidth for the memory
system when the program running on the
processor issues a series of read operations
is __________? 10
6
bytes/sec.
56. Let T be a full binary tree with 8 leaves. (A
full binary tree has every level full.)
Suppose two leaves a and b of T are chosen
uniformly and independently at random.
The expected value of the distance between
a and b in T (i.e., the number of edges in
the unique path between a and b) is
(rounded off to 2 decimal places)
___________.
57. Suppose Y is distributed uniformly in the
open interval (1, 6). The probability that the
polynomial 3x
2
+ 6xy + 3Y + 6 has only real
roots is (rounded off to 1 decimal place)
________.
58. Let ? be the set of all bijections from
{1,?,5} to {1,?,5}, where ???? denotes the
identity function, i.e. id(?? ) = ?? ,??? . Let ?
denote composition on functions. For a
string ?? = ?? 1 ?? 2 ? ?? ?? ? ?
?? , ?? ? 0, let (?? ) = ?? 1 ?
?? 2 ? ? ? ?? ?? .
Consider the language ?? = {?? ? ??| (?? ) = ???? }.
The minimum number of states in any DFA
accepting L is _________.
59. Consider that 15 machines need to be
connected in a LAN using 8-port Ethernet
switches. Assume that these switches do
not have any separate uplink ports. The
minimum number of switches needed
is__________.
60. What is the minimum number of 2-input
NOR gates required to implement a 4-
variable function expressed in sum-of-
minterms form as f = (0, 2, 5, 7, 8, 10,
13, 15)? Assume that all the inputs and their
complements are available. Answer:
_______________.
61. A relational database contains two tables
Student and Performance as shown below:
Student
Roll_no. Student_nam
e
1 Amit
2 Priya
3 Vinit
4 Rohan
5 Smita
Performance
Roll_no Subject_code Marks
1 A 86
1 B 95
1 C 90
2 A 89
2 C 92
3 C 80
The primary key of the Student table is
Roll_no. For the Performance table, the
columns Roll_no. and Subject_code
9
together form the primary key. Consider the
SQL query given below:
SELECT S.Student_name, sum(P.Marks)
FROM Student S, Performance P
WHERE P.Marks > 84
GROUP BY S.Student_name;
The number of rows returned by the above
SQL query is ________.
62. Consider the following C program:
#include
int main(){
float sum = 0.0, j = 1.0, i = 2.0;
while (i/j > 0.0625){
j = j + j;
sum = sum + i/j;
printf("%f\n", sum);
}
return 0;
}
The number of times the variable sum will
be printed, when the above program is
executed, is _________________.
63. Consider the following C program:
#include
int main()
{
int a[] = {2, 4, 6, 8, 10};
int i, sum = 0, *b = a + 4;
for (i = 0; i < 5; i++)
sum = sum + (*b ? i) ? *(b ? i);
printf (?%d\n?, sum);
return 0;
}
The output of the above C program is
__________.
64. In an RSA cryptosystem, the value of the
public modulus parameter ?? is 3007. If it is
also known that ?(?? ) = 2880, where ?()
denotes Euler?s Totient Function, then the
prime factor of ?? which is greater than 50 is
____________________.
65. Consider the following relations P(X,Y,Z),
Q(X,Y,T) and R(Y,V).
How many tuples will be returned by the
following relational algebra query?
Answer: ___________.
FirstRanker.com - FirstRanker's Choice
This post was last modified on 18 December 2019