Wednesday, 15 March 2017

GATE Computer Science Solved Paper 2017 Session II - Part 5

41.       Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M.
Which of the following decision problems are undecidable?
I. Given a regular expression R and a string w, is w ϵ L(R)?
II. Given a context-free grammar G, is L(G) = Φ?
III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑?
IV. Given a Turing machine M and a string w, is w ϵ L(M)?
(A) I and IV only
(B) II and III only
(C) II, III and IV only
(D) III and IV only
Answer: D
42.       The next state table of a 2-bit saturating up-counter is given below.
The counter is built as a synchronous sequential circuit using T flip-flops. The expressions for T1 and T0 are
Answer: B
43.       Consider the following snippet of a C program. Assume that swap (& x, & y) exchanges the contents of x and y.
int main() {
int array[] = {3, 5, 1, 4, 6, 2);
int done = 0;
int i;
while (done == 0) {
done = 1;
for (i=0; i<=4; i++) {
if (array[i] < array[i+1]) {
swap(&array[i], &array[i+1]);
done = 0;
for (i=5; i>=1; i--) {
if (array[i] > array[i-1]) {
swap(&array[i], &array[i-1]);
done = 0;
printf (“%d”, array[3]);
The output of the program is ...................
Answer: 3.0
44.       Two transactions T1 and T2 are given as
T1: r1(X)w1(X)r1(Y)w1(Y)
T2: r2(Y)w2(Y)r2(Z)w2(Z)
where ri(V) denotes a read operation by transaction Ti on a variable V and wi(V) denotes a write operation by transaction Ti on a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ...............
Answer: 54.0
45.       The read access times and the hit ratios for different caches in a memory hierarchy are as given below.
The read access time of main memory is 90 nanoseconds. Assume that the caches use the referred-word-first read policy and the write back policy. Assume that all the caches are direct mapped caches. Assume that the dirty bit is always 0 for all the blocks in the caches. In execution of a program, 60% of memory reads are for instruction fetch and 40% are for memory operand fetch. The average read access time in nanoseconds (up to 2 decimal places) is ..................
Answer: 4.72

46.       Consider the following database table named top_scorer.
Consider the following SQL query:
SELECT ta.player FROM top scorer AS ta
WHERE ta.goals > ALL (SELECT tb.goals
FROM top_scorer AS tb
WHERE = ‘Spain’)
AND ta.goals >ANY(SELECT tc.goals
FROM top_scorer AS tc
WHERE = ‘Germany’)
The number of tuples returned by the above SQL query is ...............
Answer: 7.0
47.       If the ordinary generating function of a sequence
then a3-a0 is equal to ....................
Answer: 15.0
48.       If a random variable X has a Poisson distribution with mean 5, then the expectation E[(X+2)2] equals ................
Answer: 54.0
49.       In a B+ tree, if the search-key value is 8 bytes long, the block size is 512 bytes and the block pointer size is 2 bytes, then the maximum order of the B+ tree is ...................
Answer: 52.0
50.    A message is made up entirely of characters from the set X={P,Q,R,S,T}. The table of probabilities for each of the characters is shown below:
If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is ..............
Answer: 225.0
51.    Consider the set of processes with arrival time (in milliseconds), CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes have I/O burst time.
The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is ................
Answer: 29.0
52.    If the characteristic polynomial of a 3 x 3 matrix M over R (the set of real numbers) is λ3-4λ2+aλ+30, a ϵ R, and one eigen value of M is 2, then the largest among the absolute values of the eigen values of M is .................
Answer: 5.0
53.    Consider a machine with a byte addressable main memory of 232 bytes divided into blocks of size 32 bytes. Assume that a direct mapped cache having 512 cache lines is used with this machine. The size of the tag field in bits is .............
Answer: 18.0
54.    Consider the following C Program.
int main() {
int m = 10;
int n, n1;
n = ++m;
printf(“%d”, n);
return 0;
The output of the program is ..................
Answer: 0
55.    Consider the following C Program.
int main() {
char* c = “GATECSIT2017”;
char* p = c;
printf(“%d”, (int)strlen(c+2[p]-6[p]-1));
return 0;
The output of the program is .................
Answer: 2.0

Pages   2   3   4   5 

Tuesday, 14 March 2017

GATE Computer Science Solved Paper 2017 Session II - Part 4

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

Pages   2   3   4   5