GATE | GATE CS 2012 | Question 1

Last Updated: 29-11-2013

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

Answer: (B)

Explanation: The cricket match may not be played even if doesn’t rain.

GATE | GATE CS 2012 | Question 2
Last Updated: 15-10-2019
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

Answer: (C)
QUESTION 3 :What will be the output of the following C program segment?

filter_none
edit
play_arrow
brightness_4
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)
Choice A
Choice B No choice
(D)
Program gives no output as it is erroneous

Answer: (C)
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
(A) A
(B) B
(C) C
(D) D

Answer: (B)

GATE | GATE CS 2012 | Question 5

Last Updated: 29-11-2013
The worst case running time to search for an element in a balanced in a binary search tree with
n2^n elements is

(A)

(B)
(C)

(D)
(A) A
(B) B
(C) C
(D) D

Answer: (C)

Explanation:
BCNF is a stronger version 3NF. So every relation in BCNF will also be in 3NF.
GATE | GATE CS 2012 | Question 7
Last Updated: 29-11-2013
T he 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

Answer: (B)

Explanation: The IEEE 754 standard specifies following distribution of bits:

Sign bit: 1 bit
Exponent width: 8 bits
Significand or Fraction: 24 (23 explicitly stored)
0.5 in base 10 means 1 X 2-1 in base
GATE | GATE CS 2012 | Question 8
Last Updated: 29-11-2013
A process executes the code
fork();
fork();
fork();
The total number of child processes created is
(A) 3
(B) 4
(C) 7
(D) 8

Answer: (C)

Explanation: Let us put some label names for the three lines

fork (); // Line 1
fork (); // Line 2
fork (); // Line 3

L1 // There will be 1 child process created by line 1

/ \
L2 L2 // There will be 2 child processes created by line 2
/ \ / \
L3 L3 L3 L3 // There will be 4 child processes created by line 3
We can also use direct formula to get the number of child processes

GATE | GATE CS 2012 | Question 9

Last Updated: 29-11-2013
Consider the function f(x) = sin(x) in the interval [π/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

Answer: (D)
GATE | GATE CS 2012 | Question 10
Last Updated: 09-10-2019
The protocol data unit (PDU) for the application layer in the Internet stack is
(A) Segment
(B) Datagram
(C) Message
(D) Frame

Answer: (C)
GATE | GATE CS 2012 | Question 11
Last Updated: 03-09-2017
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) A
(B) B
(C) C
(D) D

Answer: (D)

Explanation:
A = 1 1
1 -1

A2 = 2 0
0 2

A4 = A2 X A2
A4 = 4 0
0 4

A8 = 16 0
0 16

A16 = 256 0
0 256

A18 = A16 X A2
A18 = 512 0
0 512

A19 = 512 512

512 -512

Applying Characteristic polynomial

512-lamda 512
512 -(512+lamda) = 0

-(512-lamda)(512+lamda) - 512 x 512 = 0

lamda2 = 2 x 512
2

det(A) = -2.
det(A^19) = (det(A))^19 = -2^19 = lambda1*lambda2.
The only viable option is D.

GATE | GATE CS 2012 | Question 12

Last Updated: 10-09-2018
What is the complement of the language accepted by the NFA shown below?

(A) A
(B) B
(C) C
(D) D

Answer: (B)

Explanation: The given alphabet contains only one symbol {a} and the given NFA accepts all
strings with any number of occurrences of ‘a’. In other words, the NFA accepts a+. Therefore
complement of the language accepted by automata is empty string
GATE | GATE CS 2012 | Question 14
Last Updated: 29-11-2013
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

Answer: (C)

Explanation: The term ‘entity’ belongs to ER model and the term ‘relational table’ belongs to
relational model.
A and B both are true. ER model supports both multivalued and composite attributes See this for
more details.
(C) is false and (D) is true. In Relation model, an entry in relational table can can have exactly one
value or a NULL.

GATE | GATE CS 2012 | Question 15

Last Updated: 09-10-2019
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 only 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
Answer: (B)

GATE | GATE CS 2012 | Question 16

Last Updated: 29-11-2013
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

Answer: (D)
GATE | GATE CS 2012 | Question 17
Last Updated: 29-11-2013
Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected
graph, then the number of bounded faces in any embedding of G on the plane is equal to
(A) 3
(B) 4
(C) 5
(D) 6

Answer: (D)

Explanation: If the graph is planar, then it must follow below Euler’s Formula for planar graphs
v - e + f = 2
v is number of vertices
e is number of edges
f is number of faces including bounded and unbounded

