Gate-2002

Question 1
A
4
B
2
C
1
D
0
Question 1 Explanation: 
Number of non-zero rows is the rank of the matrix.
Question 2

The trapezoidal rule for integration gives exact result when the integrand is a polynomial of degree

A
0 but not 1
B
1 but not 0
C
0 or 1
D
2
Question 2 Explanation: 
If curve is of function of degree 1, then curve will be a straight line, and in that case also, all trapezoids will fit completely. So there is no error in degree 1.
Question 3
The solution to the recurrence equation T(2k) = 3T(2k-1) + 1, T(1) = 1 is
A
B
C
D
Question 3 Explanation: 
T(2k)=3T(2k-1)+1
T(1)=1
k=0; T(1)=3T(2-1)+1
k=1; T(2)=3T(20)+1=3(1)+1=4
k=2; T(4)=3T(21)+1=3(4)+1=13
k=3; T(8)=3T(22)+1=3(13)+1=40
k=4; T(16)=3T(23)+1=3(40)+1=121
Simply go through the options.
Option B:
k=4 ⇒ (34+1-1)/2
⇒ (243-1)/2
⇒ 121
Question 4
The minimum number of colours required to colour the vertices of a cycle with n nodes in such a way that no two adjacent nodes have the same colour is
A
2
B
3
C
4
D
n - 2[n/2] + 2
Question 4 Explanation: 
We need 2 colours to colour even cycle and 3 colours to colour odd cycle.
Question 5
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
A
log n
B
n/2
C
(log2)n - 1
D
n
Question 5 Explanation: 
Worst case time complexity of singly linked list is O(n). So we need n number of comparisons needed to search a singly linked list of length n.
Question 6
Which of the following is true?
A
The set of all rational negative numbers forms a group under multiplication.
B
The set of all non-singular matrices forms a group under multiplication.
C
The set of all matrices forms a group under multiplication.
D
Both B and C are true.
Question 6 Explanation: 
A group G should follow 4 properties:
a. Closure: result of a * b must be in group G.
b. There must be an identity element i.e. e * a = a * e = a
c. There must be an inverse element b for every element a such that a * b = b * a = e
d. Associativity i.e. (a * b) * c = a * (b * c)
Rational negative numbers don't form a group under multiplication, as multiplying two negative numbers results into a positive number, so closure property is not satisfied.
Set of non-singular matrices forms a group under multiplication.
The set of all matrices doesn't form a group under multiplication, since there may not be an inverse for a matrix (in particular, for singular matrices).
Question 7
The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as
A
Context free
B
Regular
C
Deterministic Context free
D
Recursive
Question 7 Explanation: 
Push down automata accept context free grammars but here the value of stack is limited 10 then it accepts regular languages.
Question 8
“If X then Y unless Z” is represented by which of the following formulas in prepositional logic? (“ ¬ “, is negation, “∧” is conjunction, and “→ ” is implication)
A
(X∧¬Z)→Y
B
(X∧Y)→¬Z
C
X→(Y∧¬Z)
D
(X→Y)∧¬Z
Question 8 Explanation: 
"If X then Y unless Z" ⇒ ¬Z → (X→Y)
⇒ Z ∨ ¬X ∨ Y
⇒ ¬X ∨ Z ∨ Y
Option A:
(X ∧ ¬Z) → Y = ¬(X ∧ ¬Z ) ∨ Y = ¬X ∨ Z ∨ Y Hence, option (A) is correct.
Question 9
A device employing INTR line for device interrupt puts the CALL instruction on the data bus while
A
B
HOLD is active
C
READY is active
D
None of the above
Question 9 Explanation: 
INTR is a signal which if enabled then microprocessor has interrupt enabled it receives high INR signal & activates INTA signal, so another request can’t be accepted till CPU is busy in servicing interrupt.
Question 10
In 8085 which of the following modifies the program counter?
A
Only PCHL instruction
B
Only ADD instructions
C
Only JMP and CALL instructions
D
All instructions
Question 10 Explanation: 
PCHL Instruction: Which can copy the content from H& L to PC.
ADD Instruction: increments the program counter.
JMP & CALL: Change the values of PC.
Question 11
In serial data transmission, every byte of data is padded with a ‘0’ in the beginning and one or two ‘1’s at the end of byte because
A
Receiver is to be synchronized for byte reception
B
Receiver recovers lost ‘0’s and ‘1’s from these padded bits
C
Padded bits are useful in parity computation
D
None of the above
Question 11 Explanation: 
‘0’ is added at the beginning which can represent receiver about arrival of data and ‘1’ is added at the end which represent receiver state of new arrival of data.
Question 12
 
