Grand Test - 2 - PDF Flipbook

Grand Test - 2

304 Views
0 Downloads
PDF 9,476,814 Bytes

Download as PDF

REPORT DMCA


GATE
CSE

GrandTests

Test-02Solutions


APTITIDE
One Mark Questions

1. Divide Rs.118000 among three persons A, B and C such that
the ratio of the shares of A and B is 3:4 and that of B: C is
5:6?
a) A = 30000 B = 40000 C = 48000
b) A = 40000 B = 48000 C = 30000
c) A = 30000 B = 48000 C = 40000
d) A = 48000 B = 40000 C = 30000
Answer: (a)
Solution:
Compound ratio of A: B: C
A: B = 3:4
B: C = 5:6
----------
A: B: C = 15:20:24
we can divide Rs.118000 in this ratio.
Share of A = 15/59 * 118000 = 30000
Share of B = 20/59 * 118000 = 40000
Share of C = 24/59 * 118000 = 48000

2. Rajeev buys good worth Rs. 6650. He gets a rebate of 6% on
it. After getting the rebate, he pays sales tax @ 10%. Find
the amount he will have to pay for the goods.
a) Rs. 6876.10
b) Rs. 6999.20

1


c) Rs. 6654
d) Rs. 7000
Answer: (a)
Solution:
Rebate = 6% of Rs. 6650 = Rs�1600 × 6650� = Rs.399.
Sales tax = 10% of Rs. (6650 – 399) = Rs�11000 × 6251�

= Rs.625.10
∴ Final amount = Rs. (6251 + 625.10) = Rs. 6876.10
3. As a child, Oscar Wilde announced that he would like to be
remembered as the hero of a “cause célèbre and to go down
to _______ as the defendant in such a case as ‘Regina
Versus Wilde’”.
a) past
b) favorable
c) posterity
d) Defame.
Answer: (c)
4. Choose the word most nearly opposite to the given word.
Tyro
a) Heckle
b) Veteran
c) Vent
d) Persist
Answer: (b)

2


Solution:
Meaning: A tyro is a beginner, a recruit, or someone who is
just learning something.
Example: If you are the new guy wearing a big badge that
says ‘trainee’, you are a tyro.
Synonyms: Beginner, Amateur, Learner, Novice
Antonyms: Expert, Professional, Teacher, and Veteran
5. Choose the word or group of words which is most similar in
meaning to the word printed in bold.
Chasm
a) Gorge
b) Charm
c) Bridle
d) Criticize
Answer: (a)
Solution:
Meaning: A chasm is a deep divide, either literal or
figurative. An immeasurable depth or space
Example: The growing chasm between two friends that
have not spoken in a long time.
Synonyms: Abyss, Crater, Ravine, Rift, Void, Gorge
Antonyms: Closure, Solid

3


Two Mark Questions
6. Two pipes A and B can separately fill a cistern in 10 and 15
minutes respectively. A person opens both the pipes together
when the cistern should have been was full he finds the
waste pipe open. He then closes the waste pipe and in
another 4 minutes the cistern was full. In what time can the
waste pipe empty the cistern when fill?
a) 7 min
b) 8 min
c) 9 min
d) 10 min
Answer: (b)
Solution:
1/10 + 1/15 = 1/6 × 4 = 2/3
1 – 2/3 = 1/3
1/10 + 1/15 – 1/x = 1/3
x=8
7. Rs.1500 is divided into two parts such that if one part is
invested at 6% and the other at 5% the whole annual interest
from both the sum is Rs.85. How much was lent at 5%?
a) Rs.1000
b) Rs.750
c) Rs.600
d) Rs.500
Answer: (d)

4


Solution:

(X × 5 × 1)/100 + [(1500 ‒ x) × 6 × 1]/100 = 85

5x/100 + 90 – 6x/100 = 85

X/100 = 5

⇒ x = 500

8. If log 2 = 0.3010 and log 3 = 0.4771, the value of log5 512

is:

a) 2.870

b) 2.967

c) 3.876

d) 3.912

Answer: (c)

Solution:

log5 512 = log 512
log 5

= log 29
log(120)

= 9 log 2 2
log 10−log

= (9 ×0.3010) = 2.709 = 2709 = 3.876
1−0.3010 0.699 699

9. Giving undue favors to one's own kith and kin

a) Nepotism

b) Favoritism

c) Worldliness

d) Corruption

Answer: (a)

5


10. In the sentence given below a part is underlined; choose the
most suitable option that can replace the underlined part.
A ground-breaking report written by a major group of
scientists has indicated that much of the previously
untraceable pollutants in stream water known to kill fish and
harm humans comes from polluted rain water and
irresponsible chemical dumping by large corporations.
a) much of the previously untraceable pollutants in stream
water known to kill fish and harm humans comes from
b) much of the previously untraceable pollutants in stream
water known to kill fish and harm humans come from
c) many of the untraceable pollutants in stream water known
to kill fish and harm humans comes from
d) many of the previously untraceable pollutants in stream
water known to kill fish and harm humans come from
Answer: (d)
Solution:
There are two major issues with the sentence as it was
originally written:
a) This sentence improperly uses much to describe a
countable quantity (i.e., pollutants) when many should be
used instead. In proper English, much is used for
uncountable quantities (e.g., much of the water)
while many is used for countable quantities (e.g., many
apples, many gifts).

6


b) The subject of the sentence (untraceable pollutants, which
is plural) does not agree with the verb of the sentence
(comes, which is singular).
Much is wrongly used to describe a countable quantity
when many should be used instead; the subject
(pollutants) does not agree with the verb (comes).
Much is wrongly used to describe a countable quantity
when many should be used instead.

7


TECHNICAL

One Mark Questions

11. Two players, A and B, alternately keep roiling a fair dice.

The person to get a six first wins the game. Given that player

A starts the game, the probability that A wins the game is

a) 5/11

b) 1/2

c) 7/13

d) 6/11

Answer: (d)

Solution:

The required probability = 1 + �65�2 ‒ �61�+�65�4+�61� + ⋯
6

= 1 �1 + �65�2 −1 61. �1361� = 6
6 11
�=

12. The curve given by the equation

x2 + y2 = 3axy is

a) Symmetrical about x-axis

b) Symmetrical about y-axis

c) Symmetrical about the line y = x

d) Tangential to x = y = a/3

Answer: (c)

Solution:
f(x, y) = f(y, x) ⇒ curve is symmetric about the line y = x

8


13. If C is a circle of radius r with centre z0, in the complex z-

plane and if 'n' is a non-zero integer, then ∮ equal
( − ) +1

a) 2πnj

b) 0

c) nj


d) 2πn

Answer: (b)

Solution:

∫ = 0 [by Cauchy’s integral formula]
( − 0) +1

Since f(z) = 1 then f(n) (z) = 0

14. The area enclosed between the curves y2 = 4x and x2 = 4y is

a) 16
3

b) 8

c) 32
3

d) 16

Answer: (a)

Solution:

= ∫04 �2√ − 4 2� = 16
3

9


15. The complex number z = x + jy which satisfy the equation
| + 1| = 1lie on
a) a circle with (1, 0) as the centre and radius 1
b) a circle with (-1, 0) as the centre and radius 1
c) y – axis
d) x – axis
Answer: (b)
Solution:
The general equation of circle is given by |Z ‒ Z0| = r
Where Z0 is center &radius is r
Now the equation of the given circle is |z + 1| = 1
(or) |z‒ (‒1)| =1
⸫ center = (‒1, 0) and radious = 1

16. Consider the problem of connecting 19 lamps to single
electric outlet by using extension cords each of which has
four outlets. The number of extension cords required is_____
Answer: 6
Solution:
Since any such connection is a quaternary tree with the
signal outlet connected to the root of the tree, according to
equation.
(m – 1) i = t ‒ 1
(4 – 1) i = 19 ‒ 1
3i = 18
i=6

10


That is although there are many ways to connect the lights,

six extinction cords are always needed.

17. 8085 microprocessor has ______ hardware interrupts.

Answer: (5)

Solution:

The 8085 has eight software interrupts from RST 0 to RST 7

and has five hardware interrupts: TRAP(RST 4.5), RST

7.5,RST 6.5, RST 5.5 and INTR.

18. IP address in B class is given by:

a) 125.123.123.2

b) 191.023.21.54

c) 192.128.52.56

d) 10.14.12.34

Answer: (b)

Solution:

Class 1st octal binary 1st octal binary (MSB)

A 1-126 0

B 128-191 10

C 192-223 110

D 224-239 1110

E 240-255 1111

Therefore, only 191. 023.21.54 belongs to class B.

11


19. A ripple counter is a (n):
a) Synchronous Counter
b) Asynchronous counter
c) Parallel counter
d) None of the above
Answer: (b)
Solution:
A ripple counter is an asynchronous: counter where only
the first flip flop is clocked by an external clock .all
subsequent flip-flop are clocked by the output of the
preceding flip-flop Asynchronous counter are also called
ripple-counter because of the way the clock pulse ripple its
way thought the flip-flop

20. What will be the value of I for the following expression?
int i = 11, i = 3',
i+ = (f > 3)? i & 2:5;

a) 2
b) 5
c) 13
d) 12
Answer: (b)
Solution:
Given, int f = 11, i = 3;
i+ = (f > 3)? i 8 & 2:5;
⟹ i+ = (f > 3)? i & 2:5

12


⟹ i+ = (11 > 3)? i & 2:5
⟹ i+ = (11 > 3)? is true so i + = i & 2
⟹ i+ = 1011 & 0010 which is 2
So i+ = 2
⟹i=i+2=3+2=5
21. Which methods are utilized to control the access to an
object in multi-threaded programming?
a) Synchronized methods
b) Synchronized methods
c) Serialized methods
d) None of the above
Answer: (b)
Solution:
Synchronization methods enable a sample strategy for
preventing thread interface and memory consistency errors
22. A complete binary tree with n non-leaf nodes contains____
Answer: 2n + 1 node
Solution:
In complete binary tree
Number of internal nodes = No. of leaf node -1
So total number of nodes = internal nodes + leaf nodes

=n+n+1
= 2n + 1
Internal node = 3
Leaf node = 4

13


Total node = 3 + 4 = 7

23. Given an arbitrary non-deterministic finite automaton
(NFA) with N states, the maximum number of states in an
equivalent minimized DFA is at least.
a) N2
b) 2N
c) 2N
d) N!
Answer: (b)
Solution:
The number of states in the DFA is M
Where:1 ≤ M ≤ 2N

24. Which one of the following is FALSE?
a) There is a unique minimal DFA for every regular
language
b) Every NFA can be converted to an equivalent PDA
c) Complement of every context free language is recursive
d) Every non deterministic PDA can be converted to an
equivalent deterministic PDA.
Answer: (d)
Solution:
Every NFA is automatically a PDA. However non-
determinism gives extra power to the PDA. So non-

14


deterministic PDA cannot be converted to a deterministic
PDA For example L = {wwR | w (a + b)*} can be
recognized by a NPDA but not by a DPDA.
25. The shift operator E is defined as E[f(xi)] = f(xi + h) and E
‒ 1[(xi)] = f (xi ‒ h) Then ∆ (forward difference) in terms of
E is_______
Answer: E + 1
Solution:
Forward difference operator = ∆
∆(f(x)) = f(x + h) ‒ f(x) [we know that]
Ef(x)) = f(x + h)
Ef(x)) = f(x + h) ‒ f(x) + f(x) [add or subtract f(x)]

= (1 + ∆) f(x)
So comparing E (f(x)) = (1 + ∆) f(x)

E=1+∆
∆=E+1
26. Consider the languages L1 = ɸ and L2 = {1} which one of
the following represents L1* ∪ L2* L1*?
a) {ϵ}
b) {ϵ, 1}
c) ɸ
d) 1*
Answer: (d)
Solution:
L1 = ɸ and L2 = {1}

15


So, L1*L2*L1* = L1* +L2*L1*
= ɸ * + (1)* ɸ * = ∈ + (1)* = (1)*

27. How many tokens will be generated by the scanner for the

following statement?

X = x*(a + b) ‒ 5;

a) 12

b) 11

c) 10

d) 07

Answer: (a)

Solution:

Given expression is: x = x*(a + b) ‒ 5;

Total number of tokens that will be generated are for;

(1) × (2) =

(3) × (4) *

(5) C (6) a

(7) + (8) b

(9) ) (10) –

(11) 5 (12);

28. The primary job of operating system is to

a) command resources

b) manage resources

c) provide utilities

d) be user friendly

Answer: (b)

16


29. Consider a system having "n" resources of same type.
These resources are shared by 3 processes, A, B, C. These
have peak demands of 3, 4, and 6 respectively. For what
value of "n" deadlock won't occur
a) 15
b) 9
c) 10
d) 13
Answer: (d)
Solution:
A BC
2 35
Now if we gave one more resource to any one of the process
will ensure, there is no deadlock.
i.e., 2 + 3 + 5 = 11
Since 11 is not present, so we go for next higher value i.e,13

30. Abstraction' is ______ step of attribute in a software design.
Answer: First
Solution:
Abstraction: abstraction is the process or result of
generalization by reducing the information content of a
concept or an observable phenomenon, typically in order to
retain only information which is relevant for a practical
purpose.

17


In his object model, Grady booch mentions abstraction,
encapsulation, modulation and hierarchy as fundamental
design principal where abstraction is the first step of
attribute in software design.
31. Analysis of large database to retrieve information is called:
a) OLTP
b) OLAP
c) OLDP
d) TLPP
Answer: (b)
Solution:
Online analytical processing or OLAP is an approach to
answering multi-dimensional analytical (MDA) queries
swift.
The the term OLAP was created as a right modification of
the traditional database term online transaction processing
(OLTP).
32. Which type of DBMS provides support for maintaining
several versions of the same entity?
a) Relational Data Base Management Systems
b) Hierarchical
c) Object Oriented Data Base Management Systems
d) Network
Answer: (c)

18


Solution:
Object oriented Database Management System provide
support for maintaining several versions of same entity. An
old version of an object that represents a tested and verified
design should be retained until a new version is tested and
verified.
33. Let R(a, b, c) and S(d, e, f) be two relations in which d is
the foreign key of S that refers to the primary key of R.
Consider the following four operations R and S
I. Insert into R
II. Insert into S
III. Delete from R
IV. Delete from S
Which of the following can cause violation of the referential
integrity constraint above?
a) Both I and IV
b) Both II and III
c) All of these
d) None of these
Answer: (b)
Solution:

R(a, b, c) S(d, e, f)

Since foreign key is present in S so insertion into R does not
cause any problem and deletion from S does not cause any

19


violation. But insertion into S and deletion from R can cause
violation
34. The forms of information that may be sent electronically
are
a) voice
b) data
c) video
d) all of these
Answer: (d)
35. Which of the following divides the high-speed signal into
frequency bands?
a) T-switch
b) Modem
c) Frequency-division multiplexer
d) Time-division multiplexer
Answer: (c)

20


Two Mark Questions
36. If the sum of the diagonal elements of a 2 × 2 matrix is -6,
then the maximum possible value of determinant of the
matrix is _______.
Answer: 9
Solution:
Let x and y be the Eigen values of the 2 × 2 matrix A.
Sum of the Eigen values of A = sum of diagonal elements of
A
⇒ x + y = − 6 … … … . . (1)
|A| = Product of the eigen values
⇒ |A| = xy
= x(−6 − x) (from 1)
−6 − 2 = ( )( )
F′(x) = −6 − 2x = 0
⇒ x = −3 is the stationary point
f ′′(x) = −2 < 0
∴ f(x) is maximum at x = − 3.
Hence, the required value= f(−3) = 9
37. The velocity v (in kilometer/minute) of a motorbike which
starts from rest, is given at fixed intervals of time t(in
minutes) as follows:
T 2 4 6 8 10 12 14 16 18 20
V 10 18 25 29 32 20 11 5 2 0

21


The approximate distance (in kilometers) rounded to two

places of decimals covered in 20 minutes using Simpson’s

1/3rd rule is______.

Answer: 308 to 310

Solution:

Required distance = ∫020 v dt

= 2 [(0 + 0) + 4(10 + 25 + 32 + 11 + 2) + 2(18 + 29 + 20 +
3

5)] (by Simpsons 1 rule) = 309.33 km
3

38. The security system at an IT office is composed of 10

computers of which exactly four are working. To check

whether the system is functional, the officials inspect four of

