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

31.       Let A be n x n real valued square symmetric matrix of rank 2 with
Consider the following statements.
(I) One eigen value must be in [-5, 5]
(II) The eigen value with the largest magnitude must be strictly greater than 5
Which of the above statements about eigen values of A is/are necessarily CORRECT?
(A) Both (I) and (II)
(B) (I) only
(C) (II) only
(D) Neither (I) nor (II)
32.       A computer network uses polynomials over GF(2) for error checking with 8 bits as information bits and uses x3+x+1 as the generator polynomial to generate the check bits. In this network, the message 01011011 is transmitted as
(A) 01011011010
(B) 01011011011
(C) 01011011101
(D) 01011011100
33.       Consider a combination of T and D flip-flops connected as shown below. Tile output of the D flip-flop is connected to the input of the T flip-flop and the output of the T flip-flop is connected to the input of the D flip-flop.
Initially, both Q0 and Q1 are set to 1 (before the 1st clock cycle). The outputs
(A) Q1Q0 after the 3rd cycle are 11 and after the 4th cycle are 00 respectively
(B) Q1Q0 after the 3rd cycle are 11 and after the 4th cycle are 01 respectively
(C) Q1Q0 after the 3rd cycle are 00 and after the 4th cycle are 11 respectively
(D) Q1Q0 after the 3rd cycle are 01 and after the 4th cycle are 01 respectively
34.       If G is a grammar with productions
S→SaS | aSb | bSa | SS | ε
where S is the start variable, then which one of the following strings is not generated by G?
(A) abab
(B) aaab
(C) abbaa
(D) babba
35.       Consider the following two functions.
void fun1(int n) {
if(n == 0) return;
printf(“%d”, n);
fun2(n-2);
printf(“%d”, n);
}

void fun2(int n) {
if(n == 0) return;
printf (“%d”, n);
fun1 (++n);
printf(“%d”, n);
}
The output printed when fun1 (5) is called is
(A) 53423122233445
(B) 53423120112233
(C) 53423122132435
(D) 53423120213243

36.       Consider the C functions foo and bar given below:
int foo(int val) {
int x=0;
while(val > 0) {
x = x + foo(vaI--);
}
return val;
}

int bar(int val) {
int x =0;
while(val > 0) {
x = x + bar(val-1);
}
return val;
}
Invocations of foo (3) and bar (3) will result in:
(A) Return of 6 and 6 respectively.
(B) Infinite loop and abnormal termination respectively.
(C) Abnormal termination and infinite loop respectively.
(D) Both terminating abnormally.
37.       Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals.
G1:S → aSb | T, T → cT | ε
G2:S → bSa | T, T → cT | ε
The language L(G1) ∩ L(G2) is
(A) Finite.
(B) Not finite but regular.
(C) Context-Free but not regular.
(D) Recursive but not context-free.
38.       Consider the following languages over the alphabet ∑= {a, b, c}
Let L1 = {anbncm | m, n ≥ 0} and L2 = { ambncn | m, n ≥ 0}
Which of the following are context-free languages?
I. L1 U L2
II. L1 ∩ L2
(A) I only
(B) II only
(C) I and II
(D) Neither I nor II
39.       Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denote the language {x # f(x) | xεA*}.
Which of the following statements is true?
(A) f is computable if and only if Lf is recursive.
(B) f is computable if and only if Lf is recursively enumerable.
(C) if f is computable then Lf is recursive, but not conversely.
(D) if f is computable then Lf is recursively enumerable, but not conversely.
40.    Recall that Belady’s anomaly is that the page-fault rate may increase as the number of allocated frames increases. Now, consider the following statements:
S1: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady’s anomaly
S2: LRU page replacement algorithm suffers from Belady’s anomaly
Which of the following is CORRECT?
(A) S1 is true, S2 is true
(B) S1 is true, S2 is false
(C) S1 is false, S2 is true
(D) S1 is false, S2 is false