GATE 1994

 Question 1

FORTRAN implementation do not permit recursion because

 A they use static allocation for variables B they use dynamic allocation for variables C stacks are not available on all machines D it is not possible to implement recursion on all machines
Question 1 Explanation:
FORTRAN implementation do not permit recursion because they use the static allocation for variables.
→ 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?

 A AA′ = 1 B A = A-1 C AB = BA D (AB)' = BA
Question 2 Explanation:
 Question 3

Backward Euler method for solving the differential equation dy/dx = f(x,y) is specified by, (choose one of the following).

 A yn+1 = yn + hf(xn, yn) B yn+1 = yn + hf(xn+1, yn+1) C yn+1 = yn-1 + 2hf(xn, yn) D yn+1 = (1 + h) f(xn+1, yn+1)
Question 3 Explanation:
dy/dx = f(x,y)
With initial value y(x0) = y0. Here the function f and the initial data x0 and y0 are known. The function y depends on the real variable x and is unknown. A numerical method produces a sequence y0, y1, y2, ....... such that yn approximates y(x0 + nh) where h is called the step size.
→ The backward Euler method is helpful to compute the approximations i.e.,
yn+1 = yn + hf(x n+1, yn+1)
 Question 4

Let A and B be any two arbitrary events, then, which one of the following is true?

 A P(A∩B) = P(A)P(B) B P(A∪B) = P(A) + P(B) C P(A|B) = P(A∩B)P(B) D P(A∪B) ≤ P(A) + P(B)
Question 4 Explanation:
(A) Happens when A and B are independent.
(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

 A it makes it more difficult to verify programs B it increases the running time of the programs C it increases the memory required for the programs D it results in the compiler generating longer machine code
Question 5 Explanation:
If we use "goto" statements then it leads to structural decomposition of code then it is difficult to verify the programs.
 Question 6

The number of distinct simple graphs with upto three nodes is

 A 15 B 10 C 7 D 9
Question 6 Explanation:
 Question 7

The recurrence relation that arises in relation with the complexity of binary search is:

 A T(n) = T(n/2) + k, k a constant B T(n) = 2T(n/2) + k, k a constant C T(n) = T(n/2) + log n D T(n) = T(n/2) + n
Question 7 Explanation:
In binary search, search for the half of the list and constant time for comparing. So,
∴ 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:

 A B C D E None of the above.
Question 8 Explanation:
 Question 9

The tank of matrix is:

 A 0 B 1 C 2 D 3
Question 9 Explanation:
 Question 10

Some group (G,o) is known to be abelian. Then, which one of the following is true for G?

 A g = g-1 for every g ∈ G B g = g2 for every g ∈ G C (goh)2 = g2oh2 for every g,h ∈ G D G is of finite order
Question 10 Explanation:
Associate property of a group (aob)oc = ao(boc)
For Abelian group, commutative also holds
i.e., (aob) = (boa)
Consider option (C):
(goh)2 = (goh)o(gog)
= (hog)o(goh)
= (ho(gog)oh)
= ((hog2)oh)
= (g2oh)oh
= g2o(hoh)
= g2oh2 [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, non-zero 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:

 A i + j B i + j - 1 C j + i(i-1)/2 D i + j(j-1)/2
Question 11 Explanation:
Though not mentioned in question, from options it is clear that array index starts from 1 and not 0.
If we assume array index starting from 1 then, ith row contains i number of non-zero elements. Before ith row there are (i-1) rows, (1 to i-1) and in total these rows has 1+2+3......+(i-1) = i(i-1)/2 elements.
Now at ith row, the jth 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(i-1)/2
 Question 12

Generation of intermediate code based on an abstract machine model is useful in compilers because

 A it makes implementation of lexical analysis and syntax analysis easier B syntax-directed translations can be written for intermediate code generation C it enhances the portability of the front end of the compiler D it is not possible to generate code for real machines directly from high level language programs
Question 12 Explanation:
In Intermediate code optimizations can also enhances the probability of optimizer.
 Question 13

A memory page containing a heavily used variable that was initialized very early and is in constant use is removed when

 A LRU page replacement algorithm is used B FIFO page replacement algorithm is used C LFU page replacement algorithm is used D None of the above
Question 13 Explanation:
In FIFO, whichever comes first that can be removed first. If the variable was initialized very early, it is in set of first pages. So it was removed.
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?

 A 3, 4, 5, 1, 2 B 3, 4, 5, 2, 1 C 1, 5, 2, 3, 4 D 5, 4, 3, 1, 2
Question 14 Explanation:
Push 1 Push 2 Push 3 Pop 3 Push 4 Pop 4 Push 5 Pop 5 Pop 2 Pop 1.
→ 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

 A n B n2 C n(n-1)/2 D n(n+1)/2
Question 15 Explanation:
No. of substrings of length
n = 1
(n-1) = 2
(n-2) = 3
So, Total = n(n+1)/2
 Question 16

Which of the following conversions is not possible (algorithmically)?

 A Regular grammar to context free grammar B Non-deterministic FSA to deterministic FSA C Non-deterministic PDA to deterministic PDA D Non-deterministic Turing machine to deterministic Turing machine
Question 16 Explanation:
NPDA to DPDA conversion is not possible. They have different powers.
 Question 17

Linked lists are not suitable data structures of which one of the following problems?

 A Insertion sort B Binary search C Radix sort D Polynomial manipulation
Question 17 Explanation:
In linked list finding an element take O(n) which is not suitable for the binary search. And time complexity of binary search is O(log n).
 Question 18

Which of the following features cannot be captured by context-free grammars?

 A Syntax of if-then-else statements B Syntax of recursive procedures C Whether a variable has been declared before its use D Variable names of arbitrary length
Question 18 Explanation:
Context free grammars are used to represent syntactic rules while designing a compiler.
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.
There are 18 questions to complete.

Register Now