A
xz+y'z
B
xz'+zx'
C
x'y+zx'
D
None of the above
Question 12 Explanation: 

⇒ xz' + zx'
Question 13
Which of the following is not a form of memory?
A
instruction cache
B
instruction register
C
instruction opcode
D
translation look-a-side buffer
Question 13 Explanation: 
Opcode is the portion of a machine language instruction that specifies the operation to be performed.
Question 14
The decimal value 0.25
A
is equivalent to the binary value 0.1
B
is equivalent to the binary value 0.01
C
is equivalent to the binary value 0.00111…
D
cannot be represented precisely in binary
Question 14 Explanation: 
1st Multiplication iteration:
Multiply 0.25 by 2.
0.25×2 = 0.50 (product)
Fractional part = 0.50
Carry = 0
2nd Multiplication iteration:
Multiply 0.50 by 2.
0.50×2 = 1.00 (product)
Fractional part = 0.00
Carry = 1
The fractional part in the 2nd iteration becomes zero and so we stop the multiplication iteration.
Carry from 1st multiplication iteration becomes MSB and carry from 2nd iteration becomes LSB. So the result is 0.01.
Question 15
The 2’s complement representation of the decimal value -15 is
A
1111
B
11111
C
111111
D
10001
Question 15 Explanation: 
15 = 1111
-15 = 11111
1's complement = 10000
2's complement = 10001
Question 16
Sign extension is a step in
A
floating point multiplication
B
signed 16 bit integer addition
C
arithmetic left shift
D
converting a signed integer from one size to another
Question 16 Explanation: 
Sign extension is a step in converting a signed integer from on size to another.
Question 17
In the C language
A
At most one activation record exists between the current activation record and the activation record for the main
B
The number of activation records between the current activation record and the activation record for the main depends on the actual function calling sequence.
C
The visibility of global variables depends on the actual function calling sequence.
D
Recursion requires the activation record for the recursive function to be saved on a different stack before the recursive fraction can be called.
Question 17 Explanation: 
In C Language a function can create activation record from the created function stack.
Question 18
The results returned by function under value-result and reference parameter passing conventions
A
Do not differ
B
Differ in the presence of loops
C
Differ in all cases
D
May differ in the presence of exception
Question 18 Explanation: 
The result return by the function under value-result and reference parameter passing conventions may differ in presence of exception because in value-result the updated value can be returned to the original variable. But in case of reface parameter the value can change immediately.
Question 19
Relation R with an associated set of functional dependencies, F, is decomposed into BCNF. The redundancy (arising out of functional dependencies) in the resulting set of relations is
A
Zero
B
More than zero but less than that of an equivalent 3NF decomposition
C
Proportional to the size of F+
D
Indetermine
Question 19 Explanation: 
If a relation is in BCNF then there is no functional dependencies.
Question 20
With regard to the expressive power of the formal relational query languages, which of the following statements is true?
A
Relational algebra is more powerful than relational calculus.
B
Relational algebra has the same power as relational calculus.
C
Relational algebra has the same power as safe relational calculus.
D
None of the above.
Question 20 Explanation: 
Relational algebra has the same power as safe relational calculus.
A query can be formulated in safe Relational Calculus if and only if it can be formulated in Relational Algebra.
Question 21
In 2’s complement addition, overflow
A
is flagged whenever there is carry from sign bit addition
B
cannot occur when a positive value is added to a negative value
C
is flagged when the carries from sign bit and previous bit match
D
None of the above
Question 21 Explanation: 
The left most bit of positive value is zero. And left most bit for negative value is one. The value of 0+1 becomes 1. Then overflow never occurs.
Question 22
Which of the following scheduling algorithms is non-preemptive?
A
Round Robin
B
First-In First-Out
C
Multilevel Queue Scheduling
D
Multilevel Queue Scheduling with Feedback
Question 22 Explanation: 
First-in first-out scheduling algorithm is non-preemptive. In this whichever the process enter into ready queue first that will be served first.
Question 23
The optimal page replacement algorithm will select the page that
A
Has not been used for the longest time in the past.
B
Will not be used for the longest time in the future.
C
Has been used least number of times.
D
Has been used most number of times.
Question 23 Explanation: 
The optimal page replacement algorithm will select the page which will not been used for the longest time in the future.
Question 24
In the absolute addressing mode
A
the operand is inside the instruction
B
the address of the operand is inside the instruction
C
the register containing the address of the operand is specified inside the instruction
D
the location of the operand is implicit
Question 24 Explanation: 
The operand is inside the instruction---Immediate addressing.
The operand is inside the instruction --- absolute addressing.
The register containing the address of the operand is specified inside the instruction --- Register addressing.
The location of the operand is implicit --- Implicit addressing.
Question 25
Maximum number of edges in a n-node undirected graph without self loops is
A
B
C
D
Question 25 Explanation: 
The set of vertices has size n, the number of such subsets is given by the binomial coefficient C(n, 2)⋅ C(n, 2) = n(n-1)/2.
Question 26
 
