CS GATE 2016 PAPER 01 - Online Test
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 B
Explaination / 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 B
Explaination / 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 C
Explaination / Solution:
No Explaination.
Q4. Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals {S,
A} and terminals {a, b}.
S → aA {print 1}
S → a {print 2}
A → Sb {print 3}
Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:
Answer : Option C
Explaination / Solution:
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 A
Explaination / Solution:
No Explaination.
Q6. A cube is built using 64 cubic blocks of side one unit. After it is built, one cubic block is
removed from every corner of the cube. The resulting surface area of the body (in square
units) after the removal is.
Answer : Option D
Explaination / Solution:
Four blocks are needed for each direction(totally 3 directions) to build a bigger cube
containing 64 blocks. So area of one side of the bigger cube = 4 ×4 = 16units
There are 6 faces so total area = 6 × 16 = 96units
When cubes at the corners are removed they introduce new surfaces equal to exposes surfaces
so the area of the bigger cube does not change from 96
Q7. In a process, the number of cycles to failure decreases exponentially with an increase in load.
At a load of 80 units, it takes 100 cycles for failure. When the load is halved, it takes 10000
cycles for failure. The load for which the failure will happen in 5000 cycles is
Answer : Option B
Explaination / Solution:
From the data given we assume
Q8. A shaving set company sells 4 different types of razors, Elegance, Smooth, Soft and
Executive. 
Elegance sells at Rs. 48, Smooth at Rs. 63, Soft at Rs. 78 and Executive at Rs. 173 per piece.
The table below shows the numbers of each razor sold in each quarter of a year.
Which product contributes the greatest fraction to the revenue of the company in that year?
Answer : Option B
Explaination / Solution:
Total income from Elegance=48(27300+25222+28976+21012) = 4920480
Total income from Smooth=63(20009+19392+22429+18229 = 5043717
Total income from Soft=78(17602+18445+19544+16595) =5630508
Total income from Executive=173(9999+8942+10234+10109) =6796132
Q9. Let an be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of
the following is the recurrence relation for an?
Answer : Option B
Explaination / Solution:
