Grand Test - 1 - PDF Flipbook

Grand Test - 1

300 Views
90 Downloads
PDF 4,748,882 Bytes

Download as PDF

REPORT DMCA


GATE
CSE

GrandTests

Test-01Solutions


APTITIDE
One Mark Questions

1. 25 persons are in a room 15 of them play hockey 17 of them
play football and 10 of them play both hockey and football.
Then the number of persons playing neither hockey nor
football is:
a) 2
b) 17
c) 13
d) 3
Answer: (d)
Solution:

10 5 7 Foot ball players

Hockey players

For above the logical Venn diagram shows as follows
Total No.of players
Total No.of persons = hockey only + foot ball only + both
hockey and foot ball only = 5 + 10 + 7 = 22
Total number of persions = 25
∴ Neither hackey or food ball players = total number of
players = 25 – 22 = 3

1


2. What is the value of x when 81 × �1256� +2 + �53�2 +4 = 144?
a) 1

b) –1

c) –2

d) Cannot be determined

Answer: (b)

Solution:

81× �2165� +2 + �53�2 +4 = 144

=�1265� +2 144
81
�53�2 +4

= (12)2
(9)2

= �192�2

=�2165� +2 �192�2

�53�2 +4

(4)2 +4 × (5)2 +4 = �192�2
(5)2 +4 (3)2 +4

(4)2 +4 = �192�2= �43�2
(3)2 +4

�34�2 +4 = �34�2

2x + 4 = 2

2x = –2

X=–1

2


3. The name of the Sloane Matthew Library has long been
________; even longtime city residents assume it is a run-of-
the-mill library, never suspecting what art treasures it
contains.
a) revered
b) proposed
c) misleading
d) elevated
Answer: (c)

4. The famous Notre Dame cathedral in Paris took almost two
hundred years to complete; this immense architectural effort
included the first notable use of a flying ________, but this
renowned feature was not part of the original design and only
employed when the walls forming the nave began to crumble
and needed additional support.
a) Ballast
b) Albatross
c) Hallmark
d) Buttress
Answer: (d)

3


5. Modern tennis fans have come to realize that, although,
quantum technological leaps in racquet technology have lead
to _______ increases in the speed and power with which
players can hit the ball, this has not necessarily lead to a more
entertaining game.
a) innocuous
b) halcyon
c) malleable
d) commensurate
Answer: (d)
Solution:
The sentence states that increases in technology have led to
increases in speed and power. The blank, therefore, requires
something along the lines of similar or proportional. Only
commensurate fits. The answer is choice (D).

4


Two Mark Questions

6. Choose the word which is most similar in meaning to the
word printed in bold.
Piquant
a) Gratified
b) Interesting
c) Sluggish
d) Indolent
Answer: (b)
Solution:
Meaning:
1. Agreeably pungent or sharp in taste
2. Agreeably stimulating, interesting or attractive
Example: Grandma’s home-made gravy is zesty and piquant
Someone who's piquant engages you with charm and wit.
Synonyms: Racy, Pungent, Tangy, Interesting, Flavorful
Antonyms: Bland, Clean, Flavorless, Dull, Tasteless

7. Two buses start from a bus terminal with a speed of 20 km/h
at interval of 10 minutes. What is the speed of a man coming
from the opposite direction towards the bus terminal if he
meets the buses at interval of 8 minutes?
a) 3 km/h
b) 4 km/h
c) 5 km/h
d) 7 km/h

5


Answer: (c)
Solution:
Let Speed of the man is x kmph.
Distance covered in 10 minutes at 20 kmph = distance
covered in 8 minutes at (20 + x) kmph.
Or, 20 ×10/60 = 8/60(20 + x)
Or, 200 = 160 + 8x
Or, 8x = 40
Hence, x = 5kmph
8. In the sentence given below a part is underlined, Choose the
most suitable option that can replace the underlined part. It is
highly desirable that you furnish evidence of your
expenses before you submit your final accounts.
a) It is highly desirable that you furnish evidence of your

expenses.
b) It is highly desirable that you should furnish evidence of

your expenses.
c) It is highly to be desired that you furnish evidences of your

expenses.
d) You must furnish evidence of your expenses.
Answer: (a)
9. A name adopted by an author in his writings
a) Nickname
b) Pseudonym
c) Nomenclature

