Q1.An operator delete (i) for a binary heap data structure is to be designed to delete the item in
the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of
the array. If the heap tree has depth d (number of edges on the path from the root to the
farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal
of the element?
Answer : Option BExplaination / Solution:
Time complexity of heapification is O (height) =O(d)
Q2. G = (V, E ) is an undirected simple graph in which each edge has a distinct weight, and e is a
particular edge of G. Which of the following statements about the minimum spanning trees
(MSTs) of G is/are TRUE?
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
Answer : Option BExplaination / Solution: No Explaination.
Q3.Let X be a recursive language and Y be a recursively enumerable but not recursive language.
Let W and Z be two languages such that Y reduces to W , and Z reduces to X (reduction
means the standard many-one reduction). Which one of the following statements is TRUE?
Answer : Option CExplaination / Solution: No Explaination.
Q5.Consider the following proposed solution for the critical section problem. There are n
processes: P0. . . Pn-1. In the code, function pmax returns an integer not smaller than any of
its arguments. For all i, t[i] is initialized to zero.
Code for Pi:
do {
c[i]=1; t[i] = pmax(t[0],. . .,t[n-1])+1; c[i]=0;
for every j = i in {0,. . .,n-1} {
while (c[j]);
while (t[j] != 0 && t[j]<=t[i]);
}
Critical Section;
t[i]=0;
Remainder Section;
} while (true);
Which one of the following is TRUE about the above solution?
Answer : Option AExplaination / Solution: No Explaination.
Assuming that m and n point to valid NULL- terminated linked lists, invocation of join will
Answer : Option BExplaination / Solution:
While loop in Join Procedure moves the pointer ‘p’ to the last node of the list “n”. And at the
last statement, we are initializing the next of the last node of list n to start of list “m”.
But in some cases it may dereference to null pointer.
The code suffers from which one of the following problems:
Answer : Option DExplaination / Solution:
(A) is wrong. We don’t need to cast the result as void * is automatically and safely promoted
to any other pointer type in this case.
(B) It is discarded for obvious reason.
(C) is wrong, because dangling pointer is nothing but the pointer which is pointing to non-
existing memory (deallocated or deleted memory) which is not happening here.
(D) is the answer. When you are calling malloc second time, new location is assigned to x
and previous memory location is lost and now we don’t have no reference to that location
resulting in memory leak.
Total Question/Mark :
Scored Mark :
Mark for Correct Answer : 1
Mark for Wrong Answer : -0.5
Mark for Left Answer : 0