CS GATE 2013 - Online Test
Q1. 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
Answer : Option B
Explaination / Solution:
Q2. The number of elements that can be sorted in Θ(logn) time using heap sort is
Answer : Option A
Explaination / Solution:
After constructing a max-heap in the heap sort , the time to extract maximum element and
then heapifying the heap takes Θ(log n) time by which we could say that Θ(log n) time is
required to correctly place an element in sorted array. If Θ(logn) time is taken to sort using
heap sort, then number of elements that can be sorted is constant which is Θ(1)
Q3. The line graph L(G) of a simple graph G is defined as follows:
• There is exactly one vertex v(e) in L(G) for each edge e in G.
• For any two edges e and e’ in G, L(G) has an edge between v(e) and v(e’), if and only if e
and e’ are incident with the same vertex in G.
Which of the following statements is/are TRUE?
(P) The line graph of a cycle is a cycle.
(Q) The line graph of a clique is a clique.
(R) The line graph of a planar graph is planar.
(S) The line graph of a tree is a tree.
Answer : Option A
Explaination / Solution:
P) The line graph of a cycle is a cycle
R) Line graph of planar graph need not be planar always. Consider the following example.
Consider the following planar graph (star graph)
S) Hence line graph of planar graph need not be planar(Here we got K5 which is not planar).
The line graph of a tree need not be tree.
Q4. The procedure given below is required to find and replace certain characters inside an input
character string supplied in array A. The characters to be replaced are supplied in array oldc,
while their respective replacement characters are supplied in array newc. Array A has a fixed
length of five characters, while arrays oldc and newc contain three characters each. However, the
procedure is flawed
void find _ and _ replace (char * A, char *oldc, char * newc) {
for (int i=0; i<5; i++)
for (int j=0; j<3; j++)
if (A[i] == oldc[j]) A[i] = newc[j];
}
The procedure is tested with the following four test cases
(1) oldc = "abc", newc = "dab" (2) oldc = "cde", newc = "bcd"
(3) oldc = "bca", newc = "cda" (4) oldc = "abc", newc = "bac"
The tester now tests the program on all input strings of length five consisting of characters
‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with the
four test cases given above, how many test cases will be able to capture the flaw?
Answer : Option B
Explaination / Solution:
Flaw in this given procedure is that one character of Array ‘A’ can be replaced by more than
one character of newc array, which should not be so.Test case (3) and (4) identifies this flaw
as they are containing ‘oldc’ and ‘newc’ array characters arranged in specific manner.
Following string can reflect flaw, if tested by test case (3).
Likewise single character ‘b’ in A is replaced by ‘c’ and then by ‘d’.
Same way test case (4) can also catch the flaw
Q5. The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed
void find _ and _ replace (char * A, char *oldc, char * newc) {
for (int i=0; i<5; i++)
for (int j=0; j<3; j++)
if (A[i] == oldc[j]) A[i] = newc[j];
}
The procedure is tested with the following four test cases
(1) oldc = "abc", newc = "dab" (2) oldc = "cde", newc = "bcd"
(3) oldc = "bca", newc = "cda" (4) oldc = "abc", newc = "bac"
If array A is made to hold the string “abcde”, which of the above four test cases will be
successful in exposing the flaw in this procedure?
Answer : Option C
Explaination / Solution:
Now for string “abcde” in array A, both test case (3) and (4) will be successful in finding the
flaw, as explained in above question.
Q6. What will be the maximum sum of 44, 42, 40, ... ?
Answer : Option C
Explaination / Solution:
The maximum sum is the sum of 44, 42,- - - - -2.
The sum of ‘n’ terms of an AP
= n/2 [2a+(n-1)d]
In this case, n = 22, a = 2 and d = 2
∴ Sum = 11[4+21×2] = 11×46 = 506
Q7. 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
Answer : Option C
Explaination / Solution:
Let the total distance covered be ‘D’
Now, average speed = D/Total time taken
Q8. Function f is known at the following points
The value of 
computed using the trapezoidal rule is
computed using the trapezoidal rule is
Answer : Option D
Explaination / Solution:
Q9. Which one of the following functions is continuous at x = 3 ?
Answer : Option A
Explaination / Solution:
f(x) is continuous at x 3
Q10. Which one of the following does NOT equal 
Answer : Option A
Explaination / Solution:
If matrix B is obtained from matrix A by replacing the 1th row by itself plus k times the mth row, for 1 ≠ m then det(B)=det(A). With this property given matrix is equal to the matrices
given in options (B),(C) and (D).
