CS GATE 2017 PAPER 01 - Online Test
Q1. Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in
E are positive and distinct. Consider the following statements:
(I) Minimum spanning tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
Answer : Option A
Explaination / Solution:
Shortest path from B to C are two B-A-C and B-C both of weight '3'
Q2. Find the smallest number y such that y × 162 is a perfect cube.
Answer : Option D
Explaination / Solution:
Factorization of 162 is 2 × 3 × 3 × 3 × 3
y × 162 is a perfect cube
y × 2 × 3 × 3 × 3 × 3 = Perfect cube
For perfect cube 2's & 3's are two more required each.
Q3. The probability that a k-digit number does NOT contain the digits 0,5,or 9 is
Answer : Option C
Explaination / Solution:
Each digit can be filled in 7 ways as 0, 5 and 9 are not allowed. So each of these places can be
filled by 1, 2, 3, 4, 6, 7, 8.
Q4. Arun, Gulab, Neel and Shweta must choose one shirt each from a pile of four shirts coloured
red, pink, blue and white respectively. Arun dislikes the colour red and Shweta dislikes the
colour white. Gulab and Neel like all the colours. In how many different ways can they
choose the shirts so that no one has a shirt with a colour he or she dislikes ?
Answer : Option D
Explaination / Solution:
As there are 4 people A,G,N,S and 4 colours so without any restriction total ways have to be
4 × 4 = 16
Now, Arun → dislikes Red and
Shweta →dislikes white
So 16-2=14 ways
Q5. Let c1 ........cn be scalars, not all zero, such that 
where ai are column vectors in
Rn . Consider the set of linear equations Ax = b where A = [a1 ........an] and 
The set of equations has
where ai are column vectors in
Rn . Consider the set of linear equations Ax = b where A = [a1 ........an] and The set of equations has
Answer : Option C
Explaination / Solution:
Since the scalars are not all zero
∴ The column vectors ai for i = 1,2...,n are linearly dependent
Q6. The n-bit fixed-point representation of an unsigned real number real X uses f bits for the
fraction part. Let i = n –f. The range of decimal values for X in this representation is
Answer : Option D
Explaination / Solution:
i = n – f . f
Max value = 111.....1 (i times).111........1 (f times)
Q7. Consider the first-order logic sentence F: ∀z (∃yR(x,y)). Assuming non-empty logical
domains, which of the sentences below are implied by F?
I. ∃y (∃xR(x,y)) II. ∃y (∀xR(x,y))
III. ∀y (∃xR(x,y)) IV. ¬∃x (∀y¬R(x,y))
Answer : Option B
Explaination / Solution:
Q8. Consider the following functions from positive integers to real numbers:
The CORRECT arrangement of the above functions in increasing order of asymptotic
complexity is:
Answer : Option B
Explaination / Solution:
No Explaination.
Q9. The value of 
Answer : Option C
Explaination / Solution:
Q10. Let u and v be two vectors in R2 whose Euclidean norms satisfy ||u|| = 2 ||v||. What is the value
of α such that w = u + αv bisects the angle between u and v ?
Answer : Option A
Explaination / Solution:
