## 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
Algorithms       Recursions
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
Engineering-Mathematics       Linear-Algebra
Question 2 Explanation: Question 3
 A B C D Engineering-Mathematics       Calculus
Question 3 Explanation: 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)
Engineering-Mathematics       Probability
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
Data-Structures       Programming
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
Engineering-Mathematics       Graph-Theory
Question 6 Explanation: Question 7
The recurrence relation that arises in relation with the complexity of binary search is:
 A B C D Algorithms       Time-Complexity
Question 7 Explanation:
In binary search, search for the half of the list and constant time for comparing. So, Question 8
 A B C D E None of the above.
Digital-Logic-Design       Logic-Gates
Question 8 Explanation: Question 9
 A 0 B 1 C 2 D 3
Engineering-Mathematics       Linear-Algebra
Question 9 Explanation: Question 10
Some group (G, 0) 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
Engineering-Mathematics       Groups
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): 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 D Engineering-Mathematics       Linear-Algebra
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
Compiler-Design       Compilers
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
Operating-Systems       Page-Replacement-Algorithm
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
Data-Structures       Stacks
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 D Engineering-Mathematics       Permutation-and-Combination
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
Theory-of-Computation       Grammar
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
Theory-of-Computation       CFG
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.
 Question 19
Which of the following algorithm design techniques is used in the quicksort algorithm?
 A Dynamic programming B Backtracking C Divide and conquer D Greedy method
Algorithms       Quick-Sort
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 call-by reference and call-by-name parameter passing methods?
 A Passing a constant value as a parameter B Passing the address of an array as a parameter C Passing an array element as a parameter D Passing an array following statements is true
Algorithms       Call-by-reference-and-Call-by-value
Question 20 Explanation:
Passing an array element as a parameter then it gives different output values for the call-by-reference and call-by-name parameters.
{ ........
a[ ] = {1, 2, 3, 4}
i = 0
fun(a[i]);
print a;
}
fun(int x)
{
int i = 1;
x = 8;
}
O/p:
Call-by-reference = 8
Call-by-value = 1
 Question 21
Which one of the following statements is true?
 A Macro definitions cannot appear within other macro definitions in assembly language programs B Overlaying is used to run a program which is longer than the address space of computer C Virtual memory can be used to accommodate a program which is longer than the address space of a computer D It is not possible to write interrupt service routines in a high level language
Computer-Organization       General
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?
 A Optimal binary search tree construction can be performed efficiently using dynamic programming. B Breadth-first search cannot be used to find converted components of a graph. C Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed. D Depth-first search can be used to find connected components of a graph.
Algorithms       Searching
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
 A g1(n) is O(g2(n)) B g1 (n) is O(3) C g2 (n) is O(g1 (n)) D g2 (n) is O(n) E Both A and B
Algorithms       Asymptotic-Notations
Question 23 Explanation:
In asymptotic complexity, we assume sufficiently large n. So, g1(n) = n2 and g2(n) = n3.
Growth rate of g1 is less than that of g2 i.e., g1(n) = O(g2(n)) = O(n).
 Question 24
 A either first fit or best fit policy (any one) B first fit but not best fit policy C best fit but first fit policy D None of the above
Operating-Systems       Page-Replacement-Algorithm
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.
 Question 25
The number of flip-flops required to construct a binary modulo N counter is __________
 A ⌈log2 N⌉
Digital-Logic-Design       Flip-Flops
Question 25 Explanation:
For mod-N counter we need ⌈log2 N⌉ flip flops.
 Question 26
On the set N of non-negative integers, the binary operation __________ is associative and non-commutative.
 A fog
Engineering-Mathematics       Functions
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.
 Question 27
Amongst the properties {reflexivity, symmetry, anti-symmetry, transitivity} the relation R = {(x,y) ∈ N2 | x ≠ y } satisfies __________
 A symmetry
Engineering-Mathematics       Relations
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.
 Question 28
The number of subsets {1, 2, ... n} with odd cardinality is __________
 A 2n-1
Engineering-Mathematics       Set-Theory
Question 28 Explanation:
Total no. of subsets with n elements is 2n.
And so, no. of subsets with odd cardinality is half of total no. of subsets = 2n /n = 2n-1
 Question 29
The number of edges in a regular graph of degree d and n vertices is _________
 A d*n/2
Engineering-Mathematics       Graph-Theory
Question 29 Explanation:
Sum of degree of vertices = 2 × no. of edges
d * n = 2 * |E|
∴ |E| = d*n/2
 Question 30
 A P2 + P3
Engineering-Mathematics       Probability
Question 30 Explanation:
P(A∩B') = P(A) - P(A∩B)
P3 = P(A) - P2
P(A) = P2 + P3
 Question 31

Consider n-bit (including sign bit) 2’s complement representation of integer number. The range of integer values, N, that can be represented is _________ ≤ N ≤ _________

 A -2n-1 to 2n-1 - 1
Digital-Logic-Design       Number-Systems
 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 __________

 A 0.93
Engineering-Mathematics       Probability
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
 Question 33
The Hasse diagrams of all the lattices with up to four elements are __________ (write all the relevant Hasse diagrams).
 A Engineering-Mathematics       Lattices
Question 33 Explanation:
For 1 element:
We can't draw lattice with 1 element.
For 2 element: For 3 element: For 4 element: Question 34
 A L=0*1*
Theory-of-Computation       Finite-Automata
Question 34 Explanation:
L = 0*1*
L contains all binary strings where a 1 is not followed by a 0.
 Question 35
 A True B False
Computer-Organization       Microprocessor
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 micro-processor.
 Question 36
 A True B False
Computer-Organization       RISC
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.
 Question 37
 A True B False
Computer-Organization       Finite-State-Machine
Question 37 Explanation:
FA or Finite state machine to add two integers can be constructed using two states:
→ q0: Start state to represent carry bit is 0.
→ q1: 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
 A Out of syllabus.
Engineering-Mathematics       General
Question 38 Explanation:
(i) - (b), (ii) - (c), (iii) - (d), (iv) - (a)
 Question 39
 A (i) - (d), (ii) - (a), (iii) - (b), (iv) - (c)
Compiler-Design       General
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.
 Question 40
 A True B False
Database-Management-System       Normalizations
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?
 A Yes B No
Database-Management-System       Normal-Forms
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.
 A Out of syllabus (For explanation see below)
Database-Management-System       Relational-Algebra
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.
 Question 43
 A True B False
Theory-of-Computation       Undecidability
Question 43 Explanation:
Because if a set itself is countable then the subset of set is definitely countable.
 Question 44
 A Out of syllabus.
Computer-Organization       General
Question 44 Explanation:
(i) - (a), (ii) - (b), (iii) - (d), (iv) - (c)
 Question 45
 A True B False
Database-Management-System       General
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
 A B C D Engineering-Mathematics       Linear-Algebra
Question 46 Explanation:
Using eigen values, the characteristic equation we get is,
3 + 2λ2 - 2 = 0
Using Cayley-Hamiltonian theorem
-A3 + 2A2 - 2I = 0
So, A-1 = 1/2 (2A - A2)
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.
 A True B False
Engineering-Mathematics       Prepositional-Logic
Question 47 Explanation: So, "imply" is False making "does not imply" True.
There are 47 questions to complete.