CS GATE 2013 (Test 2)



Tag: cs gate 2013
Q.1
Complete the sentence: Universalism is to particularism as diffuseness is to ________
A. specificity
B. neutrality
C. generality
D. adaptation
Answer : Option A
Explaination / Solution:

The relation is that of antonyms

Workspace
Report
Topic: Arithmetic Tag: CS GATE 2013
Q.2
A tourist covers half of his journey by train at 60 km/h, half of the remainder by bus at 30 km/h and the rest by cycle at 10 km/h. The average of the tourist in km/h during his entire journey is
A. 36
B. 30
C. 24
D. 18
Answer : Option C
Explaination / Solution:

Let the total distance covered be ‘D’ 
Now, average speed = D/Total time taken


Workspace
Report
Q.3
Determine the maximum length of cable (in km) for transmitting data at a rate of 500 Mbps in an Ethernet LAN with frames of size 10,000 bits. Assume the signal speed in the cable to be 2,00,000 km/s
A. 1
B. 2
C. 2.5
D. 5
Answer : Option B
Explaination / Solution:



Workspace
Report
Topic: Databases Tag: CS GATE 2013
Q.4
Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values. 
F = {CH → G, A → BC, B → CFH, E → A, F → EG} is a set of functional dependencies (FDs) so that F+ is exactly the set of FDs that hold for R
How many candidate keys does the relation R have?
A. 3
B. 4
C. 5
D. 6
Answer : Option B
Explaination / Solution:

Candidate keys are AD, BD, ED and FD

Workspace
Report
Q.5
The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have almost two source operands and one destination operand. 
Assume that all variables are dead after this code segment
c = a + b;
d = c * a;
e = c + a;
x = c *c;
if (x > a) {
y = a * a;
}
else {
d = d * d;
e = e * e;
}
 What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocation
A. 3
B. 4
C. 5
D. 6
Answer : Option B
Explaination / Solution:


In the above code minimum number of registers needed are = 4 

Workspace
Report
Q.6
Consider the following two sets of LR(1) items of an LR(1) grammar
X → c.X, c / d    X → c.X, $
X → .cX, c / d    X → .cX, $
X → .d, c / d      X → .d, $
Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE? 
1. Cannot be merged since look aheads are different
2. Can be merged but will result in S–R conflict
3. Can be merged but will result in R–R conflict
4. Cannot be merged since goto on c will lead to two different sets

A. 1 only
B. 2 only
C. 1 and 4 only
D. 1, 2, 3 and 4
Answer : Option D
Explaination / Solution:


1. Merging of two states depends on core part (production rule with dot operator), not on look aheads.
2. The two states are not containing Reduce item ,So after merging, the merged state can not contain any S-R conflict
3. As there is no Reduce item in any of the state, so can’t have R-R conflict.
4. Merging of stats does not depend on further goto on any terminal. So all statements are false.

Workspace
Report
Q.7
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is ½. What is the expected number of unordered cycles of length three?
A. 1/8
B. 1
C. 7
D. 8
Answer : Option C
Explaination / Solution:

P(edge) = 1/2
Number of ways we can choose the vertices out of 8 is 
(Three edges in each cycle) 
Expected number of unordered cycles of length 3 = 

Workspace
Report
Q.8
In the following truth table, V = 1 if and only if the input is valid

What function does the truth table represent?  
A. Priority encoder
B. Decoder
C. Multiplexer
D. Demultiplexer
Answer : Option A
Explaination / Solution:

4 to 2 priority encoder.

Workspace
Report
Q.9
Consider the following function
int unknown (int n) {
int i, j, k 0;
for (i = n/2; i<=n; i++)
for (j = 2; j<=n; j = j*2)
k = k+n/2;
return(k);
}
The return value of the function is
A. Θ(n2)
B. Θ(nlog n)
C. Θ(n3)
D. Θ(nlog n)
Answer : Option B
Explaination / Solution:



Workspace
Report
Q.10
In a k-way set associative cache, the cache is divided into v sets, each of which consists of k lines. The lines of a set are placed in sequence one after another. The lines in set s are sequenced before the lines in set (s+1). The main memory blocks are numbered 0 onwards. The main memory block numbered j must be mapped to any one of the cache lines from
A. (j mod v)*k to (j mod v)*k + (k − 1)
B. (j mod v) to (j mod v) + (k − 1)
C. (j mod k) to (j mod k) + (v − 1)
D. (j mod k)*v to (j mod k)*v + (v − 1)
Answer : Option A
Explaination / Solution:

Position of main memory block in the cache (set) = (main memory block number) MOD (number of sets in the cache). As the lines in the set are placed in sequence, we can have the lines from 0 to (K – 1) in each set. Number of sets = v, main memory block number = j First line of cache = (j mod v)*k; last line of cache = (j mod v)*k + (k – 1)

Workspace
Report