Gate1994
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 
Question 1 Explanation:
FORTRAN implementation do not permit recursion because they use the static allocation for variables.
→ Recursion requires dynamic allocation of data.
→ 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 2 Explanation:
Question 3 
Question 3 Explanation:
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) 
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).
(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 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
15  
10  
7  
9 
Question 6 Explanation:
Question 7 
The recurrence relation that arises in relation with the complexity of binary search is:
Question 7 Explanation:
In binary search, search for the half of the list and constant time for comparing. So,
∴
∴
Question 10 
Some group (G, 0) 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 
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):
For Abelian group, commutative also holds
i.e., (aob) = (boa)
Consider option (C):
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  
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, 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
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 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
LRU page replacement algorithm is used  
FIFO page replacement algorithm is used  
LFU page replacement algorithm is used  
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.
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 
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.
→ 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}  
Question 15 Explanation:
No. of substrings of length
n = 1
(n1) = 2
(n2) = 3
So, Total = 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 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?
Insertion sort  
Binary search  
Radix sort  
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 contextfree grammars?
Syntax of ifthenelse statements  
Syntax of recursive procedures  
Whether a variable has been declared before its use  
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.
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.
Question 19 
Which of the following algorithm design techniques is used in the quicksort algorithm?
Dynamic programming  
Backtracking  
Divide and conquer  
Greedy method 
Question 19 Explanation:
In quick sort, we use divide and conquer technique.
Question 20 
In which one of the following cases is it possible to obtain different results for callby reference and callbyname parameter passing methods?
Passing a constant value as a parameter  
Passing the address of an array as a parameter  
Passing an array element as a parameter  
Passing an array following statements is true

Question 20 Explanation:
Passing an array element as a parameter then it gives different output values for the callbyreference and callbyname parameters.
{ ........
a[ ] = {1, 2, 3, 4}
i = 0
fun(a[i]);
print a[0];
}
fun(int x)
{
int i = 1;
x = 8;
}
O/p:
Callbyreference = 8
Callbyvalue = 1
{ ........
a[ ] = {1, 2, 3, 4}
i = 0
fun(a[i]);
print a[0];
}
fun(int x)
{
int i = 1;
x = 8;
}
O/p:
Callbyreference = 8
Callbyvalue = 1
Question 21 
Which one of the following statements is true?
Macro definitions cannot appear within other macro definitions in assembly language programs  
Overlaying is used to run a program which is longer than the address space of computer  
Virtual memory can be used to accommodate a program which is longer than the address space of a computer  
It is not possible to write interrupt service routines in a high level language 
Question 21 Explanation:
A macro body can also have further macro definitions. However, these nested macro definitions aren't valid until the enclosing macro has been expanded. That means enclosing macro must have been called before the macros can be called.
Question 22 
Which one of the following statements is false?
Optimal binary search tree construction can be performed efficiently using dynamic programming.  
Breadthfirst search cannot be used to find converted components of a graph.  
Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.  
Depthfirst search can be used to find connected components of a graph. 
Question 22 Explanation:
In BFS algorithm, we can randomly select a source vertex and then run, after that whether we need to check distance to each and every vertex from source is still infinite (or) not. If we find any vertex having infinite distance then the graph is not connected.
Question 23 
g_{1}(n) is O(g_{2}(n))  
g_{1} (n) is O(^{3})  
g_{2} (n) is O(g_{1} (n))  
g_{2} (n) is O(n)  
Both A and B 
Question 23 Explanation:
In asymptotic complexity, we assume sufficiently large n. So, g_{1}(n) = n^{2} and g_{2}(n) = n^{3}.
Growth rate of g_{1} is less than that of g_{2} i.e., g_{1}(n) = O(g_{2}(n)) = O(n).
Growth rate of g_{1} is less than that of g_{2} i.e., g_{1}(n) = O(g_{2}(n)) = O(n).
Question 24 
either first fit or best fit policy (any one)  
first fit but not best fit policy
 
best fit but first fit policy
 
None of the above 
Question 24 Explanation:
In first fit, block request will be satisfied from the first free block that fits it.
So, request for 300 will be satisfied by 350 size block reducing the free size to 50.
Request for 25, satisfied by 125 size block, reducing it to 125.
Request for 125 satisfied by the 125 size block.
And request for 50 satisfied by 50 size block.
So, all requests can be satisfied.
In best fit strategy, a block request is satisfied by the smallest block in which can fit it. So, request for 300 will be satisfied by 350 size block reducing the free size to 50.
Request for 25, satisfied by 50 size block as its the smallest size that fits 25, reducing it to 25.
Request for 125, satisfied by 150 size block, reducing it to 25.
Now, request for 50 cannot be satisfied as the two 25 size blocks are not contiguous.
So, request for 300 will be satisfied by 350 size block reducing the free size to 50.
Request for 25, satisfied by 125 size block, reducing it to 125.
Request for 125 satisfied by the 125 size block.
And request for 50 satisfied by 50 size block.
So, all requests can be satisfied.
In best fit strategy, a block request is satisfied by the smallest block in which can fit it. So, request for 300 will be satisfied by 350 size block reducing the free size to 50.
Request for 25, satisfied by 50 size block as its the smallest size that fits 25, reducing it to 25.
Request for 125, satisfied by 150 size block, reducing it to 25.
Now, request for 50 cannot be satisfied as the two 25 size blocks are not contiguous.
Question 25 
The number of flipflops required to construct a binary modulo N counter is __________
⌈log_{2} N⌉ 
Question 25 Explanation:
For modN counter we need ⌈log_{2} N⌉ flip flops.
Question 26 
On the set N of nonnegative integers, the binary operation __________ is
associative and noncommutative.
fog 
Question 26 Explanation:
The most important associative operation thats not commutative is function composition. If you have two functions f and g, their composition, usually denoted fog, is defined by
(fog)(x) = f(g(x))
It is associative, (fog)oh = fo(goh), but its usually not commutative. fog is usually not equal to gof.
Note that if fog exists then gof might not even exists.
(fog)(x) = f(g(x))
It is associative, (fog)oh = fo(goh), but its usually not commutative. fog is usually not equal to gof.
Note that if fog exists then gof might not even exists.
Question 27 
Amongst the properties {reflexivity, symmetry, antisymmetry, transitivity} the relation R = {(x,y) ∈ N^{2}  x ≠ y } satisfies __________
symmetry 
Question 27 Explanation:
It is not reflexive as xRx is not possible.
It is symmetric as if xRy then yRx.
It is not antisymmetric as xRy and yRx are possible and we can have x≠y.
It is not transitive as if xRy and yRz then xRz need not be true. This is violated when x=x.
So, symmetry is the answer.
It is symmetric as if xRy then yRx.
It is not antisymmetric as xRy and yRx are possible and we can have x≠y.
It is not transitive as if xRy and yRz then xRz need not be true. This is violated when x=x.
So, symmetry is the answer.
Question 28 
The number of subsets {1, 2, ... n} with odd cardinality is __________
2^{n1} 
Question 28 Explanation:
Total no. of subsets with n elements is 2^{n}.
And so, no. of subsets with odd cardinality is half of total no. of subsets = 2^{n} /n = 2^{n1}
And so, no. of subsets with odd cardinality is half of total no. of subsets = 2^{n} /n = 2^{n1}
Question 29 
The number of edges in a regular graph of degree d and n vertices is _________
d*n/2 
Question 29 Explanation:
Sum of degree of vertices = 2 × no. of edges
d * n = 2 * E
∴ E = d*n/2
d * n = 2 * E
∴ E = d*n/2
Question 30 
P_{2} + P_{3} 
Question 30 Explanation:
P(A∩B') = P(A)  P(A∩B)
P_{3} = P(A)  P_{2}
P(A) = P_{2} + P_{3}
P_{3} = P(A)  P_{2}
P(A) = P_{2} + P_{3}
Question 31 
Consider nbit (including sign bit) 2’s complement representation of integer number. The range of integer values, N, that can be represented is _________ ≤ N ≤ _________
2^{n1} to 2^{n1}  1 
Question 32 
Let A, B and C be independent events which occur with probabilities 0.8, 0.5 and 0.3 respectively. The probability of occurrence of at least one of the event is __________
0.93 
Question 32 Explanation:
P(A∪B∪C) = P(A) + P(B) + P(C)  P(A∩B)  P(B∩C)  P(A∩C) + P(A∩B∩C)
Since all the events are independent, so we can write
P(A∪B∪C) = P(A) + P(B) + P(C)  P(A)P(B)  P(B)P(C)  P(A)P(C) + P(A)P(B) P(C)
= 0.8 + 0.5 + 0.3  0.4  0.5  0.24 + 0.12
= 0.93
Since all the events are independent, so we can write
P(A∪B∪C) = P(A) + P(B) + P(C)  P(A)P(B)  P(B)P(C)  P(A)P(C) + P(A)P(B) P(C)
= 0.8 + 0.5 + 0.3  0.4  0.5  0.24 + 0.12
= 0.93
Question 33 
The Hasse diagrams of all the lattices with up to four elements are __________
(write all the relevant Hasse diagrams).
Question 33 Explanation:
For 1 element:
We can't draw lattice with 1 element.
For 2 element:
For 3 element:
For 4 element:
We can't draw lattice with 1 element.
For 2 element:
For 3 element:
For 4 element:
Question 34 
L=0*1* 
Question 34 Explanation:
L = 0*1*
L contains all binary strings where a 1 is not followed by a 0.
L contains all binary strings where a 1 is not followed by a 0.
Question 35 
True  
False 
Question 35 Explanation:
Note: Out of syllabus.
The major reason of multiplexing address and data bus is to reduce the number of pins for address and data and dedicate those pins for other several functions of microprocessor.
The major reason of multiplexing address and data bus is to reduce the number of pins for address and data and dedicate those pins for other several functions of microprocessor.
Question 36 
True  
False 
Question 36 Explanation:
RISC systems use fixed length instruction to simplify pipeline.
Now the challenge is: How to fit multiple sets of instructions types into limited or fixed size instruction format.
Here comes expanding opcode into the picture, So RISC system uses expanding opcode technique to have fixed size instructions.
Now the challenge is: How to fit multiple sets of instructions types into limited or fixed size instruction format.
Here comes expanding opcode into the picture, So RISC system uses expanding opcode technique to have fixed size instructions.
Question 37 
True  
False 
Question 37 Explanation:
FA or Finite state machine to add two integers can be constructed using two states:
→ q_{0}: Start state to represent carry bit is 0.
→ q_{1}: State to represent carry bit is 1.
The inputs to the FA will be pairs of bits, i.e., 00, 01, 10, 11.
The FA starts in state 1 (since carry is 0) and inputs a pair of bits. If the pair is 11, the FA outputs a '0' and switches to state 2 (since the carry is 1), where the next pair of bits is input and is added to a carry bit of 1.
→ q_{0}: Start state to represent carry bit is 0.
→ q_{1}: State to represent carry bit is 1.
The inputs to the FA will be pairs of bits, i.e., 00, 01, 10, 11.
The FA starts in state 1 (since carry is 0) and inputs a pair of bits. If the pair is 11, the FA outputs a '0' and switches to state 2 (since the carry is 1), where the next pair of bits is input and is added to a carry bit of 1.
Question 38 
Out of syllabus. 
Question 38 Explanation:
(i)  (b), (ii)  (c), (iii)  (d), (iv)  (a)
Question 39 
(i)  (d), (ii)  (a), (iii)  (b), (iv)  (c) 
Question 39 Explanation:
Backus Normal Form (BNF) is a notation technique for context free grammars, often used to describe the syntax of languages used in computing.
Yacc (Yet Another Compiler Compiler) is a computer program for the UNIXoperating system. It is a LALR parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specially a LALR parser, based on an analytic grammar. Yacc is written in portable C.
Yacc (Yet Another Compiler Compiler) is a computer program for the UNIXoperating system. It is a LALR parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specially a LALR parser, based on an analytic grammar. Yacc is written in portable C.
Question 40 
True  
False 
Question 40 Explanation:
BCNF decomposition can always be lossless, but itmay not be always possible to get a dependency preserving BCNF decomposition.
Question 41 
An instance of a relational scheme R(A, B, C) has distinct values for attribute A.
Can you conclude that A is a candidate key for R?
Yes  
No 
Question 41 Explanation:
Because FD's are defined on the schema itself, not the instance. So, based on the state of the instance we cannot say what holds for schema (there can be many instances for R).
Question 42 
Give a relational algebra expression using only the minimum number of operators from (∪, −) which is equivalent to R ∩ S.
Out of syllabus (For explanation see below) 
Question 42 Explanation:
R  (R  S)
→ No need of using Union operation here. → In question they gave (∪, −) but we don't use both.
→ And also they are saying that only the minimum number of operators from (∪, −) which is equivalent to R ∩ S.
So, the expression is minimal.
→ No need of using Union operation here. → In question they gave (∪, −) but we don't use both.
→ And also they are saying that only the minimum number of operators from (∪, −) which is equivalent to R ∩ S.
So, the expression is minimal.
Question 43 
True  
False 
Question 43 Explanation:
Because if a set itself is countable then the subset of set is definitely countable.
Question 44 
Out of syllabus. 
Question 44 Explanation:
(i)  (a), (ii)  (b), (iii)  (d), (iv)  (c)
Question 45 
True  
False 
Question 45 Explanation:
Logical data independence is more difficult to achieve than physical data independence, since application programs are heavily dependent on the logical structure of the data that they access.
Question 46 
Question 46 Explanation:
Using eigen values, the characteristic equation we get is,
λ^{3} + 2λ^{2}  2 = 0
Using CayleyHamiltonian theorem
A^{3} + 2A^{2}  2I = 0
So, A^{1} = 1/2 (2A  A^{2})
Solving we get,
λ^{3} + 2λ^{2}  2 = 0
Using CayleyHamiltonian theorem
A^{3} + 2A^{2}  2I = 0
So, A^{1} = 1/2 (2A  A^{2})
Solving we get,
Question 47 
Let p and q be propositions. Using only the truth table decide whether p ⇔ q does not imply p → q is true or false.
True  
False 
Question 47 Explanation:
So, "imply" is False making "does not imply" True.
There are 47 questions to complete.