### SET 5

Question 1

**Consider the following segment of C-code: **

int j, n;

j = 1;

while (j <= n)

j = j*2;

The number of comparisons made in the execution of the loop for any n > 0 is: Base of Log is 2 in all options.

A : ceil(log n) +2

B : n

C : ceil(log n)

D : floor(log n) +1

Answer Discuss it!

.

Correct answer is :A

Solution :

We can see it by taking few examples like n = 1, n = 3, etc.

For example, for n=5 we have the following (4) comparisons:

------------------------

1 <= 5 (T)

2 <= 5 (T)

4 <= 5 (T)

8 <= 5 (F)

------------------------

CEIL(log_2 n)+2 = CEIL(log_2 5) + 2 = CEIL(2.3) + 2 = 3 + 2 = 5

Question 2

**Consider the following C function, what is the output? **

int f(int n)

{

static int r = 0;

if (n <= 0)

return 1;

if (n > 3)

{

r = n;

return f(n-2)+2;

}

return f(n-1)+r;

}

int main()

{

printf("%d", f(5));

}

A : 5

B : 7

C : 9

D : 18

Answer Discuss it!

.

Correct answer is :D

Question 3

**Consider the following C program segment where CellNode represents a node in a binary tree: **

struct CellNode

{

struct CellNOde *leftChild;

int element;

struct CellNode *rightChild;

};

int GetValue(struct CellNode *ptr)

{

int value = 0;

if (ptr != NULL)

{

if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL))

value = 1;

else

value = value + GetValue(ptr->leftChild) + GetVal

A : the number of nodes in the tree

B : the number of internal nodes in the tree

C : the number of leaf nodes in the tree

D : the height of the tree

Answer Discuss it!

.

Correct answer is :C

Question 4

**Consider the following C code segment: **

int IsPrime(n)

{

int i,n;

for(i=2;i<=sqrt(n);i++)

if(n%i == 0)

{printf(Not Prime\n); return 0;}

return 1;

}

Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

A : T(n) = O(sqrt(n)) and T(n) = Ω(sqrt(n))

B : T(n) = O(sqrt(n)) and T(n) = Ω(1)

C : T(n) = O(n) and T(n) = Ω(sqrt(n))

D : None of the above

Answer Discuss it!

.

Correct answer is :B

Solution :

Big O notation describes the upper bound and Big Omega notation describes the lower bound for an algorithm.

The for loop in the question is run maximum sqrt(n) times and minimum 1 time. Therefore, T(n) = O(sqrt(n)) and T(n) = Ω(1)

Question 5

**Which combination of the integer variables x, y and z makes the variable a get the value 4 in the following expression?**

a = ( x > y ) ? (( x > z ) ? x : z) : (( y > z ) ? y : z )

A : x = 3, y = 4, z = 2

B : x = 6, y = 5, z = 3

C : x = 6, y = 3, z = 5

D : x = 5, y = 4, z = 5

Answer Discuss it!

.

Correct answer is :A

Solution :

The given expression assigns maximum among three elements (x, y and z) to a.

Question 6

**Which of the following are true? **

I. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation

II. Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions

III. Recursion in programming languages cannot be implemented with dynamic
storage allocation

IV. Nesting of procedures/functions and recursion require a dynamic heap
allocation scheme and cannot be implemented with a stack-based allocation
scheme for activation records

V. Programming languages which permit a function to return a function as its
result cannot be implemented with a stack-based storage allocation scheme
for activation records

A : II and V only

B : I,III and IV only

C : I,II and V only

D : II,III and V only

Answer Discuss it!

.

Correct answer is :A

Question 7

**What is printed by the following C program? **

int f(int x, int *py, int **ppz)

{

int y, z;

**ppz += 1;

z = **ppz;

*py += 2;

y = *py;

x += 3;

return x + y + z;

}

void main()

{

int c, *b, **a;

c = 4;

b = &c;

a = &b;

printf( "%d", f(c,b,a));

getchar();

}

A : 18

B : 19

C : 21

D : 22

Answer Discuss it!

.

Correct answer is :B

Solution :

/* Explanation for the answer */

/*below line changes value of c to 5. Note that x remains unaffected
by this change as x is a copy of c and address of x is different from c*/

**ppz += 1

/* z is changed to 5*/

z = **ppz;

/* changes c to 7, x is not changed */

*py += 2;

/* y is changed to 7*/

y = *py;

/* x is incremented by 3 */

x += 3;

/* return 7 + 7 + 5*/

return x + y + z;

Question 8

**Choose the correct option to fill ?1 and ?2 so that the program below prints an input string in reverse order. Assume that the input string is terminated by a newline character.**

void reverse(void)

{

int c;

if (?1) reverse();

?2

}

int main()

{

printf ("Enter Text ") ;

printf ("\n") ;

reverse();

printf ("\n") ;

}

A : ?1 is (getchar() != \n)