6


d) Title
Answer: (b)
10. In the question below, complete the sentences with the
appropriate choice. Sometimes late at night Sharon would
gaze joyfully at her children as they slept and ______ in their
innocence.
a) sneer
b) ostracize
c) revel
d) repudiate
Answer: (c)
Solution:
To revel (v.) is to take great pleasure or delight.

7


TECHNICAL

One Mark Questions

11. How many solutions does the following system of linear

equations have

−x + 5y = −1
x−y=2

x + 3y = 3

a) Infinitely many

b) Two distinct solutions

c) Unique

d) None

Answer: (c)

Solution:

1 −5 1 1 −5 1 1 5 1
(A|B) = �1 −1� 2� ~ �0 4 � 1� ~ �0 4� 1�

1 3 3 0 8 2 0 00

ρ(A) = 2 = ρ(A|B) = 2 &number of unknowns = n

=2
Here ρ(A) = ρ(A|B) = n = 2

∴Unique solution exists.

12. If f(x + iy) = x3 – 3xy2 +i ( x,y) where i =√−1 and f(x + i y),
is an analytic functionthen (x, y) is
a) y3 – 3x2y
b) 3x2y – y3
c) x4 – 4x3y
d) xy – y2

8


Answer: (b)

Solution:

f(x + iy) = (x3 ‒ 3xy2) + iɸ(x, y)
= (x, y) + i ɸ(x, y)

Where (x, y) = x3 ‒ 3xy2

dɸ = ɸx dx + ɸy dy

dɸ = ‒ ydx + x dy

dɸ = ‒ (0 ‒ 6xy) dx + (3x2-3y2) dy

ɸ = + 6 2 + �−3 3 3� +
2

ɸ = 3x2y ‒ y3

13. Consider the function f (x) = (x2 – 4)2 where x is a real

number. Then the function has

a) Only one minimum

b) Only two minima

c) Three minima

d) Three maxima

Answer: (b)

Solution:
f(x) = (x2 ‒ 4)2 where x∈R
f '(x) = 2(x2 – 4)2x = 0⇒ x = 0, 2, -2

f"(x) = 4(3x2 – 4)

f"(0) = ‒16 < 0 f(x) has a maximum at x = 0
′ ′′(′(−22))==3322>>00� ⇒ ( )ℎ = ±2

9


14. We have a set of 3 linear equations in 3 unknowns. 'X ≡ Y'
means X and Y are equivalent statements and 'X ≢ Y' means
X and Y are not equivalent statements.
P: There is a unique solution.
Q: The equations are linearly independent.
R: All Eigen values of the coefficient matrix are non-zero.
S: The determinant of the coefficient matrix is nonzero.
Which one of the following is TRUE?
a) P ≡ Q ≡ R ≡ S
b) P ≡ R ≢ Q ≡S
c) P ≡ Q ≢ R ≡ S
d) P ≢Q ≢ R ≢ S
Answer: (a)
Solution:
If there is a unique solution, then | | ≠ 0
⇒ All eigenvalues of ‘A’ are non-zero and the given
equations are linearly independent.

15. In the solution of the following set of linear equations by
Gauss-elimination using partial pivoting 5 + + 2 = 34,
4 − 3 = 12 10 − + = −4. The pivots for
elimination of x and y are.
a) 10 and 4
b) 10 and 2
c) 5 and 4
d) 5 and -4

10


Answer: (a)
Solution:
According to partial pivoting Gauss-elimination method, the
pivot for elimination of x is the numerically largest coefficient
of x in the given 3 equations.
And the pivot for elimination of y is the numerically largest
coefficient of y in the remaining equations of the given
system.
∴ The pivots for elimination of x and y are 10 and 4.
16. q1, q2, q3, ____qm are n-dimensional vectors with m < n. This
set of vectors is linearly dependent. Q is the matrix with q1,
q2, q3, _____ qm as the columns. The rank of Q is
Answer: (a) less than m
Solution:
Q = [ 1 2 3 ⋯ ] × and m < n
We know that ( ) = number of independent vectors
(rows/columns)
i.e. ( ) ≤
But given that 1 2 3 ⋯ are dependent vectors.
∴ ( ) < (Dependent vectors)
17. Let A = 1111 1010 and B = 0000 1010 be two 8-bit 2's
complement numbers. Their product in 2's complement is
a) 11000100
b) 1001 1100
c) 1010 0101

