GATE CSE 2003
Q1.
In the following C program fragment, j, k, n and TwoLog_n are integer variables, and A is an array of integers. The variable n is initialized to an integer \geq 3, and TwoLog_n is initialized to the value of 2*\left \lceil log_{2}n \right \rceil for (k = 3; k < = n; k++) A[k] = 0; for (k = 2; k < = TwoLog_n; k++) for (j = k + 1; j < = n; j++) A[j] = A[j] || (j % k); for (j = 3; j < = n; j++) if (!A[j]) printf("%d", j); The set of number printed by this program fragment isQ2.
Assume the following C variable declaration int *A [10], B[10][10]; Of the following expressions I A[2] II A[2][3] III B[1] IV B[2][3] which will not give compile-time errors if used as left hand sides of assignment statements in a C program?Q3.
Let T(n) be the number of different binary search trees on n distinct elements. Then T(n)=\sum_{k=1}^{n}T(k-1)T(x), where x isQ4.
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the inorder transversal sequence of the resultant tree ?Q5.
Consider the following 2-3-4 tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree What is the result of inserting G in the above tree ?Q6.
The cube root of a natural number n is defined as the largest natural number m such that m^{3}\leq n. The complexity of computing the cube root of n(n is represented in binary notation) isQ7.
Consider the following three claims 1. (n+k)^{m}=\ominus (n^{m}) , where k and m are constants 2. 2^{n+1}=O(2^{n}) 3. 2^{2n+1}=O(2^{n}) Which of these claims are correct?Q8.
n couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party isQ9.
m identical balls are to be placed in n distinct bags. You are given that m \geqkn, where k is a natural number \geq1. In how many ways can the balls be placed in the bags if each bag must contain at least k balls?Q10.
Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, B and C are there such that (i) each is sorted in ascending order, (ii) B has 5 and C has 3 elements, and (iii) the result of merging B and C gives A?