CS GATE 2015 - Online Test
Q1. In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of
the following statements is true?
Answer : Option B
Explaination / Solution:
Since, every edge in a tree is bridge
(A) is false
Since, every edge in a complete graph
kn (n ≥ 3) is not a bridge (c) is false
Let us consider the following graph G:
This graph has a bridge i.e., edge „e‟ and a cycle of length „3‟
(D) is false
Since, in a cycle every edge is not a bridge
(B) is true
Q2. Which one of the following assertions concerning code inspection and code walkthrough is
true?
Answer : Option A
Explaination / Solution:
No Explaination.
Q3. Consider the intermediate code given below.
The number of nodes and edges in the control-flow-graph constructed for the above code,
respectively, are
Answer : Option B
Explaination / Solution:
No Explaination.
Q4. Consider the following routing table at an IP router:
For each IP address in Group I identify the correct choice of the next hop from Group II using
the entries from the routing table above.
Answer : Option A
Explaination / Solution:
No Explaination.
Q5. Consider two relations R1(A,B) with the tuples (1.5), (3,7) and R2 (A,C) = (1,7), (4,9).
Assume that R(A,B,C) is the full natural outer join of R1 and R2 . Consider the following
tuples of the form (A,B,C): a = (1.5,null), b = (1,null,7) c = (3,null,9), d = (4,7,null), e = (1,5,7), f = (3,7,null), g = (4,null,9).
Which one of the following statements is correct?
Answer : Option C
Explaination / Solution:
Q6. A graph is self-complementary if it is isomorphic to its complement For all self-complementary
graphs on n vertices, n is
Answer : Option D
Explaination / Solution:
An n vertex self complementary graph has exactly half number of edges of the complete
graph i.e., n(n-1)/4 edges. Since n(n-1) must be divisible by 4 , n must be congruent to 0 or
1 module 4.
Q7. In a triangle PQR,PS is the angle bisector of ∟QPR and ∟QPS = 600 .
What is the length of PS?
Answer : Option B
Explaination / Solution:
No Explaination.
Q8. If the list of letters, P,R,S,T,U is an arithmetic sequence, which of the following are also in
arithmetic sequence?
I . 2P, 2R, 2S, 2T, 2U
II . P - 3,R - 3,S - 3,T - 3,U - 3
III. P2 , R2 , S2 ,T2 ,U2
Answer : Option B
Explaination / Solution:
Let us take the numbers as 3,4,5,6,7 n=1 and they are in arithmetic sequence
I. 6, 8,10,12,14 n=2 and they are in arithmetic sequence
II. 0,1,2,3,4 n=1 and they are in arithmetic sequence
III. 9,16,25,36,49 n=7,9,11,13 they are not in an arithmetic sequence
Q9. Consider a function f(x) = 1-|x| on -1≤ x ≤ 1. The value of x at which the function attains a
maximum, and the maximum value of the function are.
Answer : Option C
Explaination / Solution:
Q10. Four branches of a company are located at M.N.O and P. M is north of N at a distance of
4km: P is south of O at a distance of 2 km: N is southeast of O by 1 km. What is the distance
between M and P in km?
Answer : Option A
Explaination / Solution:
