## GATE 2012

 Question 1

Consider the following logical inferences.

I1: If it rains then the cricket match will not be played.
The cricket match was played.
Inference: There was no rain.
I2: If it rains then the cricket match will not be played.
It did not rain.
Inference: The cricket match was played.

Which of the following is TRUE?

 A Both I1 and I2 are correct inferences B I1 is correct but I2 is not a correct inference C I1 is not correct but I2 is a correct inference D Both I1 and I2 are not correct inferences
Engineering-Mathematics       Propositional-Logic
Question 1 Explanation:
I1: If it rains then the cricket match will not be played.
The cricket match was played.
Let p = it rains
q = playing cricket/ match played
If (it rains) then (the match will not be played)
p ⇒ (∼q)
Inference: There was no rain. (i.e., p = F)
So for any F ⇒ (∼q) is true.
So this inference is valid.
I2: If it rains then the cricket match will not be played.
It did not rain.
p ⇒ (∼q)
Inference: The cricket match was played.
q = T
p ⇒ (∼q)
p ⇒ (∼T)
p ⇒ F
This is false for p = T, so this is not true.
 Question 2

Which of the following is TRUE?

 A Every relation in 3NF is also in BCNF B A relation R is in 3NF if every non-prime attribute of R is fully functionally dependent on every key of R C Every relation in BCNF is also in 3NF D No relation can be in both BCNF and 3NF
Database-Management-System       Normalization
Question 2 Explanation:
BCNF is a stronger version 3NF. So straight from definition of BCNF every relation in BCNF will also be in 3NF.
 Question 3

What will be the output of the following C program segment?

```char inchar = 'A';
switch (inchar)
{
case 'A' :
printf ("choice A n") ;
case 'B' :
printf ("choice B ") ;
case 'C' :
case 'D' :
case 'E' :
default:
printf ("No Choice") ;
}```
 A No Choice B Choice A C D Program gives no output as it is erroneous
Programming       C-Programming
Question 3 Explanation:
Everything in the switch will be executed, because there is no break; statement after case ‘A’. So it executes all the subsequent statements until it find a break;
So,
→ Choice A
→ Choice B. No choice. Is the output.
 Question 4

Assuming P ≠ NP, which of the following is TRUE?

 A NP-complete = NP B NP-complete ∩ P = ∅ C NP-hard = NP D P = NP-complete
Algorithms       P-NP
Question 4 Explanation:
Note: Out of syllabus.
The definition of NP-complete is,
A decision problem p is NP-complete if:
1. p is in NP, and
2. Every problem in NP is reducible to p in polynomial time.
It is given that assume P ≠ NP , hence NP-complete ∩ P = ∅ .
This is due to the fact that, if NP-complete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NP-complete also, then it means that P1 (NP-complete problem) can be solved in polynomial time also (as it is also in P class) and this implies that every NP problem can be solve in polynomial time, as we can convert every NP problem into NP-complete problem in polynomial time.
Which means that we can convert every NP problem to P1 and solve in polynomial time and hence P = NP, which is contradiction to the given assumption that P ≠ NP.
 Question 5

The worst case running time to search for an element in a balanced binary search tree with n2n elements is

 A Θ (n log n) B Θ (n2n) C Θ (n) D Θ (log n)
Data-Structures       Binary-Search-Tree
Question 5 Explanation:
→ Worst case running time to search for an element in a balanced binary search tree of ‘n’ elements is (log n).
→ No of elements = n.2n then search time = (log n.2n)
= (log n + log 2n)
= (log n + n log 2)
= O(n)
 Question 6

The truth table

represents the Boolean function

 A X B X + Y C X ⊕ Y D Y
Digital-Logic-Design       Boolean-Algebra
Question 6 Explanation:
f(X,Y) = XY’ + XY = X(Y’ + Y) = X
 Question 7

The decimal value 0.5 in IEEE single precision floating point representation has

 A fraction bits of 000…000 and exponent value of 0 B fraction bits of 000…000 and exponent value of −1 C fraction bits of 100…000 and exponent value of 0 D no exact representation
Digital-Logic-Design       Number-Systems
Question 7 Explanation:
(0.5)10 = (1.0)2 × 2–1
So, value of the exponent = -1
and
fraction is 000…000 (Implicit representation)
 Question 8

A process executes the code

```fork();
fork();
fork();```

The total number of child processes created is

 A 3 B 4 C 7 D 8
Operating-Systems       System-Calls
Question 8 Explanation:
The no. of child process created = 2n - 1 = 23 - 1 = 7 (where n is number of fork() statements)
7 are child processes.
 Question 9

Consider the function f(x) = sin(x) in the interval x ∈ [π/4, 7π/4]. The number and location(s) of the local minima of this function are

 A One, at π/2 B One, at 3π/2 C Two, at π/2 and 3π/2 D Two, at π/4 and 3π/2
Engineering-Mathematics       Calculus
Question 9 Explanation:
f(x) = sin x
f’(x) = cos x

