1. A basket of fruit is being arranged out of apples, bananas, and oranges. What is the smallest number of pieces of fruit that should be put in the basket in order to guarantee that either there are at least 8 apples or at least 6 bananas or at least 9 oranges?
(a) 9 (b) 10 (c) 20 (d) 21
2. A man has three cats. At least one is male. What is the probability that all three are male?
(a) 1/2 (b) 1/7 (c) 1/8 (d) 3/8
3. You are given two sorting algorithms A and B that work in time O(n log n) and O(n^2), respectively. Consider the following statements:
(I) Algorithm A will sort any array faster than algorithm B.
(II) On an average, algorithm A will sort a given array faster than algorithm B.
(III) If we need to implement one of the two as the default sorting algorithm in a
system, algorithm A will always be preferable to algorithm B.
Which of the statements above are true?
(a) I, II and III (b) I and III (c) II and III (d) None of them
The next two questions are based on the following program.
procedure mystery (A : array [1..100] of int)
int i,j,position,tmp;
begin
for j := 1 to 100 do
position := j;
for i := j to 100 do
if (A[i] > A[position]) then
position := i;
endfor
tmp := A[j];
A[j] := A[position];
A[position] := tmp;
endfor
end
5. When the procedure terminates, the array A has been:
(a) Reversed
(c) Sorted in descending order
(b) Left unaltered
(d) Sorted in ascending order
6. The number of times the test A[i] > A[position] is executed is:
(a) 100 (b) 5050 (c) 10000 (d) Depends on contents of A
7. The 12 houses on one side of a street are numbered with even numbers starting at 2 and
going up to 24. A free newspaper is delivered on Monday to 3 different houses chosen
at random from these 12. Find the probability that at least 2 of these newspapers are
delivered to houses with numbers strictly greater than 14.
(a) 7/11 (b) 5/12 (c) 4/11 (d) 5/22
8. In the code fragment, start and end are integer values and prime(x) is a function that returns true if x is a prime number and false otherwise.
i := 0; j := 0; k := 0;
for (m := start; m <= end; m := m+1){
k := k + m;
if (prime(m)){
i := i + m;
}else{
j := j + m;
}
}
At the end of the loop:
(a) k < i+j (b) k = i+j (c) k > i+j (d) Depends on start and end
9. Suppose each edge of an undirected graph is coloured using one of three colours — red, blue or green. Consider the following property of such graphs: if any vertex is the endpoint of a red coloured edge, then it is either an endpoint of a blue coloured edge or not an endpoint of any green coloured edge. If a graph G does not satisfy this property, which of the following statements about G are valid?
(a) There is a red coloured edge.
(b) Any vertex that is the endpoint of a red coloured edge is also the endpoint of a green coloured edge.
(c) There is a vertex that is not an endpoint of any blue coloured edge but is an endpoint of a green coloured edge and a red coloured edge.
(d) (a) and (c).
10. An undirected graph has 10 vertices labelled {1, 2, . . . , 10} and 37 edges. Vertices 1, 3, 5, 7, 9 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 10?
(a) 5 (b) 6 (c) 7 (d) 8