# 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
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);
}
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 .................