1
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,…,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j], 1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,…,ai} whose elements sum to j.
Which of the following is valid for 2 <= i <= n and ai <= j <= W?
A
X[i, j] = X[i – 1, j] V X[i, j -ai]
B
X[i, j] = X[i – 1, j] V X[i – 1, j – ai]
C
X[i, j] = X[i – 1, j] V X[i, j – ai]
D
X[i, j] = X[i – 1, j] V X[i -1, j – ai]
2
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.
1.   f(int Y[10], int x) {
2.     int i, j, k;
3.     i = 0; j = 9;
4.     do {
5.             k =  (i + j) /2;
6.             if( Y[k] < x)  i = k; else j = k;
7.         } while(Y[k] != x && i < j);
8.     if(Y[k] == x) printf ("x is in the array ") ;
9.     else printf (" x is not in the array ") ;
10.  }
On which of the following contents of Y and x does the program fail?
A
Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
B
Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
C
Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
D
Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even
3
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.
1.   f(int Y[10], int x) {
2.     int i, j, k;
3.     i = 0; j = 9;
4.     do {
5.             k =  (i + j) /2;
6.             if( Y[k] < x)  i = k; else j = k;
7.         } while(Y[k] != x && i < j);
8.     if(Y[k] == x) printf ("x is in the array ") ;
9.     else printf (" x is not in the array ") ;
10.  }
The correction needed in the program to make it work properly is
A
Change line 6 to: if (Y[k]
B
Change line 6 to: if (Y[k]
C
Change line 6 to: if (Y[k]
D
Change line 7 to: } while ((Y[k]==x)&&(i
4
GATE CSE 1996
MCQ (Single Correct Answer)
+2
-0.6
A binary search tree is generated by inserting in order the following integers:

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

The number of nodes in the left subtree and right subtree of the root respectively is
A
(4, 7)
B
(7, 4)
C
(8, 3)
D
(3, 8)
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12