the computers picked at random (without replacement). The

system is deemed functional if at least three of the four

computers inspected are working. Let the probability that the

system is deemed functional be denoted by p. Then 100p =

______.

Answer: 11.9

Solution:

P = probability of picking ‘3’ working computer or ‘4’

working computers.

= 4C3 6C1 + 4C3 = 25
10C4 10C4 210

∴ Required value =100p =100 × 25 = 11.9
210

22


39. The third term in the Taylor’s series expansion of ex about

'a' would be _______

Answer: ea (x − a)2
2

Solution:

By Taylor’s series expansion,

ex = ea + (x − a)ea + (x−a)2 ea + ⋯……
2!

Third term is (x−a)2 f ′′(a) = ea (x − a)2
2! 2

40. The complex number z = x + j y which satisfy the equation

|z +1| = 1 lie on

a) a circle with (1, 0) as the centre and radius 1

b) a circle with (‒1, 0) as the centre and radius 1

c) y-axis

d) x-axis

Answer: (b)

Solution: -
The general equation of circle is given by |z − Z0| = r

Where Z0 is center & radius is r

Now the equation of the given circle is |z + 1| = 1

(or)
|z − (−1)| = 1
∴ Center = (−1, 0) and radius = 1

23


41. A RAM chip has a capacity of 1024 words of 8 bits each

(1K × 8). The number of 2 × 4 decoders with enable line

needed to construct a 16K × 16 RAM from 1K × 8 RAM

is______

Answer: 5

Solution:
Basic capacity = 1 K × 8

Target size = 16K × 16

Total number of chips needed = 16 ×16 =16×2
1 ×8

Number of rows = 16 with 2 chips per row and both chips

get enable with single decoder output.

Number of decoders needed = 1 master + 4 slaves.

So total = 5

42. Consider the expression (a – 1) × (((b + c)/3) + d). Let X be

the minimum number of registers required by an optimal

code generation (without any register spill) algorithm for a

load/store architecture, in which (i) only load and store

instructions can have memory operands and (ii) arithmetic

instructions can have only register or immediate operands.

The value of X is_____.

Answer: 2

Solution:
Expression is (a ‒1) × (((b + c)/3) + d)
Load R1, b (R1 ← b)
Load R2, c (R2 ← c)

24


ADD R1, R2 (R1 ← b + c)
DIV R1, �3 1 ← � +3 ��
Load R2, d (R2 ← b)

ADD R1, R2 � 1 ← � +3 + ��
Load R2, d (R2 ← a)
Dec R2 (R2 ← a – 1)

MUL R1, R2 (final result is available in R2)

STORE R2 on memory

→ only R1 and R2 registers are sufficient to evaluate the

expression.

43. The attributes of three arithmetic operators in some

programming language are given below.

Operator Precedence Associativity Arity

+ High Left Binary

– Medium Right Binary

* Low Left Binary

The value of the expression 2 – 5 + 1 – 7*3 In this language

is_____.

Answer: 9

Solution:

2‒5+1‒7*3

2‒6‒7*3

2 ‒ (‒1) * 3

3*3=9

25


44. In a complete k-ary tree, every internal node has exactly k

children. The number of leaves in such a tree with n internal

nodes is:

a) nk

b) (n – 1)k + 1

c) n(k – 1) + 1

d) n(k – 1)

Answer: (c)

Solution:

Let x be the depth of the k-ary tree number on internal nodes

= 1 + k1+ k2 +….+ kx-1 = n ⟹ 1(Kx−1) = n
K−1

⟹ Kx = n(k −1)+1

Number of leaf nodes = Kx = n(k − 1) + 1

45. A program attempts to generate as many permutations as

possible of the string 'abcd' by pushing the characters a, b, c,

d in the same order onto a stack, but it may pop off the top

character at any time. Which one of the following strings

CANNOT be generated using this program?

a) abcd

b) dcba

c) cbad

d) cabd

Answer: (d)

26


Solution:
We have to push the characters on to the stack in the order
'a', 'b', 'c', 'd'.
We may perform pop operation at any time between those
push operations.

Choice (a) Choice (b)
Program to generated abcd; ‘bcda’
Push ‘a’
Push ‘a’ Push ‘b’
Pop ‘a’ Push ‘c’
Push ‘b’ Push ‘d’
Pop ‘b’ Pop ‘d’
Push ‘c’ Pop ‘c’
Pop ‘c’ Pop ‘b’
Push ‘d’ Pop ‘d’
Pop ‘d’
Choice (c)
Choice (d) ‘cabd’
‘cbad’ Push ‘a’
Push ‘b’
Push ‘a’ Push ‘c’
Push ‘b’ Pop ‘c’
Push ‘c’
Pop ‘c’ We can’t pop ‘a’ this time
Pop ‘b’
Pop ‘a’
Push ‘d’
Pop ‘d’

46. In a binary tree, for every node the difference between the

number of nodes in the left and right subtrees is at most 2. If

the height of the tree is h > 0, then the minimum number of

nodes in the tree is

a) 2h – 1

b) 2h – 1 +1

c) 2h – 1

d) 2h

27


Answer: (b)
Solution:
Tree of height 1 having min no. of nodes is

Extra number of nodes added (1)
Tree of hight 2 and having min o of nodes is

Extra number of nodes added (2)
Tree of hight 3 and having min o of nodes is

Extra number of nodes added (3)
Tree of hight 4 and having min o of nodes is

Extra number of nodes added (4)

Tree of hight 5 and having min o of nodes is
Height 1→ 2 nodes
2→ 2+1 nodes
3→ 2+1+2
4→2+1+2+4
5→2+1+2+4+8
Height→2+2h-1 -1
=2h-1+1

47. A complete n-array tree is a tree in which each node has n
children or no children. Let I be the number of internal
nodes and L be the number of leaves in a complete n-array
tree. If L = 41, and I = 10, what is the value of n?
a) 3
b) 4
c) 5
d) 6

28


Answer: (c)
Solution:
Leaves = 41 = L
Internal nodes =10 = L
Given i =10
LI = 41
41n + (10 − 1) (n − 1)
41= 10n – 9 ⟹ 50 = 10n ⟹ n = 5
For an n-ary tree where each node has n children or no
children, following relation holds L = (n – l) × I + 1, where
L is the number of leaf nodes and I is the number of internal
nodes. Let us find out the value of n for the given data:
L = 41, I = 10 ⟹ 41 = 10 × (n − 1) + 1 = 5
48. Let P be a singly linked list, Let Q be the pointer to an
intermediate node x in the list. What is the worst - case time
complexity of the best - known algorithm to delete the node
x from the list is____
Answer: O (n)
Solution:
In order to delete an intermediate node x, we need a pointer
to the node behind it. We have to traverse from starting node
to the node behind required node. So, worst case complexity
is O (n)

29


49. An advantage of chained hash table (external hashing) over
the open addressing scheme is_____
Answer: deletion is easier
Solution:
Advantage of chained hash table over open addressing
Space used is less FALSE (link maintained ⇒ more space)
(∵ In open addressing after deleting an element, then
rearrangement of elements is necessary. But no need in
chaining)
In separate chaining we search for the element to be deleted
in linked list of hashed key. Since they are in linked list
form, it is easy to delete. The search operation is not very
efficient in this case. Also, space used for this not less due to
the fact that linked list nodes need extra space for pointers.

50. The length of the path from v5 to v6 in the MST of previous
question with n = 10 is:
a) 11
b) 25
c) 31
d) 41
Answer: (c)

30


Solution:

V5 → V6 :(V5 – V3 – V1 – V2 – V4 – V6)

31

V5 → V6=31
51. The Finite state machine described by the following state

diagram with A as starting state, where an arc label is x/y
and x stands for l-bit input and y stands for 2-bit output.

31


a) Outputs the sum of the present and the previous bits of
the input.

b) Outputs 01 whenever the input sequence contains 11
c) Outputs 00 whenever the input sequence contains 10
d) None of the above
Answer: (a)
Solution:
If input is 10, output is 01 = 1 + 0 = 01.
If input is 110, output is 01 = 1 + 0.
If input is 111, output is 10 = 1 + 0.
52. Consider the grammar
S → (S) | a
Let the number of states in SLR(1), LR(1) and LALR (1)
parsers for the grammar be n1, n2 and n3 respectively. The
following relationship holds good
a) n1 < n2 < n3
b) n1 = n3 < n2
c) n1 = n2 = n3
d) n1 ≥ n2 ≥ n3
Answer: (b)
Solution:
The number of states of deterministic finite automata in SLR
(1) and LALR (1) parsers are equal so n1 = n3. The number
of states of deterministic finite automata in LR (l) or

