 Sample Questions, Previous Year Solved Papers, Study Materials For Competitive Examinations Like UGC NET, SET And GATE Computer Science.

Tuesday, 14 March 2017

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
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
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?
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
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

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
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)
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)
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}
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