11


d) 1101 0101
Answer: (a)
Solution:

A = 1111 1010 = ‒ 6
B = 0000 1010 = 10

A × B = ‒ 60
‒ 64 + 4 = ‒ 60
18. In which addressing mode, the effective address of the
operand is generated by adding a constant value to the
content of a register?
a) Absolute mode
b) Indirect mode
c) Immediate mode
d) Index mode
Answer: (d)
Solution:
Index addressing mode:
Effective address = [Base address + Displacement]
19. Dijkstra's algorithm is based on 3 is____
Answer: Greedy Approach
Solution:
Dijkstra’s algorithm based on greedy approach
20. An example of a connective which is not associative is:
a) AND
b) OR

12


c) EX-OR
d) NAND
Answer: (d)
Solution:
Associativity: within expression containing two or more of
the same associative connective in a row, the order of the
operations does not matter as long as t5he sequence of the
operands is not changed. Formally, a binary operation *on
set S is called associative if it satisfied the associative law.
(x* y)z = x*(y*z) for all x, y, z in S. AND, OR and EX-OR
associative operators, but NAND is not since,

(x↑ y)↑z ≠ x↑(y ↑ z) ⇒(�� � �∧���� � � )��^� � v ≠ � � ^��(�� � ^��� � � �)
⟹ (x ^ y)⋁ � ≠ ̅ ⋁(y^ z)

21. C++ actually supports the following two complete dynamic
systems:
a) One defined by C++ and the other not defined by c.
b) One defined by C and one specrfic to C++
c) Both are specrfic to C++
d) Both of them are improvements of C
Answer: (b)
Solution:
C++ actually supports two complete dynamic allocation
systems; the one defined by c and the one specific to C++.
The system specific to C++ contain several improvements
over that

13


22. Recursive functions are executed in a
a) First in first out-order
b) Last in first out-order
c) Parallel fashion
d) Load balancing
Answer: (b)
Solution:
A recursive function is a function which itself or is in a
pointed cycle of function calls stack is ordered list of similar
data types, Stack is a last in first out(LIFO) structure .Stacks
are an important way of supporting nested or function calls.

23. Let T (n) be defined by T(1) = 10 and T(n + 1) = 2n + T(n)
for all integers n ≥ 1. Which of the following represents the
order of growth of T (n) as a function of n?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(n3)
Answer: (b)
Solution:
T (n +1) = T (n) + 2n
= T (n ‒ 1) + 2(n ‒ 1) + 2n
= T (n ‒ 2) + 2(n ‒ 2) + 2(n ‒ 1) + 2n
;
;

14


= T (1) + 2[n + (n ‒1) + (n ‒ 2) +…1]
= 10 + 2 ( 2 +1) = O (n2)
24. Symbol Table can be used for:
a) Checking type compatibility
b) Suppressing duplication of error message
c) Storage allocation
d) All of these
Answer: (d)
Solution:
Symbol table is important data structure created and
maintained by compilers in in order to store information
about the occurrence of various entities such as variable
names, function names, objects, classes, information, etc.,
symbol table is used by both the analysis and synthesis parts
of a compiler
25. If the regular set A is represented by A = (01+1)* and the
regular set 'B' is represented by B = ((01)*1*)* which of the
following is true?
a) A ⊂ B
b) B ⊂ A
c) A and B are incomparable.
d) A = B
Answer: (d)

15


Solution:
Conceptual strategy: “If you have everything in the world and
are given something you still have everything in the world."
Let01 = and 1 = then = { , } andA represents the set
of all strings overΣ.

The set = ((01)∗1∗)∗
= (( + 01)∗( + 1)∗)∗
= ([ + 01) + ( + 01)∗][( + 1)( + 1)∗])∗
= ( + 01 + 1 + ℎ )∗
= (01 + 1)∗ = .

Alternative proof:
The DFA accepting A and B are the same.

26. The set of all Equivalence Classes of a set A of Cardinality C
is_____
Answer: forms a partition of A
Solution:
The set of all equivalence class of a set A of cardinality C
forms a partition of A.

16


