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?
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.
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 CExplaination / 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.
Q5. The number of elements that can be sorted in Θ(logn) time using heap sort is
Answer : Option AExplaination / 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)
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
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 BExplaination / 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
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 CExplaination / 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 AExplaination / 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 AExplaination / Solution:
The In order Traversal of Ternary Tree is done as follows:
Left → Root → Middle → Right
So the nodes are visited in SQPTRWUV order.
Total Question/Mark :
Scored Mark :
Mark for Correct Answer : 1
Mark for Wrong Answer : -0.5
Mark for Left Answer : 0