31.
For any discrete random variable X, with
probability mass function

define the
polyiona1 function

For a
certain discrete random variable Y, there exists a scalar Î² Ïµ [0, 1] such that

g

_{Y}(z) = (1 - Î² + Î²z)^{N}. The expectation of Y is
(A) NÎ²(1 -
Î²)

(B) NÎ²

(C) N(1 - Î²)

(D) Not
expressible in terms of N and Î² alone

Answer: B

32. Consider
the following expression grammar G:

E -> E -
T | T

T -> T +
F | F

F -> (E)
| id

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

(A) E ->
E - T | T

T
-> T + F | F

F
-> (E) | id

(B) E ->
TE’

E’
-> -TE’ | Ïµ

T
-> T + F | F

F
-> (E) | id

(C) E ->
TX

X
-> -TX | Ïµ

T
-> FY

Y
-> +FY | Ïµ

F
-> (E) | id

(D) E ->
TX | (TX)

X
-> -TX | +TX | Ïµ

T
-> id

Answer: C

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

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

(A) Safe,
Deadlocked

(B) Safe,
Not Deadlocked

(C) Not
Safe, Deadlocked

(D) Not
Safe, Not Deadlocked

Answer: B

34. Consider
a binary code that consists of only four valid codewords as given below:

00000,01011,10101,11110

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

(A) p = 3
and q = l

(B) p = 3
and q = 2

(C) p = 4
and q = 1

(D) p = 4
and q = 2

Answer: A

35. Consider
two hosts X and Y, connected by a single direct link of rate 10

^{6}bits/sec. The distance between the two hosts is 10,000 km and the propagation speed along the link is 2 x 10^{8}m/sec. Host X sends a file of 50,000 bytes as one large message to host Y continuously. Let the transmission and propagation delays be p milliseconds and q milliseconds, respectively.
Then the
values of p and q are

(A) p = 50
and q = 100

(B) p = 50
and q = 400

(C) p = 100
and q = 50

(D) p = 400
and q = 50

Answer: D

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

Then the post-order
traversal of this tree is:

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

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

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

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

Answer: B

37. Consider
the C program fragment below which is meant to divide x by y using repeated

subtractions.
The variables x, y, q and r are all

*unsigned int*.
while (r
>= y) {

r = r - y;

q=q + 1;

}

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

x == (y*q + r)?

(A) (q == r)
&& (r == 0)

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

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

(D) (q == 0)
&& (y > 0)

Answer: C

38. Consider
the following C function.

int fun(int
n) {

int
i, j;

for(i
= 1; i <= n; i++) {

for(j = 1; j < n; j += i) {

printf(“%d
%d”,i,j);

}

}

}

Time
complexity of

*fun*in terms of Î˜ notation is
(A) Î˜(n√n)

(B) Î˜(n

^{2})
(C) Î˜(n
logn)

(D) Î˜(n

^{2}logn)
Answer: C

39. Let
Î´ denote the transition function and Î´^ denote the extended transition function
of the Ïµ-NFA whose transition table is given below:

Then Î´^(q2,
aba) is

(A)

*Î¦*
(B) {q

_{0}, q_{1}, q_{3}}
(C) {q

_{0}, q_{1}, q_{2}}
(D) {q

_{0}, q_{2}, q_{3}}
Answer: C

40. Consider
the following languages.

L

_{1}= {a^{p}| p is a prime number}
L

_{2}= {a^{n}b^{m}c^{2m}| n≥0, m≥0)
L

_{3}= {a^{n}b^{n}c^{2n}| n≥0)
L

_{4}= {a^{n}b^{n}| n≥1)
Which of the
following are CORRECT?

I. L

_{1}is context-free but not regular.
II. L

_{2}is not context-free.
III. L

_{3}is not context-free but recursive.
IV. L

_{4}is deterministic context-free.
(A) I, II
and IV only

(B) II and
III only

(C) I and IV
only

(D) III and
IV only

Answer: D

## 0 Comments