27. Which one of the following is TRUE?
a) The language = { | ≥ 0} is regular.
b) The language = { | is prime} is regular.
c) The language L = {w | w has 3k + 1 b’s for some k N
with Σ ={a, b}} is regular.
d) The language L = {ww | w Σ* withΣ = {0, 1}} is
regular.
Answer: (c)
Solution:
L = {W | W has 3k + 1 b's for some k Nwith Σ = {a, b}}
for every value of k, weget thelanguage L with finite
number of b's in a string of a's and b's. Let n = 3k + b.
⇒ L is a language of all strings over the alphabet I: {a, b}
where every string contains exactly n b's, then L is accepted
by finite automata with n + 2states.
⇒ L is a Regular language.

28. Given the following two statements:
A. L = {w | n a (w) = n b is deterministic context free
language, but not linear.
B. L = {an bn} ∪ {an b2n} is linear, but not deterministic
context free language.
Which of the following options is correct?
a) Both (A) and (B) are false.
b) Both (A) and (B) are true.
c) (A) is true, (B) is false.

17


d) (A) is false, (B) is true.
Answer: (c)
Solution:
L= {w| na(w) = nb(w) is DCFL but not linear. TRUE
L= {an bm} ∪ {an ∪b2n} is not linear so false
29. The context-free languages are closed for:
1. Intersection
2. Union
3. Complete
4. Kleene star
a) (i) and (iv)
b) (i) and (iii)
c) (ii) and (iv)
d) (i) and (iii)
Answer: (c)
Solution:
The context free language are closerd under union and
kleene star properties.The context-free languages are not
closed under complement, intersectyion or difference
properties
30. Given two languages:
L1 = {(ab)n ak | v > k, k ≥ 0}
L2 = {an bm | n ≠ m}
Using pumping lemma for regular language, it can be shown
in_______

18


Answer: 1 is not regular and 2 is not regular.
Solution:
Both L1 = {(ab) n ak| n > K, K > 0} and L2 = {an bm | n ≠ m}
are not regular languages, because we cannot do matching in
DFA. Both requires stack, so, both are requires stack. So both
are context free languages but not regular
31. Let L be the language generated by regular expression 0*10*
and accepted by the deterministic finite automata M.Consider
the relation Rm defined by M.As all states are reachable from
the start state, Rm has ____ equivalence classes.
a) 3
b) 4
c) 5
d) 6
Answer: (a)
Solution:
Since we want want equivalence classes and all states are
reacheable from startv states, we must design a minimal
DFA.\First design minimal NFA,

00
1

The converted to DFA by adding a trap,

19


0 0 0, 1
1 1

So, there are 3 equaling classes.
32. Multiprocessor is used because

a) it saves money compared to multiple single systems
b) they increase reliability
c) distributed capability
d) all of these
Answer: (d)
33. A software to create a Job Queue is called____
Answer: Spooler
Solution:
Spooler is software that manages sending jobs to the
printer, when an application prints a document, the
formatted output is stored on disk, and the print spooler
feeds the print images to the printer in the background at
slower printing speed.
Jobs are in the queue.
A link editor is a computer program that takes on e or
more, object files generated y a compiler and combines
them into a single executable size, library file, or another
object file.
An interpreter is a computer program that directly
executes. Driver is a program that controls a device.

20


34. Suppose-x and y are two integer Variables having values
ox5486and ox6lcD respectively the result (in hex) of
applying bitwise operator AND to x and Y will be:
a) Ox50B9
b) Ox4084
c) Ox78A4
d) Ox3AD1
Answer: (b)
Solution:

O×5AB6=0101 1010 1011 0110
O×61CD=011000111001101
AND =0100 0000 1000 0100

=O×4084

35. The entity types on which the _______ type depends is called
the identifying owner.
a) Strong entity
b) Relationship
c) Weak entity
d) E-R
Answer: (c)
Solution:
Weak entity is an entity that alone cannot uniquely identify
its attributes therefore; it must use a foreign key in
conjunction with its attributes to create a primary key. The
foreign key is typically a primary key of an entity it is related
to.

21


Two Marks Questions
36. Let A = [aij], 1≤ i, j ≤ n with n≥3 and aij = i.j. The rank of A

is

a) 0

b) 1

c) n – 1

d) n

Answer: (b)

Solution:

1 2 3 .. n

= �2. 4 6 .. n �
. . .. .
n 2n 3n . . n2

