GATE 1994
Question 1 
FORTRAN implementation do not permit recursion because
they use static allocation for variables  
they use dynamic allocation for variables  
stacks are not available on all machines  
it is not possible to implement recursion on all machines 
→ Recursion requires dynamic allocation of data.
Question 2 
Let A and B be real symmetric matrices of size n × n. Then which one of the following is true?
AA′ = 1  
A = A^{1}  
AB = BA  
(AB)' = BA 
Question 3 
Backward Euler method for solving the differential equation dy/dx = f(x,y) is specified by, (choose one of the following).
y_{n+1} = y_{n} + hf(x_{n}, y_{n})  
y_{n+1} = y_{n} + hf(x_{n+1}, y_{n+1})  
y_{n+1} = y_{n1} + 2hf(x_{n}, y_{n})  
y_{n+1} = (1 + h) f(x_{n+1}, y_{n+1}) 
With initial value y(x_{0}) = y_{0}. Here the function f and the initial data x_{0} and y_{0} are known. The function y depends on the real variable x and is unknown. A numerical method produces a sequence y_{0}, y_{1}, y_{2}, ....... such that y_{n} approximates y(x_{0} + nh) where h is called the step size.
→ The backward Euler method is helpful to compute the approximations i.e.,
y_{n+1} = y_{n} + hf(x _{n+1}, y_{n+1})
Question 4 
Let A and B be any two arbitrary events, then, which one of the following is true?
P(A∩B) = P(A)P(B)  
P(A∪B) = P(A) + P(B)  
P(AB) = P(A∩B)P(B)  
P(A∪B) ≤ P(A) + P(B) 
(B) Happens when A and B are mutually exclusive.
(C) Not happens.
(D) P(A∪B) ≤ P(A) + P(B) is true because P(A∪B) = P(A) + P(B)  P(A∩B).
Question 5 
An unrestricted use of the “goto” statement is harmful because
it makes it more difficult to verify programs  
it increases the running time of the programs  
it increases the memory required for the programs
 
it results in the compiler generating longer machine code 
Question 6 
The number of distinct simple graphs with upto three nodes is
15  
10  
7  
9 
Question 7 
The recurrence relation that arises in relation with the complexity of binary search is:
T(n) = T(n/2) + k, k a constant  
T(n) = 2T(n/2) + k, k a constant  
T(n) = T(n/2) + log n  
T(n) = T(n/2) + n 
∴ T(n) = 2T(n/2) + k, k a constant
Question 8 
The logic expression for the output of the circuit shown in figure below is:
None of the above. 
Question 10 
Some group (G,o) is known to be abelian. Then, which one of the following is true for G?
g = g^{1} for every g ∈ G  
g = g^{2} for every g ∈ G  
(goh)^{2} = g^{2}oh^{2} for every g,h ∈ G  
G is of finite order 
For Abelian group, commutative also holds
i.e., (aob) = (boa)
Consider option (C):
(goh)^{2} = (goh)o(gog)
= (hog)o(goh)
= (ho(gog)oh)
= ((hog^{2})oh)
= (g^{2}oh)oh
= g^{2}o(hoh)
= g^{2}oh^{2} [True]
Question 11 
In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size n × n, nonzero elements (i.e elements of the lower triangle) of each row are stored one after another, starting from the first row, the index of the (i, j)^{th} element of the lower triangular matrix in this new representation is:
i + j  
i + j  1  
j + i(i1)/2  
i + j(j1)/2 
If we assume array index starting from 1 then, i^{th} row contains i number of nonzero elements. Before i^{th} row there are (i1) rows, (1 to i1) and in total these rows has 1+2+3......+(i1) = i(i1)/2 elements.
Now at i^{th} row, the j^{th} element will be at j position.
So the index of (i, j)^{th} element of lower triangular matrix in this new representation is
j = i(i1)/2
Question 12 
Generation of intermediate code based on an abstract machine model is useful in compilers because
it makes implementation of lexical analysis and syntax analysis easier  
syntaxdirected translations can be written for intermediate code generation  
it enhances the portability of the front end of the compiler  
it is not possible to generate code for real machines directly from high level language programs 
Question 13 
A memory page containing a heavily used variable that was initialized very early and is in constant use is removed when
LRU page replacement algorithm is used  
FIFO page replacement algorithm is used  
LFU page replacement algorithm is used  
None of the above 
In LRU which can eliminate (or) removed which is least recently used.
In LFU the frequency of the page is more. So it is in constant use so cannot be replaced.
Question 14 
Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence 1, 2, 3, 4, 5 in that order?
3, 4, 5, 1, 2  
3, 4, 5, 2, 1  
1, 5, 2, 3, 4  
5, 4, 3, 1, 2 
→ Remaining options are not possible.
Question 15 
The number of substrings (of all lengths inclusive) that can be formed from a character string of length n is
n  
n^{2}  
n(n1)/2  
n(n+1)/2 
n = 1
(n1) = 2
(n2) = 3
So, Total = n(n+1)/2
Question 16 
Which of the following conversions is not possible (algorithmically)?
Regular grammar to context free grammar  
Nondeterministic FSA to deterministic FSA  
Nondeterministic PDA to deterministic PDA  
Nondeterministic Turing machine to deterministic Turing machine 
Question 17 
Linked lists are not suitable data structures of which one of the following problems?
Insertion sort  
Binary search  
Radix sort  
Polynomial manipulation

Question 18 
Which of the following features cannot be captured by contextfree grammars?
Syntax of ifthenelse statements  
Syntax of recursive procedures  
Whether a variable has been declared before its use  
Variable names of arbitrary length 
Syntactic rules not checking the meaningful things such as if a variable is declared before it use (or) not.
Like this, things are handled by semantic analysis phase.