?2 is getchar(c);

B : ?1 is (c = getchar() ) != \n)

?2 is getchar(c);

C : ?1 is (c != \n)

?2 is putchar(c);

D : ?1 is ((c = getchar()) != \n)

?2 is putchar(c);

Answer Discuss it!

.

Correct answer is :D

Solution :

getchar() is used to get the input character from the user and putchar() to print the entered character, but before printing reverse is called again and again until
is entered. When
is entered the functions from the function stack run putchar() statements one by one. Therefore, last entered character is printed first.

Question 9

**The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution? **

struct node
{
int value;
struct node *next;
};
void rearrange(struct node *list)
{
struct node *p, * q;
int temp;
if ((!list) || !list->next)
return;
p = list;
q = list->next;
while(q)
{
temp = p->value;
p->value = q->value;
q->value = temp;
p = q->next;
q = p?p->next:0;
}
}

A : 1,2,3,4,5,6,7

B : 2,1,4,3,6,5,7

C : 1,3,2,5,4,7,6

D : 2,3,4,5,6,7,1

Answer Discuss it!

.

Correct answer is :B

Solution :

The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.

Question 10

**Consider the following C program**

int f1(int n)

{

if(n == 0 || n == 1)

return n;

else

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] ;

}

The running time of f1(n) and f2(n) are

A : θ (n) and θ (n)

B : θ (2^{n}) and θ (n)

C : θ (n) and θ (2^{n})

D : θ (2^{n}) and θ (2^{n})

Answer Discuss it!

.

Correct answer is :B

Solution :

For f1(), let T(n) be the function for time complexity.

T(n) = T(n-1) + T(n-2)

Above recursion is a standard one for Fibonacci Numbers. After solving the recursion, we get

T(n) = 1/sqrt(5)[(1 + sqrt(5))/2]^n - 1/sqrt(5)[(1 - sqrt(5))/2]^n

Above recursion can also be written as ?(1.618.^n)

In f2(), there is a single loop, so time complexity is ?(n)

Among all the 4 given choices, (B) looks closest.

Question 11

**Consider the following C program**

int f1(int n)

{

if(n == 0 || n == 1)

return n;

else

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

Answer Discuss it!

.

Correct answer is :C

Solution :

Both functions perform same operation, so output is same, means either (B) or (C) is correct.

f1(2) = 2*f1(1) + 3*f1(0) = 2

f1(3) = 2*f1(2) + 3*f1(1) = 2*2 + 3*1 = 7

f1(4) = 2*f1(3) + 3*f1(2) = 2*7 + 3*2 = 20

f1(5) = 2*f1(4) + 3*f1(3) = 2*20 + 3*7 = 40 + 21 = 61

We can skip after this as the only remaining choice is (C)

f1(6) = 2*f1(5) + 3*f1(4) = 2*61 + 3*20 = 122 + 60 = 182

f1(7) = 2*f1(6) + 3*f1(5) = 2*182 + 3*61 = 364 + 183 = 547

f1(8) = 2*f1(7) +

Question 12

**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

Answer Discuss it!

.

Correct answer is :C

Solution :

(C) The above program doesnt work for the cases where element to be searched is the last element of Y[] or greater than the last element (or maximum element) in Y[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false.

Question 13

**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] < x) i = k + 1; else j = k-1;

B : Change line 6 to: if (Y[k] < x) i = k - 1; else j = k+1;

C : Change line 6 to: if (Y[k] <= x) i = k; else j = k;

D : Change line 7 to: } while ((Y[k] == x) && (i < j));

Answer Discuss it!

.

Correct answer is :A

Solution :

Below is the corrected function

f(int Y[10], int x) {
int i, j, k;
i = 0; j = 9;
do {
k = (i + j) /2;
if( Y[k] < x) i = k + 1; else j = k 1;
} while(Y[k] != x && i < j);
if(Y[k] == x) printf ('x is in the array ');
else printf ('x is not in the array ') ;
}

Question 1

int j, n;

j = 1;

while (j <= n)

j = j*2;

The number of comparisons made in the execution of the loop for any n > 0 is: Base of Log is 2 in all options.

.

Correct answer is :A

Solution :

We can see it by taking few examples like n = 1, n = 3, etc.

For example, for n=5 we have the following (4) comparisons:

------------------------

1 <= 5 (T)

2 <= 5 (T)

4 <= 5 (T)

8 <= 5 (F)

------------------------

CEIL(log_2 n)+2 = CEIL(log_2 5) + 2 = CEIL(2.3) + 2 = 3 + 2 = 5

Question 2

int f(int n)

{

static int r = 0;

if (n <= 0)

return 1;

if (n > 3)

{

r = n;

return f(n-2)+2;

}

return f(n-1)+r;

}

int main()

{

printf("%d", f(5));

}

.

Correct answer is :D

Question 3

struct CellNode

{

struct CellNOde *leftChild;

int element;

struct CellNode *rightChild;

};

