Programming and Data Structures - Online Test

Q1. The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
Answer : Option D
Explaination / Solution:

Pr eorder :30,20,10,15,25,23,39,35,42 
Inorder :10,15,20,23,25,30,35,39,42


Q2. What is the return value of f (p,p) if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.
int f (int & x, int c) {
c = c - 1;
if (c = 0) return 1;
x = x + 1;
return f (x,c)* x;
}
Answer : Option B
Explaination / Solution:



Q3. A certain computation generates two arrays a and b such that a[i] = f(i) for 0 ≤ i < n and b[i] = g(a[i]) for 0 ≤ i < n. Suppose this computation is decomposed into two concurrent processes X and Y such that X computes the array a and Y computes the array b. The processes employ two binary semaphores R and S, both initialized to zero. The array a is shared by the two processes. The structures of the processes are shown below.
Pr ocess X;                                              Pr ocess Y;
private i;                                                   private i;
   for(i = 0; i<n; i++){                                      for(i = 0; i<n; i++){
        a[i] = f(i);                                                      EntryY(R, S);
           ExitX(R, S);                                                    b[i] = g(a[i]);
}                                                                  }
Which one of the following represents the CORRECT implementations of ExitX and EntryY? 

Answer : Option C
Explaination / Solution:

For computing both the array a[] and b[], first element a[i] should be computed using which b[i] can be computed. So process X and Y should run in strict alteration manner, starting with X. This requirement meets with implementation of ExitX and EntryY given in option C.

Q4. 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:



Q5. 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)

Q6. 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. 

Q7. 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  

Q8. 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.

Q9.  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.

Q10. 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.