PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2018

36 Consider the following C program:
#include
void fun 1 (char *s1, char *s2) {
char *tmp;
tmp = s1;
s1 = s2;
s2 = tmp;
}
Void fun2 (char **s1, char **s2) {
char *tmp;
tmp = s1;
s1 = s2;
s2 = tmp;
}
int main () {
char *str1 = “Hi”, *str2 = “Bye”;
fun1 (str1, str2);
printf(“%s %s”, str1, str2);
fun2 (&str1, &str2);
printf(“%s %s”, str1, str2);
return 0;
}
The output of the program above is

fun1(char *s1, char *s2)
function scope is local, so the value changed So the affect actual parameters. SO the values will be ‘Hi Bye’.
fun2(char **s1, char **s2)
In this function value is pointer to pointer, so it changes pointer of the actual value. So values will be ‘Bye Hi’

37 Consider the first-order logic sentence
φ ≡ ∃s∃t∃u∀v∀w∀x∀y ψ(s, t, u, v, w, x, y)
where ψ(s, t, u, v, w, x, y) is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality,
but no function symbols. Suppose φ has a model with a universe containing 7 elements.
Which one of the following statements is necessarily true?

∀ are always True and ∃ are always False for empty sets.
So there exists at least one model with universe of size 3 (or less than). Therefore, option (A) is necessarily TRUE.

38 Let G be a simple undirected graph. Let T_D be a depth first search tree of G. Let T_B be a breadth first search tree of G. Consider the following statements.
(I) No edge of G is a cross edge with respect to T_D. (A cross edge in G is between two nodes neither of which is an ancestor of the other in T_D).
(II) For every edge (u, v) of G, if u is at depth i and v is at depth j in T_B, then ∣i − j∣ = 1.
Which of the statements above must necessarily be true?

For statement (II) take counter example of complete graph of three vertices, i.e., K3 with XYZ, where X is source and Y and Z are in the same level. Also, there is an edge between vertices Y and Z, i.e., |i-j| = 0 ≠ 1 in BFS. So, statement became false. Option (A) is correct.

39 The size of the physical address space of a processor is 2^P bytes. The word length is 2^W bytes. The capacity of cache memory is 2^N bytes. The size of each cache block is 2^M words. For a K-way set-associative cache memory, the length (in number of bits) of the tag field is

MM space = 2^P bytes
Physical Address (PA) size = P bits
CM size = 2^N bytes
Block size 2^M words
2^M words*2^W bytes/word
2^M+W bytes
Number of lines = (CM size)/Block size ⇒ 2^N/(2^M+W)
⇒ 2^N-M-W
Number of sets = (Number in cm)/P-way
= 2^N-M-W/K
The Address format

⇒ (N-M-W-log₂K)
∴ Tag size
⇒ P-(N-M-W-log₂K)
⇒ P-N+log₂K)

40 Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.
(I) For an unrestricted grammar G and a string w, whether wϵL(G)
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammar G₁ and G₂, whether L(G₁) = L(G₂)
(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language
Which one of the following statement is correct?

Here the match flowing.
I. Membership problem for RE → undecidable
II. Regularity problem for RE → undecidable
III. Equivalence problem for RE → undecidable
IV. Since DPDA P exists for every nfa N and equivalent to it, this problem is trivially decidable.

PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2018

Follow Us :