PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2017 Shift 1

31 If G is grammar with productions
S → SAS | aSb | bSa | SS | ∈
where S is the start variable,
then which one of the following is not generated by G?

1) S → SS → aSbS → abS → abaSb → abab
2) S → aSb → aSaSb → aaaSb → aaab
3) S → SS → aSbS → abS → abaSb → abab → abbSaSa → abbaa
4) can't not drive

32 The value of

33 Consider a database that has the relation schemas EMP (EmpId, EmpName, DepId), and DEPT(DeptName, DeptId). Note that the DepId can be permitted to be NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus.
I. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∀ v ∈ DEPT (t[DeptId] ≠ DeptId]))}
II. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] ≠ DeptId]))}
III. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] = DeptId]))}

Given, DepId can be permitted to be NULL
I. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∀ v ∈ DEPT (t[DeptId] ≠ DeptId]))} : Gives empnames who donot belong to any department
II. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] ≠ DeptId]))} : Gives empnames who donot belong to some department
III. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] = DeptId]))}: Gives empnames who donot belong to same department
All of these queries are giving some results which are finite and thus all are safe expressions.
Therefore, option D is correct.

34 Recall that Belady’s anomaly is that the pages-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?

Statement 1 is “TRUE”. Because there can be a case when page selected to be replaced is by FIFO policy.
Statement 2 is “FALSE”. Because LRU page replacement algorithm does not suffers from Belady’s Anomaly. Only FIFO page replacement algorithm suffers from Belady’s Anomaly.

35 The output of executing the following C program is ____.
# include
int total(int v)
{
static int count = 0;
while (v) {
count += v & 1;
v >>= 1;
}
return count;
}
void main()
{
static int x = 0;
int i = 5;
for (; i> 0; i--) {
x = x + total(i);
}
printf (“%d\n”, x) ;
}

Count in the function total is static.

i	Count	Table i
5	0	2
4	2	3(2+1)
3	3	5(3+2)
2	5	6(5+1)
1	6	7(6+1)
		= 23