32


canonical LR is greater than number of states of
deterministic finite automata of SLR (1) and LALR(1).
Hence n1 = n3 < n2
Common Data for Questions 53 and 54
Consider the following expression grammar. The semantic
rules for expression evaluation are started next to each
grammar production.

E → number E. val = number. val
|E ’+’ E E(1).val = E(2).Val + E(3).val
|E ’×’ E E(1).val = E(2).Val + E(3).val
53. Consider the basic block given below.
a=b+c
c=a+d
d=b+c
e=d–b
The minimum number of nodes and edges present in the
DAG representation of the above basic block respectively
are
a) 6 and 6
b) 8 and 10
c) 9 and 12
d) 4 and 4
Answer: (b)

33


Solution:

A=b+c
C=a+b
D=b+c
E=d−b
A=e+d
Number of nodes = 8
Number of edges = 10
54. Consider the following C code segment.
For (i = 0; i < n; i++)
{
For (j = 0; j++)
{
if (i% 2)
{
X+ = (4 × j + 5 × i);
Y+ = (7 + 4*j);
}
}
Which one of the following is false?

34


a) The code contains loop-invariant computation
b) There is scope of common sub expression elimination in

this code.
c) There is scope of strength reduction in this code.
d) There is scope of dead code elimination in this code.
Answer: (d)
Solution:
Case (a): i% 2 & 5i are code invariant computations TRUE.
Case (b): 4 * j is a common sub-expression as it occurs
twice. TRUE.
Case (c): By using induction variable elimination strength
reduction can be achieved. TRUE.
Case (d): There is no scope for dead code elimination.
FALSE
55. A unit-processor computer system only has two processes,
both of which alternate 10 ms CPU bursts with 90 ms 110
bursts. Both the processes were created at nearly the same
time. The 110 of both processes can proceed in parallel.
Which of the following scheduling strategies will result in
the least CPU utilization (over a long period of time) for this
system?
a) First come first served scheduling
b) Shortest remaining time first scheduling
c) Static priority scheduling with different priorities for the

two processes

35


d) Round robin scheduling with a time quantum of 5 ms.
Answer: (a)
Solution:
In FCFS, the next job cannot be started unless, the current
one is finished.
56. Which of the following is/are advantages of virtual
memory?
a) Faster access to memory on an average.
b) Processes can be given protected address spaces.
c) Linker can assign addresses independent of where the

program will be loaded in physical memory.
d) Programs large than the physical memory size can be run.
Answer: (b)
Solution:
By concept of virtual memory
57. The root directory of a disk should be placed:
a) At a fixed address in main memory
b) At a fixed location on the disk
c) Anywhere on the disk
d) At a fixed location on the system disk
Answer: (b)
Solution:
To facilitate/minimize the Disk access time.

36


58. Match the pairs in the following question by writing the
corresponding letters only.
List - I
A. Buddy system
B. Interpretation
C. Pointer type
D. Virtual memory
List – II
P. Run-time type specification
Q. Segmentation
R. Memory allocation
S. Garbage Collection
a) A ‒ Q, B ‒ P, C ‒ S, D ‒ Q
b) A ‒ S, B ‒ P, C ‒ S, D ‒ Q
c) A ‒ R, B ‒ P, C ‒ S, D ‒ R
d) A ‒ R, B ‒ P, C ‒ S, D ‒ Q
Answer: (d)

59. A computer system implements 8 kilobyte pages and a 32-
bit physical address space. Each page table entry contains a
valid bit, a dirty bit, three permission bits, and the
translation. If the maximum size of the page table of a
process is 24 megabytes, the length of the virtual address
supported by the system is bits.
Answer: 36

37


Solution:

N number of pages = 24MB? 3B = 8M;

Page Size = 8KB;

Hence VAS = 64GB; VA = 36bits

60. Consider the following CPU processes with arrival times

(in milliseconds) and length of CPU bursts (in milliseconds)

as given below:

Process Arrival Time Burst time

P1 0 7

P2 3 3

P3 5 5

P4 6 2

If the pre-emptive shortest remaining time first scheduling

algorithm is used to schedule the processes, then the average

waiting time across all processes is _____ millisecond.

Answer: 3
Solution: Gantt chart:

P1 P2 P4 P1 P3

0 3 6 8 12 17

Arrival Burst Turn around Waiting
time time Compilation Time(compilation- Time(TA
Process time(TC) T_BT)
P1 0 Time Arrival time)
P2 3 5
P3 5 7 12 12
P4 6
36 3 0

5 17 12 7

28 2 0

Total =12

Average Waiting Time = 12 = 3
4

38


61. A Counting semaphore was initialized to 10. Then 6P
(wait) operations and 4V (Signal) operations were completed
on this semaphore. The resulting value of the semaphore is
________.
Answer: 8
Solution:
Since semaphore value s= 10
6P ⟹ S = S ‒ 6
=4
4V ⟹ S = S + 4
=8

62. A Computer has six tape drives, with n processes
competing for them. Each process may need two drives.
What is the______maximum value of n for the system to be
deadlock free?
Answer: 5
Solution:
If there are 5 processes then at least 1process will get 2 tape
drives out of 6 tape drives. The system is deadlock free.

63. Consider the following relational query on the above
database:
SELECT S.name
FROM Suppliers S
WHERE S.id NOT IN
(SELECT C. sid

39


FROM Catalog C
WHERE C. pid NOT IN
(SELCET P. pid
FROM parts P
WHERE P. color < > ’blue’))
Assume that relations corresponding to the above schema
are not empty. Which one of the following is the correct
interpretation of the above query?
a) Find the names of all suppliers who have supplied a non-

blue part.
b) Find the names of all suppliers who have not supplied a

non-blue part
c) Find the names of all suppliers who have supplied only

blue parts
d) Find the names of all suppliers who have not supplied

only blue parts.
Answer: (a)
Solution:
Inner most query produces P. pid of non-blue parts. Mid
query produces C. cid of blue parts (since it is NOT IN).
Outer query produces S.name of non-blue parts (since it is
NOT IN).

40


64. Consider a LAN with four nodes S1, S2, S3 and S4. Time
is divided into fixed-size slots, and a node can begin its
transmission only at the beginning of a slot. A collision is
said to have occurred if more than one node transmit in the
same slot. The probability of generation of a frame in a time
slot by SI, S2, S3 and S4 are 0.1, 0.2, 0.3 and 0.4,
respectively. The probability of sending a frame in the first
slot without any collision by any of these four stations is
______.
Answer: 0.40 - 0.46
Solution:
All k-stations
For a stations P (1 − P)k
For some stations among K-stations = K.P (1 − P)k-1

S1 S2 S3 S4 (0.6)=0.0336
P 1-P 1-P 1-P (0.6)=0.0756
(0.8) (0.7) (0.6)=0.1296
For S1 (0.1) (0.4)=0.2016
(0.2) (0.7)
For S2 (0.9) 0.4404
(0.8) (0.3)
For S3 (0.9)
(0.8) (0.7)
For S4 (0.9)

Probability for anyone station among S1, S2, S3, S4 to send a
frame without collision = 0.4404.

41


65. Host A is sending data to host B over a full duplex link. A

and B are using the sliding window protocol for flow

control. The send and receive window sizes are 5 packets

each. Data packets (sent only from A to B) are all 1000 bytes
long and the transmission time for such a packet is 50 sec.

Acknowledgement packets (sent only from B to A) are very

small and require negligible transmission time. The
propagation delay over the link is 200 sec. What is the

maximum achievable throughput in this communication

is_______ bps

Answer: 11.11 × 106

Solution:

(No options correct since in options bps is given not in Bps)

L = 1000 bytes
Transmission delay = 50μ sec
Propagation delay = 200μ sec

Window size = 5 packets

RTT = Transmission delay + (2 × propagation delay)

= 450 sec

Throughput = 1


= 5×1000
450

= 11.11 × 106 Bps

42


Data Loading...