Computer Science Engineering - Online Test
Q1. 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.
Q2. The grammar S → aSa|bS|c is
Answer : Option B
Explaination / Solution:
No Explaination.
Q3. 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
Q4. Let L = {w ∈ (0 + 1)* | w has even number of 1s}, i.e. L is the set of all bit strings
with even number of 1s. Which one of the regular expressions below represents
L?
Answer : Option A
Explaination / Solution:
No Explaination.
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. Let A be a square matrix size n × n. Consider the following pseudocode. What is the
expected output?
C = 100;
for i = 1 to n do
for j = 1 to n do
{
Temp = A[ i ] [ j ] + C ;
A [ i ] [ j ] = A [ j ] [ i ] ;
A [ j ] [ i ] = Temp – C ;
}
for i = 1 to n do
for j = 1 to n do
output (A[ i ] [ j ]);
Answer : Option A
Explaination / Solution:
In the computation of given pseudo code for each row and column of Matrix A, each upper
triangular element will be interchanged by its mirror image in the lower triangular and after
that the same lower triangular element will be again re-interchanged by its mirror image in
the upper triangular, resulting the final computed Matrix A same as input Matrix A.
Q7. Consider the languages L1 = {0i1j | i≠j}. L2 = {0i1j | i=j}. L3 = {0i1j | i=2j+1}. L4 = {0i1j | i≠2j}. Which one of the following statements is true?
Answer : Option A
Explaination / Solution:
No Explaination.
Q8. Consider the following rooted tree with the vertex labelled P as the root
The order in which the nodes are visited during an in-order traversal of the tree is
Answer : Option A
Explaination / Solution:
The In order Traversal of Ternary Tree is done as follows:
Left → Root → Middle → Right
So the nodes are visited in SQPTRWUV order.
Q9. Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w.
What is the minimum number of states in a non-deterministic finite automaton
that accepts L?
Answer : Option B
Explaination / Solution:
No Explaination.
Q10. You have an array of n elements. Suppose you implement quick sort by always choosing the
central element of the array as the pivot. Then the tightest upper bound for the worst case
performance is
Answer : Option A
Explaination / Solution:
The Worst case time complexity of quick sort is O(n2). This will happen when the elements
of the input array are already in order (ascending or descending), irrespective of position of
pivot element in array.