A
Σ(1,4,5)
B
Σ(6,7)
C
Σ(0,1,3,5)
D
None of the above
Question 26 Explanation: 
f(x,y,z) = (f1', (x,y,z) ⋅ f2'(x,y,z) + f3'(x,y,z))
= (Σ(0,1,3,5) ⋅ Σ(6,7) + Σ(1,4,5))
[Σ(0,1,3,5) and Σ(6,7) ⇒ No common terms]
= (Σ(1,4,5))
Question 27
   
A
xyz'
B
xy+z
C
x+y
D
None of the above
Question 27 Explanation: 
F = (A'A0'10 + A'A0'11 + A'A0'12 + A1A013) EN
F = (xyz' + xyz + y'zy + zy')z'
= (xyz' + xyz + y'z(y+1))z'
= (xyz' + xyz + y'z)z'
= (xy(z+z') + y'z)z'
= (xy + y'z)z'
= (xyz' + y'zz')
= (xyz')
Question 28
Let f(A,B) = A'+B. Simplified expression for function f (f (x + y, y), z) is
A
x'+z
B
xyz
C
xy'+z
D
None of the above
Question 28 Explanation: 
f(A,B) = A' +B
⇒ f(f((x+y), y), z)
⇒ f(((x+y)' + y), z)
⇒ f(((x'⋅y') + y), z)
⇒ f((x'⋅y') + y), z)
⇒ ((x'⋅y') + y)' + z
⇒ (x'⋅y')⋅y' + z
⇒ (x+y)⋅y' + z
⇒ (xy'+yy') + z
⇒ xy' + z
Question 29
 
A
AC = 0 and CY =0
B
AC = 1 and CY =1
C
AC = 1 and CY =0
D
AC = 0 and CY =1
Question 29 Explanation: 
MOV H, 5DH
⇒ H = 0101 1101
MOV L, 6BH
⇒ L = 0110 1011
MOV A, H
A = 0101 1101
ADD L ⇒ A+L =

Here, AC=1; CY=0
Question 30
 
A
Outputs the sum of the present and the previous bits of the input.
B
Outputs 01 whenever the input sequence contains 11
C
Outputs 00 whenever the input sequence contains 10
D
None of the above
Question 30 Explanation: 
Let us consider a string 100111
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,0) = (A, 01)
Previous input + Present input = 1+0 = 01
(A,0) = (A, 00)
Previous input + Present input = 0+0 = 00
(A,1) = (B, 01)
Previous input + Present input = 0+1 = 01
(B,1) = (C, 10)
Previous input + Present input = 1+1 = 10
(C,1) = (C, 10)
Previous input + Present input = 1+1 = 10
Question 31
The performance of a pipelined processor suffers if
A
the pipeline stages have different delays
B
consecutive instructions are dependent on each other
C
the pipeline stages share hardware resources
D
All of the above
Question 31 Explanation: 
To speedup from pipelining equals the number of pipe stages are involve. Usually, however, the stages will not be perfectly balanced; besides, the pipelining itself involves some overhead.
If pipeline stages can’t have different delays, no dependency among consecutive instructions and sharing of hardware resources should not be there.
Question 32
Horizontal microprogramming
A
does not require use of signal decoders
B
results in larger sized microinstructions than vertical microprogramming
C
uses one bit for each control signal
D
all of the above
Question 32 Explanation: 
In horizontal microprogramming the instruction size is less as compared to vertical microprogramming. So, there is no need for decoding. But, one bit is used for all control signals to execute the microinstruction. If the bit is set to ‘1’ the control signal field is activated. If the bit is set to ‘0’ the control signal field is deactivated
Question 33
 
A
4040
B
4050
C
5040
D
5050
Question 33 Explanation: 
Address for a[40][50] = BaseAddress + [40 * 100 * element size] + [50 * element size]
= 0 + [40 * 100 * 1] + [50 * 1]
= 4000 + 50
= 4050
Question 34
The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
A
B
C
D
Question 34 Explanation: 

Question 35
 
A
n
B
n-1
C
2n
D
Question 35 Explanation: 
Question 36
 
A
O(n)
B
O(log n)
C
O(log log n)
D
O(1)
Question 36 Explanation: 
T(n) = T(√n)+1
Let n=2m
So, T(2m) = T(2m/2)+1
We substitute T(2m) = S(m),
So now the equation becomes,
S(m) = S(m/2)+1
Now after applying master's theorem,
S(m) = O(log m)
T(n) = O(log log n)
Question 37
A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?
A
B
C
D
Question 37 Explanation: 
Number of nodes in the left subtree is atleast half and atmost the num begin right sub tree.
No. of nodes in left sub tree = 2 right sub tree
No. of nodes in left sub tree = (n-1/3)
No. of nodes in right sub tree = 2(n-1/3)

Height of the tree = log3/2 n
Question 38
The smallest finite automaton which accepts the language {x|length of x is divisible by 3} has
A
2 states
B
3 states
C
4 states
D
5 states
Question 38 Explanation: 
{x | length of x divisible by 3} for this constructing a finite Automata that implies

Minimum no. of states that we require is "3".
Question 39
Which of the following is true?
A
The complement of a recursive language is recursive.
B
The complement of a recursively enumerable language is recursively enumerable.
C
The complement of a recursive language is either recursive or recursively enumerable.
D
The complement of a context-free language is context-free.
Question 39 Explanation: 
Recursive languages are closed under complementation.
Question 40
   
A
X2 = 3
B
X3 = 3
C
X2 = 2
D
X3 = 2
Question 40 Explanation: 
Newton Rampson formula,
Question 41
Four fair coins are tossed simultaneously. The probability that at least one head and one tail turn up is
A
B
C
D
Question 41 Explanation: 
Total possibilities = 42 = 16
Atleast one head = 1/16
Atleast one tail = 1/16
Probability of getting one head and one tail is = 1 - 1/16 - 1/16 = 16-1-1/16 = 14/16 = 7/8
Question 42
The binary relation S = ɸ (empty set) on set A = {1,2,3} is
A
Neither reflexive nor symmetric
B
Symmetric and reflexive
C
Transitive and reflexive
D
Transitive and symmetric
Question 42 Explanation: 
S = ɸ; A = {1,2,3}
A×S = {(ɸ,1), (ɸ,2), (ɸ,3), (1,ɸ), (2,ɸ), (3,ɸ)}
Not reflexive = (1,1), (2,2), (3,3) not there
Symmetric: if (a,b) is present then (b,a) is also present
Transitive: True; if (x,y), (y,z) then (z,x) is also present
Question 43
The C language is:
A
A context free language
B
A context sensitive language
C
A regular language
D
Parsable fully only by a Turing machine
Question 43 Explanation: 
C and C++ are context sensitive languages.
Question 44
To evaluate an expression without any embedded function calls
A
One stack is enough
B
Two stacks are needed
C
As many stacks as the height of the expression tree are needed
D
A Turning machine is needed in the general case
Question 44 Explanation: 
To evaluate an expression or converting prefix to postfix, postfix to prefix only one stack is enough.
Question 45
Dynamic linking can cause security concerns because
A
Security is dynamic
B
The path for searching dynamic libraries is not known till runtime
C
Linking is insecure
D
Cryptographic procedures are not available for dynamic linking
Question 45 Explanation: 
Because dynamic linking the path for searching dynamic libraries is not known till runtime.
Question 46
 
A
A
B
A and B
C
A and C
D
A, B and C
Question 46 Explanation: 
Statement C can be done in both multi programmed OS and as well as uni programmed OS.
Question 47
In the index allocation scheme of blocks to a file, the maximum possible size of the file depends on
A
the size of the blocks, and the size of the address of the blocks.
B
the number of blocks used for the index, and the size of the blocks.
C
the size of the blocks, the number of blocks used for the index, and the size of the address of the blocks.
D
None of the above
Question 47 Explanation: 
No. of addressable blocks using one Index block (A) = Size of block/Size of block address.
No. of block addresses available for addressing one file(B) = No. of Maximum blocks we can use for the Index * No. of addressable blocks using one Index block(A)
Size of File = B * Size of Block
Question 48

A B+- tree index is to be built on the Name attribute of the relation STUDENT. Assume that all student names are of length 8 bytes, disk blocks are of size 512 bytes, and index pointers are of size 4 bytes. Given this scenario, what would be the best choice of the degree (i.e. the number of pointers per node) of the B+-tree?

A
16
B
42
C
43
D
44
Question 48 Explanation: 
Let P be the degree of the nodes.
Then,
8(P-1) + 4P ≤ 512
12P - 8 ≤ 512
12P ≤ 520
P ≤ 43.33
P = 43
Question 49

Relation R is decomposed using a set of functional dependencies, F, and relation S is decomposed using another set of functional dependencies, G. One decomposition is definitely BCNF, the other is definitely 3NF, but it is not known which is which. To make a quaranteed identification, which one of the following tests should be used on the decompositions? (Assume that the closures of F and G are available).

A
Dependency-preservation
B
Lossless-join
C
BCNF definition
D
3NF definition
Question 49 Explanation: 
If it is BCNF then it is 3NF. But the relation is in 3NF then it is need not to be in BCNF.
Question 50
 
A
A functionally determines B and B functionally determines C
B
A functionally determines B and B does not functionally determines C
C
B does not functionally determines C
D
A does not functionally determines B and B does not functionally determines C
Question 50 Explanation: 
From the given instanceof relation it can be seen that A functionally determines B, but we cannot conclude this for the entire relation.
But for the given instance it can be seen that B does not functionally determines C, and it can be concluded for entire relation
Question 51
 
A
Theory Explanation is given below.
Question 52
(a) S = {〈1,2〉,〈2,1〉} is binary relation on set A = {1,2,3}. Is it irreflexive? Add the minimum number of ordered pairs to S to make it an equivalence relation. Give the modified S. (b) Let S = {a,b} and let (S) be the powerset of S. Consider the binary relation ‘⊆ (set inclusion)’ on (S). Draw the Hasse diagram corresponding to the lattice ((S),⊆).  
A
Theory explanation is given below.
Question 52 Explanation: 
(a) S = {(1,2), (2,1)}; A = {1,2,3}
The given relation S is irreflexive because no diagonal elements are present in the relation i.e., (x,x)∉R, ∀x∈A
If a relation is equivalence then it is
Reflexive
Symmetric
Transitive
Given relation S is not Reflexive & Transitive.
Reflexive closure on S = {(1,1), (2,2), (3,3), (1,2), (2,1)}
Transitive closure on S is does not change after performing reflexive closure on S.
S = {(1,1), (2,2), (3,3), (1,2), (2,1)}
(b) Given S = {a,b}
Powerset of S i.e., P(S) = {(ɸ), (a), (b), (a,b)}
Hasse diagram:
Question 53
   
A
Theory Explanation is given below.
Question 53 Explanation: 
(a)
Eigen value of upper/ lower triangular matrix are the diagonal elements of matrix.

(b) (i) A↔(A∨A): This can tells that if A then (A or A)and if (A or A) then A. It represents result as a tautology.
(ii) (A∨B)→B: This is neither tautology nor contradiction.
(iii) A∧(¬(A∨B)): here when A is true then (¬(A∨B)) is false, then it results contradiction.
Question 54
Draw all binary trees having exactly three nodes labeled A, B and C on which Preorder traversal gives the sequence C, B, A.
A
Theory Explanation is given below.
Question 54 Explanation: 

Total 5 binary trees are possible with the preorder C, B, A.
Question 55
   
A
Theory Explanation is given below.
Question 55 Explanation: 
A
Theory Explanation is given below.
Question 57
 
A
Theory of Explantion is given below.
Question 58

A
Theory Explanation is given below.
Question 59
 
A
Theory Explanation is given below.
Question 59 Explanation: 
move (disk-1, source, aux, dest) //Step-1
move disk from source to dest //Step-2
move (disk-1, aux, dest, source) //Step-3
Recurrence: 2T(n - 1) + 1
T(n) = 2T (n - 1) + 1
= 2[2T(n - 2) + 1] + 1
= 22T(n - 2) + 3

2k T(n - k) + (2k - 1)
= 2n-1T(1) + (2n-1 - 1)
= 2n-1 + 2n-1 - 1
= 2n - 1
≅ O(2n)
void move (int n, char A, char B, char C) {
if (n>0)
move(n-1, A, C, B);
printf("Move disk%d from pole%c to pole%c\n", n,A,C);
move(n-1, B, A, C);
}
}
Question 60
 
A
Theory Explanation is given below.
Question 60 Explanation: 
(a) INITIALIZATION: For i = 1 ... n
{ for j = 1 ... n
{ if a[i,j] = 0 then P[i,j] = infinite;
else P[i,j] = a[i,j];
}
}
(b) ALGORITHM: For i = 1 ... n
{ for j = 1 ... n;
{ for k = 1 ... n
{
P[i,j] = min (P[i,j], P[i,k]+P[k,j])
}
}
}
(c) Actual graph:

MST: There are 2 possible MST's

Question 61
 
A
Theory Explanation is given below.
Question 62
A
Theory Explanation is given below.
Question 63
 
A
Theory Explanation is given below.
Question 64
 
A
Theory Explanation is given below.
Question 65
 
A
Theory Explantion is given below.
Question 66
 
A
Theory Explanation is given below.
Question 67
 
A
Theory Explanation is given below.
Question 68
 
A
Theory Exolanation is given below.
Question 69
A
Theory Explanation is given below.
Question 70
 
A
Theory Explanation is given below.
There are 70 questions to complete.