int GetValue(struct CellNode *ptr)

{

int value = 0;

if (ptr != NULL)

{

if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL))

value = 1;

else

value = value + GetValue(ptr->leftChild) + GetVal

.

Correct answer is :C

Question 4

int IsPrime(n)

{

int i,n;

for(i=2;i<=sqrt(n);i++)

if(n%i == 0)

{printf(Not Prime\n); return 0;}

return 1;

}

Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

.

Correct answer is :B

Solution :

Big O notation describes the upper bound and Big Omega notation describes the lower bound for an algorithm.

The for loop in the question is run maximum sqrt(n) times and minimum 1 time. Therefore, T(n) = O(sqrt(n)) and T(n) = Ω(1)

Question 5

a = ( x > y ) ? (( x > z ) ? x : z) : (( y > z ) ? y : z )

.

Correct answer is :A

Solution :

The given expression assigns maximum among three elements (x, y and z) to a.

Question 6

I. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation

II. Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions

III. Recursion in programming languages cannot be implemented with dynamic storage allocation

IV. Nesting of procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records

V. Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records

.

Correct answer is :A

Question 7

int f(int x, int *py, int **ppz)

{

int y, z;

**ppz += 1;

z = **ppz;

*py += 2;

y = *py;

x += 3;

return x + y + z;

}

void main()

{

int c, *b, **a;

c = 4;

b = &c;

a = &b;

printf( "%d", f(c,b,a));

getchar();

}

.

Correct answer is :B

Solution :

/* Explanation for the answer */

/*below line changes value of c to 5. Note that x remains unaffected by this change as x is a copy of c and address of x is different from c*/

**ppz += 1

/* z is changed to 5*/

z = **ppz;

/* changes c to 7, x is not changed */

*py += 2;

/* y is changed to 7*/

y = *py;

/* x is incremented by 3 */

x += 3;

/* return 7 + 7 + 5*/

return x + y + z;

Question 8

void reverse(void)

{

int c;

if (?1) reverse();

?2

}

int main()

{

printf ("Enter Text ") ;

printf ("\n") ;

reverse();

printf ("\n") ;

}

.

Correct answer is :D

Solution :

getchar() is used to get the input character from the user and putchar() to print the entered character, but before printing reverse is called again and again until is entered. When is entered the functions from the function stack run putchar() statements one by one. Therefore, last entered character is printed first.

Question 9

struct node { int value; struct node *next; }; void rearrange(struct node *list) { struct node *p, * q; int temp; if ((!list) || !list->next) return; p = list; q = list->next; while(q) { temp = p->value; p->value = q->value; q->value = temp; p = q->next; q = p?p->next:0; } }

.

Correct answer is :B

Solution :

The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.

Question 10

int f1(int n)

{

if(n == 0 || n == 1)

return n;

else

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] ;

}

The running time of f1(n) and f2(n) are

.

Correct answer is :B

Solution :

For f1(), let T(n) be the function for time complexity.

T(n) = T(n-1) + T(n-2)

Above recursion is a standard one for Fibonacci Numbers. After solving the recursion, we get

T(n) = 1/sqrt(5)[(1 + sqrt(5))/2]^n - 1/sqrt(5)[(1 - sqrt(5))/2]^n

Above recursion can also be written as ?(1.618.^n)

In f2(), there is a single loop, so time complexity is ?(n)

Among all the 4 given choices, (B) looks closest.

Question 11

int f1(int n)

{

if(n == 0 || n == 1)

return n;

else

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

.

Correct answer is :C

Solution :

Both functions perform same operation, so output is same, means either (B) or (C) is correct.

f1(2) = 2*f1(1) + 3*f1(0) = 2

f1(3) = 2*f1(2) + 3*f1(1) = 2*2 + 3*1 = 7

f1(4) = 2*f1(3) + 3*f1(2) = 2*7 + 3*2 = 20

f1(5) = 2*f1(4) + 3*f1(3) = 2*20 + 3*7 = 40 + 21 = 61

We can skip after this as the only remaining choice is (C)

f1(6) = 2*f1(5) + 3*f1(4) = 2*61 + 3*20 = 122 + 60 = 182

f1(7) = 2*f1(6) + 3*f1(5) = 2*182 + 3*61 = 364 + 183 = 547

f1(8) = 2*f1(7) +

Question 12

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?

.

Correct answer is :C

Solution :

(C) The above program doesnt work for the cases where element to be searched is the last element of Y[] or greater than the last element (or maximum element) in Y[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false.

Question 13

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

.

Correct answer is :A

Solution :

Below is the corrected function

f(int Y[10], int x) { int i, j, k; i = 0; j = 9; do { k = (i + j) /2; if( Y[k] < x) i = k + 1; else j = k 1; } while(Y[k] != x && i < j); if(Y[k] == x) printf ('x is in the array '); else printf ('x is not in the array ') ; }