10 - 15 + f = 2
f = 7
There is always one unbounded face, so the number of bounded faces =  6
GATE | GATE CS 2012 | Question 18
Last Updated: 29-11-2013
Let w(n) and A(n) denote respectively, the worst case and average case running time of an
algorithm executed on an input of size n. which of the following is ALWAYS TRUE?

(A) 
(B) 
(C) 
(D) 
(A) A
(B) B
(C) C
(D) D

Answer: (C)

Explanation: The worst case time complexity is always greater than or same as the average case
time complexity.
The term written in Big O notation can always asymptotically same or greater than the term on the
other side.
GATE | GATE CS 2012 | Question 19
Last Updated: 19-11-2018
The amount of ROM needed to implement a 4 bit multiplier is
(A) 64 bits
(B) 128 bits
(C) 1 Kbits
(D) 2 Kbits

Answer: (D)
Explanation: For a 4 bit multiplier, there are 24 * 24 combinations, i.e., 28 combinations.
Also, Output of a 4 bit multiplier is 8 bits.
Thus, the amount of ROM needed = 28 * 8 = 211 = 2048 bits = 2Kbits
GATE | GATE CS 2012 | Question 65
Last Updated: 29-11-2013
Which of the following transport layer protocols is used to support electronic mail?
(A) SMTP
(B) IP
(C) TCP
(D) UDP

Answer: (C)

Explanation: E-mail uses SMTP as application layer protocol.

TCP and UDP are two transport layer protocols. SMTP uses TCP as transport layer protocol as
TCP is reliable.
Which of the following problems are decidable?

(A) 1, 2, 3, 4
(B) 1, 2
(C) 2, 3, 4
(D) 3, 4

Answer: (D)
Consider the data given in previous question. The size of the cache tag directory is
(A) 160 Kbits
(B) 136 bits
(C) 40 Kbits
(D) 32 bits

Answer: (A)

Explanation: 16 bit address

2 bit valid
1 modified
1 replace
Total bits = 20
20 × no. of blocks
= 160 K bits.
GATE | GATE CS 2011 | Question 43
Last Updated: 19-11-2018

An 8KB direct-mapped write-back cache is organized as multiple blocks, each of size 32-bytes.
The processor generates 32-bit addresses. The cache controller maintains the tag information for
each cache block comprising of the following.
1 Valid bit
1 Modified bit
As many bits as the minimum needed to identify the memory block mapped in the cache. What is
the total size of memory needed at the cache controller to store meta-data (tags) for the cache?
(A) 4864 bits
(B) 6144 bits
(C) 6656 bits
(D) 5376 bits

Answer: (D)

Explanation:
Cache size = 8 KB
Block size = 32 bytes
Number of cache lines = Cache size / Block size = (8 × 1024 bytes)/32
= 256

total bits required to store meta-data of 1 line = 1 + 1 + 19 = 21

bits
total memory required = 21 × 256 = 5376 bits
GATE | GATE CS 2010 | Question 48
Last Updated: 19-11-2018

A computer system has an L1 cache, an L2 cache, and a main memory unit connected as shown
below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The
memory access times are 2 nanoseconds. 20 nanoseconds and 200 nanoseconds for L1 cache, L2
cache and main memory unit respectively.
When there is a miss in L1 cache and a hit in L2 cache, a block is transferred from L2 cache to L1
cache. What is the time taken for this transfer?
(A) 2 nanoseconds
(B) 20 nanoseconds
(C) 22 nanoseconds
(D) 88 nanoseconds

Answer: (C)

Explanation: A block to access in L2 cache requires 20 nanoseconds, and 2 seconds to place in

L1-cache.
The block size in L1 cache is 4 words, so total time is =time to access L2 + time to place in L1 =
20+2 = 22 ns.

Consider the data from above question. When there is a miss in both L1 cache and L2 cache, first a
block is transferred from main memory to L2 cache, and then a block is transferred from L2 cache
to L1 cache. What is the total time taken for these transfers?
(A) 222 nanoseconds
(B) 888 nanoseconds
(C) 902 nanoseconds
(D) 968 nanoseconds

Answer: (C)

Explanation: Since the block size of L2 cache is 16 words and the bandwidth of mainmem->L2
cache is 4 words, it requires a transfer of 4 words 4 times and then a transfer of required 4 words
from L2 cache to L1 cache.
So total time is 4*(200 + 20) + 1*(20 + 2) = 902 nanoseconds.
Option (C) is correct.