R2 − 2R1, R3 − 3R1, … … Rn − nR1

123..n

~ �0. 0 0 . . 0. �
. . . .

000..0

∴ Rank of ‘A’ = 1

37. How many hosts are attached to each of the local area

network at our site?

a) 128

b) 254

c) 256

d) 64

Answer: (b)

22


38. The smallest and largest Eigen values of the following matrix
3 −2 2

are:�4 −4 6�
2 −3 5

a) 1.5 and 2.5

b) 0.5 and 2.5

c) 1.0 and 3.0

d) 1.0 and 2.0

Answer: (d)

Solution:

The characteristic equation of the given matrix is
− 3 + 4 2 − 5 + 2 = 0

⇒ ( − 2)(− 2 + 2 − 1) = 0

∴ = 2, 1

39. How many of the following matrices have an Eigen value 1?
�10 00� , �00 01� , �11 −11� , �−01 −01�

a) One

b) Two

c) Three

d) Four

Answer: (a)

Solution: 10� , = �11 −11�,

Let = �10 00� , = �00
D = �−01 −01�

23


The Eigen values of A are 1, 0

The Eigen values of B are 0, 0

The Eigen values of C are 1+ i, 1 – i

And the Eigen values of D are –1, –1

∴ Only one of the matrixes A has an Eigen value 1.

40. The value of ∮ 2 , using cauchy’s integral around the
4−1

circle | + 1| = 1 where z = x + i y is______

Answer: −
2

Solution:

I = ∫ 2 = ∫ ( 2 = 1 ∫ � 21−1 + 21+1�
4−1 2−1)( 2+1) 2

I = 12∮ 21−1 + 1 ∮ 1 , | + 1| = 1
2 2+1

I = 1 ∫ 1 + 1 ∫ 1
2 ( −1)( +1) 2 ( − )( + )

Only z = ‒ 1 lies inside C, By Cauchy integral formula

I = 212πi� −1 1� = −1 + 1 2 (0) ⟹I = −
2 2

010
41. The inverse of matrix �1 0 0� is

001

010
a) �1 0 0�

001

0 −1 0
b) �−1 0 0 �

0 0 −1

010
c) �0 0 1�

100

24


0 −1 0
d) � 0 0 −1�
0
−1 0
Answer: (a)

Solution:

The given matrix A can be obtained from the unit matrix with
elementary operation 1 ↔ 2.
The inverse matrix corresponding to the elementary matrix A

is A itself.

42. It is known that two roots of the non-linear equation x3 – 6x2

+ 11x – 6 = 0 are 1 and 3. The third root will be

a) j

b) ‒ j

c) 2

d) 4

Answer: (c)

Solution:

For the equation ax3 + bx2 + cx + d = 0, product of root = d/a
∴ For the give equation let x be the third root = d/a

1×3×x=6

x=2

43. If f(x) is even function and a is a positive real number, then

∫− ( ) equals ______
Answer: 2 ∫0 ( )

25


Solution:

∫− ( ) = �2 ∫0 ( ) ( )
0 ( )

44. Symbol Table can be used for:

a) Checking type compatibility

b) Suppressing duplication of error message

c) Storage allocation

d) All of these

Answer: (d)

Solution:

Symbol Table is important data structure created and

maintained by compiler in order to store information about

the occurrence of various entities such as variable names,

function names, objects, classes, interfaces, etc, symbol table

is used by both the analysis and synthesis parts of compiler.

45. A priority queue Q is used to implement a stack S that stores

characters. PUSH(C) is implemented as INSERT (Q, C, K)

where K is an appropriate integer key chosen by the

implementation. POP is implemented as DELETEMIN (Q).

For a sequence of operations, the keys chosen are in

a) Non - increasing order

b) Non - decreasing order

c) Strictly increasing order

d) Strictly decreasing order

Answer: (a)

26


Solution:
Keys chosen for sequence of PUSH (C) operations should be
in decreasing order. Because extract-MIN (Q) gives the
character with minimum key value which is recently inserted
character, if keys chosen are in decreasing order.
Keys (two or more successive) may be same. Because, when
we perform pop operation, we are deleting the key inserted.
By tracking deletions, we can allow same key values for two
insert operations.
46. Which of the following sequences of array elements forms a
heap?
a) {23, 17, 14,6, 13, 10, 1, 12, 7, 5}
b) {23, 17, 14,6, 13, 10, 1,5, 7, 12}
c) {23, 17, 14, 7, 13, 10, 1,5,6, 12}
d) {23, 17, 14, 7, 13, 10, 1, 12,5, 7}
Answer: (c)
Solution:

27


47. A circularly linked list is used to represent a Queue. A single
variable p is used to access the Queue. To which node should
p point such that both the operations enqueue and dequeue
can be performed in constant time?

a) rear node
b) front node
c) not possible with a single pointer
d) node next to front
Answer: (c)
Solution:
Choice (a): If p points to rear node, we have to traverse back
to the node behind rear node for queue operation. So time
complexity is O(n)
Choice (b): If p points to front node, we need extra pointer to
perform dequeue operation.
Choice (d): If p points to node next to front, we have to
traverse back to perform dequeue operation.
48. In a circular linked list organization, insertion of a record
involves modification of:
a) One pointer
b) Two pointers

28


c) Multiple pointers
d) No pointer
Answer: (b)
Solution:

Two pointers are required as shown above

49. Let LASTPOST, LASTIN and LASTPRE denote the last
vertex visited in a post order, in order and preorder traversal,
respectively, of a complete binary tree. Which of the
following is always true?
a) LASTIN = LASTPOST
b) LASTIN = LASTPRE
c) LASTPRE = LASTPOST
d) None of the above
Answer: (d)
Solution:

Complete Binary tree: LAST IN: 3
LAST PRE: 6
LAST POST: 1

29


50. Let R1 and R2 be regular sets defined over the alphabet Σ
then:
a) R1 ∩ R2 is not regular.
b) R1 ∩ R2 is regular.
c) Σ* - R1 is regular.
d) R1* is not regular.
Answer: (c)
Solution:
Let Σ is any alphabet. Σ∗ is an universal language which is
accepted by a finite Automata. Also R1 is regular language
and Σ∗- R1 is complement of R1, and Σ∗- R1 is also accepted
by Finite Automata. Finite automata for 1 can be obtained
by interchanging final and non-final states from FA of R1.
Hence if R1 regular language then Σ∗- R1 is also regular.

51. The string 1101 does not belong to the set represented by
a) 110*(0 + 1)
b) 1(0 +1)*101
c) (10)*(01)*(00 + 11)*
d) (00 + (11)*0)*
Answer: (c)
Solution:
a) 110*(0 + 1) = 110*0 + 110*1
= 110*0 + 11( + 0 + 0*)1
= 110*0 + 111 + 1101 + 110*1
So, this choice can be ruled out.

30


b) 1(0 + 1)*101 = 1 101 + 1(0 + 1)*101
= 1101 + 1(0 + 1)*101

So, this choice can be ruled out.
c) (10)*(01)*(00 + 11)*
d)

Only this term can contribute 11. After
this term cannot be a single 1. So 1101
is not possible in this regular set.
52. Consider the finite automaton in the following figure.

What is the set of reachable states for the input string 0011?
a) { 0, 1, 2}
b) { 0, 1}
c) { 0, 1, 2, 3}
d) { 3}
Answer: (a)
Solution:

The set of states acceptable to the string w:{ 0, 1, 2}

31


53. Consider the SLR (1) and LALR (1) parsing tables for a
context free grammar. Which of the following statements
is/are true?
a) The go to part of both tables may be different
b) The shift entries are identical in both the tables
c) The reduce entries in the tables may be different
d) The error entries in the table may be different
Answer: (b)
Solution:
The shift entries are identical in both the tables.

54. Which of the following is NOT an advantage of using shared,
dynamically linked libraries as opposed to using statically
linked libraries?
a) Smaller sizes of executable files
b) Lesser overall page fault rate in the system
c) Faster program start up
d) Existing programs need not be re-linked to take advantage
of newer versions of libraries.
Answer: (b)
Solution:
Case (c): The avoidance of static linking leads to less linking
time & faster program start up.
Case (a): The smaller exe file is not an advantage these days
& large memories but the requirement of memory is larger.
Case (b): The page fault rate is an O.S problem.

32


Case (d): The latest versions are linked & this is an

advantage.

55. The grammar S → a S a | b S | c is

a) LL(1) but not LR(1)

b) LR(1) but not LL(1)

c) Both LL(1) and LR(1)

d) Neither LL(1) nor LR(1)

Answer: (c)

Solution:

The LL (1) predictive parsing table is as follows

S1 → S

S → aSa |bS| c

a bc $

S1 - - - S1 → S

S S → aSa S → bS S → c -

As there is no conflict, the grammar is LL (1)

The LR (0) machine as follows:

S → aSa |bS| c

As there are no shift reduce or reduce-reduce conflicts, the
grammar is LR (0), SLR(1), LALR(I) & LR(l).

33


Statement for Linked Answer Questions 56 & 57
For the grammar below, a partial LL(1) parsing table is also
presented along with the grammar. Entries that need to be
filled are indicated as El, E2 and E3. is the empty string, $
indicates end of input, and, | separates alternate right hand
sides of productions.
S → aAbB |b A a B|ℰ
A→S
B→S

ab$
S E1 E2 S → ε
A A → S A → S Error
B B → S B → S E3
56. The above grammar and the semantic rules are fed to a yacc
tool (which is an LALR (1) parser generator) for parsing and
evaluating arithmetic expressions. Which one of the
following is true about the action of yacc for the given
grammar?
a) It detects recursion and eliminates recursion.
b) It detects reduce - reduce conflict, and resolves.
c) It detects shift reduce conflict, and resolves the conflict in
favor of a shift over a reduce action.
d) It detects shift reduce conflict, and resolves the conflict in
favor of a reduce over a shift action
Answer: (c)

34


Solution:
E → number |E’+’ E|E’×’ E

57. Consider the following grammar:
Stmt → if expr then else ecpr; stmt |o
expr → term relop term | term
term → id | number
number → [0 - 9]
Where relop is relational operator (e.g., , ...), o refers to
the empty statement, and if, then, else are terminals.
Consider a program P following the above grammar
containing ten if terminals. The number of control flow
paths in P is _____.
For example, the program
if e1 then e2 else e3 has 2 control flow paths,
e1 → e2 and e1 → e3
Answer: 1024
Solution:
To have 10 if terminals grammar uses stmt → if expr then
expr else expr for 10 times and each of this production has 2
control flow paths.
The 10th if statement has 2 control flow path and from the
9th if statement there are 4 control flow paths and from the
8th if statement there are 8 control flow paths similarly from
the 1st statement there are 1024 control flow Paths.

35


58. A student wrote two context-free grammars G1 and G2 for

generating a single C-like array declaration. The dimension

of the array is at least one. For example,

int a[10][3];

The grammars use D as the start symbol, and use six terminal

symbols int; id [ ] num.

Grammar G1 Grammar G2

D → int L; D → int L;

L → id [e L → id E

E → num] E → E [num]

E → num][E E → [num]

Which of the grammars correctly generate the declaration

mentioned above?

a) Both G1 and G2

b) Only G1

c) Only G2

d) Neither G1 nor G2

Answer: (a)

Solution:

G1: G2:

D→ int L; D → int L;

L → id [e L → id E

E → num] E → E [num]

E → num][E E → [num]

Int a [10] [3];

36


From G1:

D → int L; D → int L;

→ int id [E]; (or) → int a[E]

→ int a[num]; → int a [num][E

→ int a [num] [num]

→ Int a [10] [3];

From G2:

D → int L;

→ int id E;

→ int a[num];

→ int a [num] [num]

→ int a [10] [3];
∴ Both G1 & G2 generates the string.

int a[10][3];

59. Consider a hard disk with 16 recording surfaces (0-15)

having 16384 cylinders (0-16383) and each cylinder contains

64 sectors (0-63). Data storage capacity in each sector is 512

bytes. Data are organized cylinder-wise and the addressing

format is < cylinder no., surface no., sector no.>. A file of

size 42797 KB is stored in the disk and the starting disk

location of the file is . What is the cylinder

number of the last sector of the file, if it is stored in a

contiguous manner?

a) 1281

b) 1282

37


c) 1283

d) 1284

Answer: (b)

Solution:

File occupies 42797∗1024 sectors = 85594 sector starting
512

number < 1200, 9, 40 >

= 1200 × 64 × 16 + 9 × 64 + 40 = 1229 416

Last sector number = 1229 416 + 85594 = 131 5010 = x

