1
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
Consider the following C functions:
int f1(int n){
 if(n == 0 || n == 1){
    return n;
 }
 return (2 * f1(n - 1) + 3 * f1(n - 2));
}
int f2(int n){
 int i;
 int X[N], Y[N], Z[N];
 X[0] = Y[0] = Z[0] = 0;
 X[1] = 1; Y[1] = 2; Z[1] = 3;
 for(i = 2; i <= n; i++){
  X[i] = Y[i - 1] + Z[i - 2];
  Y[i] = 2 * X[i];
  Z[i] = 3 * X[i];
 }
 return X[n];
}
f1(8) and f2(8) return the values
A
1661 and 1640
B
59 and 59
C
1640 and 1640
D
1640 and 1661
2
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
The subset-sum problem is defined as follows:
Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to W. An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?
A
Q solves the subset-sum problem in polynomial time when the input is encoded in unary
B
Q solves the subset-sum problem in polynomial time when the input is encoded in binary
C
The subset sum problem belongs to the class NP
D
The subset sum problem is NP-hard
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 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
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12