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

## GATE Computer Science Solved Paper 2017 Session II - Part 5

March 15, 2017
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
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
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 ...................
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 ...............
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 ..................

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 tb.country = ‘Spain’)
AND ta.goals >ANY(SELECT tc.goals
FROM top_scorer AS tc
WHERE tc.country = ‘Germany’)
The number of tuples returned by the above SQL query is ...............
47.       If the ordinary generating function of a sequence
then a3-a0 is equal to ....................
48.       If a random variable X has a Poisson distribution with mean 5, then the expectation E[(X+2)2] equals ................
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 ...................
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 ..............
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 ................
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 .................
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 .............
54.    Consider the following C Program.
#include<stdio.h>
int main() {
int m = 10;
int n, n1;
n = ++m;
n1=m++;
n--;
--n1;
n-=n1;
printf(“%d”, n);
return 0;
}
The output of the program is ..................
55.    Consider the following C Program.
#include<stdio.h>
#include<string.h>
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 .................

Pages   2   3   4   5

## GATE Computer Science Solved Paper 2017 Session II - Part 4

March 14, 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