[just consider the given interval (π/4, 7π/4)]
f'(x) = 0 at π/2, 3π/2
To get local minima f ’’(x) > 0, f ’’(x) = - sin x
f ’’(x) at π/2, 3π/2
f ’’(x) = -1< 0 local maxima
f ’’ (3π/2) = 1 > 0 this is local minima
In the interval [π/4, π/2] the f(x) is increasing, so f(x) at π/4 is also a local minima.
So there are two local minima for f(x) at π/4, 3π/2.
 Question 10

The protocol data unit (PDU) for the application layer in the Internet stack is

 A Segment B Datagram C Message D Frame
Computer-Networks       Application-Layer-Protocol
Question 10 Explanation:
The PDU for Data Link layer, Network layer, Transport layer and Application layer are frame, datagram, segment and message respectively.
 Question 11

Let A be the 2×2 matrix with elements a11 = a12 = a21 = +1 and a22 = -1. Then the eigenvalues of the matrix A19 are

 A 1024 and -1024 B 1024√2 and -1024√2 C 4√2 and -4√2 D 512√2 and -512√2
Engineering-Mathematics       Linear-Algebra
Question 11 Explanation:
a11 = a12 = a21 = 1, a22 = -1
The 2×2 matrix =
Cayley Hamilton theorem:
If matrix A has ‘λ’ as eigen value, An has eigen value as λn.
Eigen value of
|A-λI| = 0

-(1-λ)(1+λ)-1 = 0
-(1-λ2 )-1 = 0
-1 = 1-λ2
λ2 = 2
λ = ±√2
A19 has (√2)19 = 29×√2 (or) (-√2)19 = -512√2
= 512√2
 Question 12

What is the complement of the language accepted by the NFA shown below?

Assume Σ={a} and ε is the empty string.

 A ∅ B {ε} C a* D {a ,ε}
Theory-of-Computation       Finite-Automata
Question 12 Explanation:
The Σ= {a} and the given NFA accepts the strings {a, aa, aaa, aaaa, ……….} i.e. the language accepted by the NFA can be represented by the regular expression: {a+}
Hence the complement of language is: {a* − a+} = {ϵ}
 Question 13

What is the correct translation of the following statement into mathematical logic?

“Some real numbers are rational”

 A ∃x (real(x) ∨ rational(x)) B ∀x (real(x) → rational(x)) C ∃x (real(x) ∧ rational(x)) D ∃x (rational(x) → real(x))
Engineering-Mathematics       Propositional-Logic
Question 13 Explanation:

∃x (real(x) ∧ rational(x))
(A) ∃x(real(x) ∨ rational(x))
means There exists some number, which are either real or rational.
(B) ∀x (real(x)→rational(x))
If a number is real then it is rational.
(D) ∃x (rational(x)→real(x))
There exists a number such that if it is rational then it is real.
 Question 14

Given the basic ER and relational models, which of the following is INCORRECT?

 A An attribute of an entity can have more than one value B An attribute of an entity can be composite C In a row of a relational table, an attribute can have more than one value D In a row of a relational table, an attribute can have exactly one value or a NULL value
Database-Management-System       ER-Model
Question 14 Explanation:
Option (A): In ER-model, multivalued attribute of an entity can have more than one value.
Option (B): In ER model, the attribute which can be further broken down into some other attributes is called composite attribute.
Option (C): In Relational model, the intersection of one row and column should contain only one value. So, option (C) is INCORRECT.
Option (D): In Relational model, the intersection of one row and column should contain either exactly one value or NULL.
 Question 15

Which of the  following statements are TRUE about an SQL query?

P:An SQL query can contain a HAVING clause even if it does not have a GROUP BY clause.
Q:An SQL query can contain a HAVING clause even if it has a GROUP BY clause.
R: All attributes used in the GROUP BY clause must appear in the SELECT clause.
S: Not all attributes used in the GROUP BY clause need to appear in the SELECT clause
 A P and R B P and S C Q and R D Q and S
Database-Management-System       SQL
Question 15 Explanation:
The SQL GROUP BY clause is used in collaboration with the SELECT statement to arrange identical data into groups. This GROUP BY clause follows the WHERE clause in a SELECT statement and precedes the ORDER BY clause. The attributes used in GROUP BY clause must present in SELECT statement.
The HAVING Clause enables you to specify conditions that filter which group results appear in the results. The WHERE clause places conditions on the selected columns, whereas the HAVING clause places conditions on groups created by the GROUP BY clause. So, we cannot use HAVING clause without GROUP BY clause.
 Question 16

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

 A T(n) = 2T(n - 2) + 2 B T(n) = 2T(n - 1) + n C T(n) = 2T(n/2) + 1 D T(n) = 2T(n - 1) + 1
Data-Structures       Recursion
Question 16 Explanation:
The recurrence equation for given recurrence function is
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 22 T(n – 2) + 3

= 2k T( n – k) + (2k – 1)
n – k = 1
= 2n-1 T(1) + (2n-1 – 1)
= 2n-1 + 2n-1 – 1
= 2n – 1
≌ O(2n)
There are 16 questions to complete.

Register Now