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 T

_{1}and T_{0}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 T

_{1}and T_{2}are given as
T

_{1}: r_{1}(X)w_{1}(X)r_{1}(Y)w_{1}(Y)
T

_{2}: r_{2}(Y)w_{2}(Y)r_{2}(Z)w_{2}(Z)
where r

_{i}(V) denotes a read operation by transaction T_{i}on a variable V and w_{i}(V) denotes a write operation by transaction T_{i}on a variable V. The total number of conflict serializable schedules that can be formed by T_{1}and T_{2}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
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 ...............

Answer: 7.0

47. If
the ordinary generating function of a sequence

then a

_{3}-a_{0}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 2

^{32}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.

#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 ..................

Answer: 0

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

Answer: 2.0