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
gY(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 106
bits/sec. The distance between the two hosts is 10,000 km and the propagation
speed along the link is 2 x 108 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) Θ(n2)
(C) Θ(n
logn)
(D) Θ(n2
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) {q0,
q1, q3}
(C) {q0,
q1, q2}
(D) {q0,
q2, q3}
Answer: C
40. Consider
the following languages.
L1
= {ap | p is a prime number}
L2
= {anbmc2m | n≥0, m≥0)
L3
= {anbnc2n | n≥0)
L4
= {anbn | n≥1)
Which of the
following are CORRECT?
I. L1
is context-free but not regular.
II. L2
is not context-free.
III. L3
is not context-free but recursive.
IV. L4
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