Q2. Which of the following statements is/are TRUE for undirected graphs?
P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.
Answer : Option CExplaination / Solution:
Q: Sum of degrees of all vertices = 2 × (number of edges)
Q4.Which one of the following is the tightest upper bound that represents the time complexity of
inserting an object into a binary search tree of n nodes?
Answer : Option CExplaination / Solution:
For skewed binary search tree on n nodes, the tightest upper bound to insert a node is O(n)
Q8.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?
Q9.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.
Q10.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.
Total Question/Mark :
Scored Mark :
Mark for Correct Answer : 1
Mark for Wrong Answer : -0.5
Mark for Left Answer : 0