Number of sectors/ cylinder =16 × 64 = 24.26

= 210 = 1024 = y
Cylinder number =� �=�13110520410� =1284

60. Consider an Entity-Relationship (ER) model in which entity

sets E1 and E2 are connected by an m : n relationship R12,

E1 and E3 are connected by a 1 : n (1 on the side of E1 and n

on the side of E3) relationship R13.

E1 has two single-valued attributes a11 and a12 of which a11

is the key attribute. E2 has two single-valued attributes a21

and a22 is the key attribute. E3 has two single-valued

attributes a31 and a32 of which a31 is the key attribute. The

relationships do not have any attributes.

If a relational model is derived from the above ER model,

then the minimum number of relations that would be

generated if all the relations are in 3NF?

38


a) 2
b) 3
c) 4
d) 5
Answer: (c)
61. Consider the following two-process synchronization solution.
Process 0
Entry; loop while (turn == 1);
(Critical section)
Exit: turn = 1;
Process 1
Enter: loop while (turn == 0);
(Critical section)
Exit: turn = 0;
The shared variable turn is initialized to zero. Which one of
the following is TRUE?
a) This is a correct two-process synchronization solution.
b) This solution violates mutual exclusion requirement.
c) This solution violates progress requirement.
d) This solution violates bounded wait requirement.
Answer: (c)
Solution:
If the value of turn is 1 and Process 1 is not interested in CS
then Process 0 cannot enter CS and hence P1 blocks P0
indefinitely.

39


62. The sequence _____ is an optimal non-preemptive

scheduling sequence for the following jobs which leaves the

CPU idle for _____ Unit (s) of time

Job Arrival time Burst Time

1 0.0 9

2 0.6 5

3 1.0 1

Answer: {3, 2, 1}, 1

Solution:

S.J.F is the optimal non-preemptive CPU scheduling

algorithm. SJF is the optimal non-preemptive CPU

scheduling algorithm.

So, in order to produce the optimal Solution here it considers

the shortest job first.

The optimal sequence is {j3, j2, j1}.

Since, Burst time (j3) < Burst time (j2) Burst time (j1) But to

start j3 CPU Should wait for 1.0 units of time as its arrival

time is 1.0.

63. Three processes A, Band C each execute a loop of 100

iterations. In each iteration of the loop, a process performs a

single computation that requires tc CPU milliseconds and

then initiates a single I/O operation that lasts for tio

milliseconds. It is assumed that the computer where the

processes execute has sufficient number of I/O devices and

the OS of the computer assigns different I/O devices to each

40


process. Also the scheduling overhead of the OS is

negligible. The processes have the following characteristics:

Process Id tc ti0

A 100 ms 500 ms

B 350 ms 500 ms

C 200 ms 500 ms

The processes A, B, and C are started at times 0, 5 and 10

milliseconds respectively in a pure time sharing system

(round robin scheduling) that uses a time slice of 50

milliseconds. The time in milliseconds at which process C

would complete its first I/O operation is _____.

Answer: 1000

Solution:

Preparing the Gantt Chart by Context- Switching between

process. A, B, C with a time quantum; First process A

initiates IO operation at time 200 and then process C initiates

IO at time 500 and completing the same at time 1000.

64. How many tuples does the result of the following relational
algebra expression contain? Assume that the schema of A∪B

is the same as that of A is____

(A∪B)⋈ A.Id>40 ⋁C,Id < 15C

Answer: 7

41


Solution:

Apply first cross product then apply filter' Cross product

yields 10 rows, then you play filter A.ID > 40 or C.ID < 15

produces 7 rows.

A∪B ⇒ a.id

12, 15, 25, 98, 99

|x| is cross product followed selection and projection.

{3, 2, 1}, 1

X gives

A.Id B.Id (cross 10 rows Conditions

product)

A.Id B.Id A.Id > 40 V C.Id < 15

5 rows 2 rows 12 10 √

12 99 ×

15 10 √

15 99 ×

25 10 √

25 99 ×

98 10 √

Result 98 99 √

contains 99 10 √

7 rows 99 99 √

42


65. Which one of the following is not a client server application?
a) Internet chat
b) Web browsing
c) E-mail
d) Ping
Answer: (d)
Solution:
PING is utility, to check connectivity either between client-
client or client – server

43


Data Loading...