C Programming and Data Structures Programming in C Page 1 of 107

Chapter 1 Programming in C
1.1 Basics
Q 1. int x =126 , y =105; 2025Set2
do {
if (x > y ) x =x - y ;
else y =y - x ;
}
while ( x != y );

printf ( " % d " ,x );

The output of the given C code segment is . (Answer in integer)

Q 2. Consider the following C program 2004

main ()
{
int x , y , m , n ;
scanf ( " % d % d " , &x , & y );
/* Assume x >0 and y >0 */
m = x; n = y;
while ( m != n )
{
if ( m > n )
m = m-n;
else
n = n-m;
}
printf ( " % d " , n );
}

The program computes

A. x + y using repeated subtraction
B. x mod y using repeated subtraction
C. the greatest common divisor of x and y
D. the least common multiple of x and y
Q 3. What does the following algorithm approximate? (Assume m > 1, ϵ > 0). 2004
x = m;
y = 1;
while (x - y > ϵ)
{
x = ( x + y )/2;
y = m/x;
}
print ( x );
1 1
A. log m B. m2 C. m 2 D. m 3

Q 4. Consider the following C program: 2024Set1

# include < stdio .h >
int main (){
int a = 6;

1
 C Programming and Data Structures Programming in C Page 2 of 107

int b = 0;
while ( a < 10) {
a = a / 12 + 1;
a += b ;
}
printf ( " % d " , a );
return 0;
}

Which one of the following statements is CORRECT?

A. The program prints 9 as output
B. The program prints 10 as output
C. The program gets stuck in an infinite loop
D. The program prints 6 as output

Q 5. Consider the following C program. 2017Set2

# include < stdio .h >
int main () {
int m =10;
int n , n1 ;
n =++ m ;
n1 = m ++;
n - -;
-- n1 ;
n -= n1 ;
printf ( " % d " , n );
return 0;
}

The output of the program is .

Q 6. Consider the following C code. Assume that unsigned long int type length is 64 bits. 2018
unsigned long int fun ( unsigned long int n ) {
unsigned long int i , j =0 , sum = 0;
for ( i = n ; i >1; i = i /2) j ++;
for ( ; j >1; j = j /2) sum ++;
return sum ;
}

The value returned when we call fun with the input 240 is
A. 4 B. 5 C. 6 D. 40
Q 7. Consider the following C function definition. 2024Set1
int f ( int x , int y ) {
for ( int i =0; i < y ; i ++) {
x = x + x + y;
}
return x ;
}

Which of the following statements is/are TRUE about the above function?
A. If the inputs are x = 20, y = 10, then the return value is greater than 220
B. If the inputs are x = 20, y = 20, then the return value is greater than 220
C. If the inputs are x = 20, y = 10, then the return value is less than 210

2
 C Programming and Data Structures Programming in C Page 3 of 107

D. If the inputs are x = 10, y = 20, then the return value is greater than 220

Q 8. Consider the following ANSI C program. 2021Set1

# include < stdio .h >
int main ()
{
int i , j , count ;
count =0;
i =0;
for ( j = -3; j <=3; j ++)
{
if (( j >= 0) && ( i ++))
count = count + j ;
}
count = count + i ;
printf ( " % d " , count );
return 0;
}

Which one of the following options is correct?

A. The program will not compile successfully
B. The program will compile successfully and output 10 when executed
C. The program will compile successfully and output 8 when executed
D. The program will compile successfully and output 13 when executed
Q 9. Consider the following C program : 2019
# include < stdio .h >
int jumble ( int x , int y ){
x = 2* x + y ;
return x ;
}
int main (){
int x =2 , y =5;
y = jumble (y , x );
x = jumble (y , x );
printf ( " % d \ n " ,x );
return 0;
}

The value printed by the program is .

Q 10. Consider the following C program: 2019
# include < stdio .h >
int main () {
float sum = 0.0 , j =1.0 , i =2.0;
while ( i / j > 0.0625) {
j=j+j;
sum = sum + i / j ;
printf ( " % f \ n " , sum );
}
return 0;
}

The number of times the variable sum will be printed, when the above program is executed, is .

3
 C Programming and Data Structures Programming in C Page 4 of 107

Q 11. Consider the following C function. 2003

float f ( float x , int y ) {
float p , s ; int i ;
for ( s =1 , p =1 , i =1; i < y ; i ++) {
p *= x / i ;
s += p ;
}
return s ;
}

For large values of y, the return value of the function f best approximates
A. xy B. ex C. ln(1 + x) D. xx

Q 12. Consider the function func shown below: 2014Set2

int func ( int num ) {
int count = 0;
while ( num ) {
count ++;
num > >= 1;
}
return ( count );
}

The value returned by func(435) is .

Q 13. Which combination of the integer variables x, y and z makes the variable a get the value 4 in the 2008
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

Q 14. What will be the output of the following C program segment? 2012
char inChar = ‘A ’;
switch ( inChar ) {
case ‘A ’ : printf ( " Choice A \ n " );
case ‘B ’ :
case ‘C ’ : printf ( " Choice B " );
case ‘D ’ :
case ‘E ’ :
default : printf ( " No Choice " );
}

A. No Choice
B. Choice A
C. Choice A
Choice B No Choice
D. Program gives no output as it is erroneous

Q 15. Consider the following C program: 2015Set3

# include < stdio .h >
int main ()
{
int i , j , k = 0;
j =2 * 3 / 4 + 2.0 / 5 + 8 / 5;

4
 C Programming and Data Structures Programming in C Page 5 of 107

k -= - - j ;
for ( i =0; i <5; i ++)
{
switch ( i + k )
{
case 1:
case 2: printf ( " \ n % d " , i + k );
case 3: printf ( " \ n % d " , i + k );
default : printf ( " \ n % d " , i + k );
}
}
return 0;
}

The number of times printf statement is executed is .

Q 16. Suppose n and p are unsigned int variables in a C program. We wish to set p to n C3 . If n is large, 2014Set2
which one of the following statements is most likely to set p correctly?
A. p = n * (n-1) * (n-2) / 6;
B. p = n * (n-1) / 2 * (n-2) / 3;
C. p = n * (n-1) / 3 * (n-2) / 2;
D. p = n * (n-1) * (n-2) / 6.0;

Q 17. Consider the following C program. 2017Set1

# include < stdio .h >
# include < string .h >

void printlength ( char *s , char * t ) {

unsigned int c =0;
int len = (( strlen ( s ) - strlen ( t )) > c ) ? strlen ( s ) : strlen ( t );
printf ( " % d \ n " , len );
}

void main () {
char * x = " abc " ;
char * y = " defgh " ;
printlength (x , y );
}

Recall that strlen is defined in string.h as returning a value of type size t, which is an unsigned
int. The output of the program is .
Q 18. What is printed by the following ANSI C program? 2022
# include < stdio .h >
int main ( int argc , char * argv []){
char a = ‘P ’;
char b = ‘x ’;
char c = ( a & b ) + ‘* ’;
char d = ( a | b ) - ‘- ’;
char e = ( a ^ b ) + ‘+ ’;
printf ("% c % c % c \ n " , c , d , e );
return 0;
}

5
 C Programming and Data Structures Programming in C Page 6 of 107

ASCII encoding for relevant characters is given below

A B C ... Z a b c ... z ∗ + –
65 66 67 . . . 90 97 98 99 . . . 122 42 43 45
A. z K S B. 122 75 83 C. * - + D. P x +
Q 19. Consider the following C program: 2025Set1
# include < stdio .h >
int gate ( int n ) {
int d , t , newnum , turn ;
newnum = turn = 0; t =1;
while (n >= t )
t *= 10;
t /=10;
while (t >0) {
d = n/t;
n = n%t;
t /= 10;
if ( turn ) newnum = 10* newnum + d ;
turn = ( turn + 1) % 2;
}
return newnum ;
}
int main () {
printf ( " % d " , gate (14362));
return 0;
}
The value printed by the given C program is . (Answer in integer)
Q 20. Consider the following program fragment for reversing the digits in a given integer to obtain a new 2004
integer. Let n = d1 d2 . . . dm
int n , rev ;
rev = 0;
while ( n > 0) {
rev = rev * 10 + n %10;
n = n /10;
}

The loop invariant condition at the end of the ith iteration is:
A. n = d1 d2 . . . dm−i and rev = dm dm−1 . . . dm−i+1
B. n = dm−i+1 . . . dm−1 dm or rev = dm−i . . . d2 d1
C. n ̸= rev
D. n = d1 d2 . . . dm or rev = dm . . . d2 d1
Q 21. Consider the following pseudo code, where x and y are positive integers. 2015Set1
begin
q := 0
r := x
while r ≥ y do
begin
r := r - y
q := q + 1
end
end
The post condition that needs to be satisfied after the program terminates is

6
 C Programming and Data Structures Programming in C Page 7 of 107

A. {r = qx + y ∧ r < y} C. {y = qx + r ∧ 0 < r < y}

B. {x = qy + r ∧ r < y} D. {q + 1 < r − y ∧ y > 0}

Q 22. The following function computes X Y for positive integers X and Y . 2016Set2
int exp ( int X , int Y ) {
int res =1 , a = X , b = Y ;

while ( b != 0) {
if ( b % 2 == 0) { a = a * a ; b = b /2; }
else { res = res * a ; b = b - 1; }
}
return res ;
}

Which one of the following conditions is TRUE before every iteration of the loop?
A. X Y = ab B. (res ∗ a)Y = (res ∗ X)b C. X Y = res ∗ ab D. X Y = (res ∗ a)b

Q 23. Consider the C program fragment below which is meant to divide x by y using repeated subtractions. 2017Set2
The variables x, y, q and r are all unsigned int.
while ( r >= y ) {
r =r - y ;
q = q +1;
}

Which of the following conditions on the variables x, y, q and r before the execution of the fragment
will ensure that the loop terminated in a state satisfying the condition x==(y*q + r)?

A. (q==r) && (r==0) C. (q==0) && (r==x) && (y>0)

B. (x>0) && (r==x) && (y>0) D. (q==0) && (y>0)

Q 24. The attributes of three arithmetic operators in some programming language are given below. 2016Set1

OPERATOR PRECEDENCE ASSOCIATIVITY ARITY

+ High Left Binary
− Medium Right Binary
∗ Low Left Binary

The value of the expression 2 − 5 + 1 − 7 ∗ 3 in this language is .

1.2 Arrays

Q 25. Consider the C program given below. What does it print? 2008IT
# include < stdio .h >
int main ()
{
int i , j ;
int a [8] = {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8};
for ( i = 0; i < 3; i ++) {
a [ i ] = a [ i ] + 1;
i ++;
}
i - -;

7
 C Programming and Data Structures Programming in C Page 8 of 107

for ( j = 7; j > 4; j - -) {
int i = j /2;
a [ i ] = a [ i ] - 1;
}
printf ( " %d , % d " , i , a [ i ]);
}

A. 2, 3 B. 2, 4 C. 3, 2 D. 3, 3

Q 26. Consider the C program given below : 2007IT

# include < stdio .h >
int main ()
{
int sum = 0 , maxsum = 0 , i , n = 6;
int a [] = {2 , -2 , -1 , 3 , 4 , 2};
for ( i = 0; i < n ; i ++)
{
if ( i == 0 || a [ i ] < 0 || a [ i ] < a [ i - 1])
{
if ( sum > maxsum )
maxsum = sum ;
sum = ( a [ i ] > 0) ? a [ i ] : 0;
}
else
sum += a [ i ];
}
if ( sum > maxsum )
maxsum = sum ;
printf ( " % d \ n " , maxsum );
}

What is the value printed out when this program is executed?

A. 9 B. 8 C. 7 D. 6
Q 27. The procedure given below is required to find and replace certain characters inside an input character 2013
string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective
replacement characters are supplied in array newc. Array A has a fixed length of five characters, while
arrays oldc and newc contain three characters each. However, the procedure is flawed.
void find_and_replace ( char *A , char * oldc , char * newc ) {
for ( int i =0; i <5; i ++)
for ( int j =0; j <3; j ++)
if ( A [ i ] == oldc [ j ])
A [ i ] = newc [ j ];
}

The procedure is tested with the following four test cases.

1. oldc=“abc”, newc=“dab”
2. oldc=“cde”, newc=“bcd”
3. oldc=“bca”, newc=“cda”
4. oldc=“abc”, newc=“bac”
(i) The tester now tests the program on all input strings of length five consisting of characters ‘a’, ‘b’,
‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with the four test cases
given above, how many test cases will be able to capture the flaw?
A. Only one B. Only two C. Only three D. All four

8
 C Programming and Data Structures Programming in C Page 9 of 107

(ii) If array A is made to hold the string “abcde”, which of the above four test cases will be successful
in exposing the flaw in this procedure?
A. None B. 2 only C. 3 and 4 only D. 4 only

Q 28. Consider the following snippet of a C program. Assume that swap (&x,&y) exchanges the content of x 2017Set2
and y.
int main ()
{
int array [] = {3 , 5 , 1 , 4 , 6 , 2};
int done =0;
int i ;
while ( done ==0)
{
done =1;
for ( i =0; i <=4; i ++)
{
if ( array [ i ] < array [ i +1])
{
swap (& array [ i ] , & array [ i +1]);
done =0;
}
}
for ( i =5; i >=1; i - -)
{
if ( array [ i ] > array [i -1])
{
swap (& array [ i ] , & array [i -1]);
done =0;
}
}
}
printf ( " % d " , array [3]);
}

The output of the program is .

Q 29. The following C function takes two ASCII strings and determines whether one is an anagram of the 2005IT
other. An anagram of a string s is a string obtained by permuting the letters in s.
int anagram ( char *a , char * b ) {
int count [128] , j ;
for ( j = 0; j < 128; j ++) count [ j ] = 0;
j = 0;
while ( a [ j ] && b [ j ]) {
A;
B;
}
for ( j = 0; j < 128; j ++) if ( count [ j ]) return 0;
return 1;
}

Choose the correct alternative for statements A and B

A. A: count[a[j]]++ and B: count[b[j]]-- C. A: count[a[j++]]++ and B: count[b[j]]--

B. A: count[a[j]]++ and B: count[b[j]]++ D. A: count[a[j]]++ and B: count[b[j++]]--

9
 C Programming and Data Structures Programming in C Page 10 of 107

Q 30. Consider the function computes(X) whose pseudocode is given below: 2024DA
computes(X)
S [1] ← 1
for i←2 to length ( X )
S[i] ← 1
if X [i -1] ≤ X [ i ]
S [ i ] ← S [ i ]+ S [i -1]
end if
end for
return S

Which ONE of the following values is returned by the function computes(X) for X = [6, 3, 5, 4, 10]?

A. [1, 1, 2, 3, 4] C. [1, 1, 2, 1, 2]
B. [1, 1, 2, 3, 3] D. [1, 1, 2, 1, 5]

Q 31. A set X can be represented by an array x[n] as follows: 2006

(
1 if i ∈ X
x [i] =
0 otherwise
Consider the following algorithm in which x, y and z are Boolean arrays of size n:
algorithm zzz ( x [] , y [] , z []) {
int i ;

for ( i =0; i < n ; ++ i )

z [ i ] = ( x [ i ] ∧ ∼y [ i ]) ∨ (∼x [ i ] ∧ y [ i ]);
}

The set Z computed by the algorithm is:

A. (X ∪ Y ) B. (X ∩ Y ) C. (X − Y ) ∩ (Y − X) D. (X − Y ) ∪ (Y − X)

1.3 Multi-dimensional Array

Q 32. Consider the following C program which is supposed to compute the transpose of a given 4 × 4 matrix 2004IT
M . Note that, there is an X in the program which indicates some missing statements. Choose the
correct option to replace X in the program.
# include < stdio .h >
# define ROW 4
# define COL 4
int M [ ROW ][ COL ] = {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 ,
14 , 15 , 16};
main ()
{
int i , j , t ;
for ( i = 0; i < 4; ++ i )
{
X
}
for ( i = 0; i < 4; ++ i )
for ( j = 0; j < 4; ++ j )
printf ( " % d " , M [ i ][ j ]);
}

10
 C Programming and Data Structures Programming in C Page 11 of 107

A. for ( j = 0; j < 4; ++ j ){ C. for ( j = i ; j < 4; ++ j ){

t = M [ i ][ j ]; t = M [ i ][ j ];
M [ i ][ j ] = M [ j ][ i ]; M [ i ][ j ] = M [ j ][ i ];
M [ j ][ i ] = t ; M [ j ][ i ] = t ;
} }

B. for ( j = 0; j < 4; ++ j ){ D. for ( j = i ; j < 4; ++ j ){

M [ i ][ j ] = t ; M [ i ][ j ] = t ;
t = M [ j ][ i ]; t = M [ j ][ i ];
M [ j ][ i ] = M [ i ][ j ]; M [ j ][ i ] = M [ i ][ j ];
} }

Q 33. Let A be the square matrix of size n × n. Consider the following pseudocode. What is the expected 2014Set3
output?
C =100;
for i =1 to n do
for j =1 to n do
{
Temp = A [ i ][ j ]+ C ;
A [ i ][ j ] = A [ j ][ i ];
A [ j ][ i ] = Temp - C ;
}
for i =1 to n do
for j =1 to n do
output ( A [ i ][ j ]);

A. The matrix A itself

B. Transpose of the matrix A
C. Adding 100 to the upper diagonal elements and subtracting 100 from lower diagonal elements of A
D. None of the above
Q 34. Consider the following two C code segments. Y and X are one and two dimensional arrays of size n and 2015Set3
n × n respectively, where 2 ≤ n ≤ 10. Assume that in both code segments, elements of Y are initialized
to 0 and each element X[i][j] of array X is initialized to i + j. Further assume that when stored in main
memory all elements of X are in same main memory page frame.
Code segment 1:
// initialize elements of Y to 0
// initialize elements of X [ i ][ j ] of X to i + j
for ( i =0; i < n ; i ++)
Y [ i ] += X [0][ i ];

Code segment 2:
// initialize elements of Y to 0
// initialize elements of X [ i ][ j ] of X to i + j
for ( i =0; i < n ; i ++)
Y [ i ] += X [ i ][0];

Which of the following statements is/are correct?

S1: Final contents of array Y will be same in both code segments
S2: Elements of array X accessed inside the for loop shown in code segment 1 are contiguous in main
memory
S3: Elements of array X accessed inside the for loop shown in code segment 2 are contiguous in main
memory

11
 C Programming and Data Structures Programming in C Page 12 of 107

A. Only S2 is correct C. Only S1 and S2 are correct

B. Only S3 is correct D. Only S1 and S3 are correct

Q 35. What is printed by the following ANSI C program? 2022

# include < stdio .h >
int main ( int argc , char * argv [])
{
int a [3][3][3] =
{{1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9} ,
{10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18} ,
{19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27}};

int i = 0 , j = 0 , k = 0;
for ( i = 0; i < 3; i ++ ){
for ( k = 0; k < 3; k ++ )
printf ( " % d " , a [ i ][ j ][ k ]);
printf ( " \ n " );
}
return 0;
}

A. 1 2 3 B. 1 4 7 C. 1 2 3 D. 1 2 3
10 11 12 10 13 16 456 13 14 15
19 20 21 19 22 25 789 25 26 27

1.4 Storage Classes

Q 36. The value of j at the end of the execution of the following C program 2000
int incr ( int i )
{
static int count = 0;
count = count + i ;
return ( count );
}
main (){
int i , j ;
for ( i = 0; i <= 4; i ++)
j = incr ( i );
}

is:
A. 10 B. 4 C. 6 D. 7

Q 37. What is the output of the following program? 2004IT

# include < stdio .h >
int funcf ( int x );
int funcg ( int y );
main ()
{
int x = 5 , y = 10 , count ;
for ( count = 1; count <= 2; ++ count ) {
y += funcf ( x ) + funcg ( x );

12
 C Programming and Data Structures Programming in C Page 13 of 107

printf ( " % d " , y );

}
}
funcf ( int x ) {
int y ;
y = funcg ( x );
return ( y );
}
funcg ( int x ) {
static int y = 10;
y += 1;
return ( y + x );
}

A. 43 80 B. 42 74 C. 33 37 D. 32 32

Q 38. Consider the following C code segment. 2012

int a , b , c = 0;
void prtFun ( void );
main ()
{
static int a = 1; /* Line 1 */
prtFun ();
a += 1;
prtFun ();
printf ( " \ n % d % d " , a , b );
}

void prtFun ( void )

{
static int a = 2; /* Line 2 */
int b = 1;
a += ++ b ;
printf ( " \ n % d % d " , a , b );
}

(i) What output will be generated by the given code segment?

A. 3 1 B. 4 2 C. 4 2 D. 3 1
41 61 62 52
42 61 20 52

(ii) What output will be generated by the given code segment if:
Line 1 is replaced by auto int a=1;
Line 2 is replaced by register int a=2;

A. 3 1 B. 4 2 C. 4 2 D. 4 2
41 61 62 42
42 61 20 20

Q 39. Consider the following C program: 2015Set3

# include < stdio .h >
int f1 ( void );
int f2 ( void );
int f3 ( void );

13
 C Programming and Data Structures Programming in C Page 14 of 107

int x =10;
int main ()
{
int x =1;
x += f1 () + f2 () + f3 () + f2 ();
printf ( " % d " , x );
return 0;
}
int f1 () { int x = 25; x ++; return x ;}
int f2 () { static int x = 50; x ++; return x ;}
int f3 () { x *= 10; return x ;}

The output of the program is .

Q 40. What will be the output of the following C program? 2016Set1

void count ( int n ) {
static int d =1;

printf ( " % d " ,n );

printf ( " % d " ,d );
d ++;
if (n >1) count (n -1);
printf ( " % d " ,d );
}

void main (){

count (3);
}

A. 3 1 2 2 1 3 4 4 4 B. 3 1 2 1 1 1 2 2 2 C. 3 1 2 2 1 3 4 D. 3 1 2 1 1 1 2

Q 41. The output of executing the following C program is . 2017Set1

# include < stdio .h >

int total ( int v ) {

static int count = 0;
while ( v ) {
count += v &1;
v > >= 1;
}
return count ;
}

void main () {
static int x =0;
int i =5;
for (; i >0; i - -) {
x = x + total ( i );
}
printf ( " % d \ n " , x );
}

Q 42. Consider the following C program: 2019

# include < stdio .h >
int r () {

14
 C Programming and Data Structures Programming in C Page 15 of 107

static int num =7;

return num - -;
}
int main () {
for ( r (); r (); r ())
printf ( " % d " ,r ());
return 0;
}

Which one of the following values will be displayed on execution of the program?
A. 41 B. 52 C. 63 D. 630
Q 43. The integer value printed by the ANSI-C program given below is . 2023
# include < stdio .h >
int funcp (){
static int x = 1;
x ++;
return x ;
}
int main (){
int x , y ;
x = funcp ();
y = funcp ()+ x ;
printf ( " % d \ n " , ( x + y ));
return 0;
}

1.5 Pointers and Memory Allocation

Q 44. Consider the C program shown below: 2003

# include < stdio .h >
# define print ( x ) printf ( " % d " , x )

int x ;
void Q ( int z )
{
z += x ;
print ( z );
}
void P ( int * y )
{
int x = * y + 2;
Q ( x );
* y = x - 1;
print ( x );
}
main ( void ) {
x = 5;
P (& x );
print ( x );
}

The output of this program is:

A. 12 7 6 B. 22 12 11 C. 14 6 6 D. 7 6 6

15
 C Programming and Data Structures Programming in C Page 16 of 107

Q 45. What does the following fragment of C program print? 2011

char c [] = " GATE2011 " ;
char * p = c ;
printf ( " % s " , p + p [3] - p [1]);

A. GATE2011 B. E2011 C. 2011 D. 011

Q 46. Consider the following C program segment: 2015Set3
# include < stdio .h >
int main ()
{
char s1 [7] = " 1234 " , * p ;
p = s1 + 2;
* p = ‘0 ’;
printf ("% s " , s1 );
}

What will be printed by the program?

A. 12 B. 120400 C. 1204 D. 1034
Q 47. Consider the following C program. 2017Set2
# include < stdio .h >
# include < string .h >
int main () {
char * c = " GATECSIT2017 " ;
char * p = c ;
printf ( " % d " , ( int ) strlen ( c +2[ p ] -6[ p ] -1));
return 0;
}

The output of the program is .

Q 48. Consider the following C program: 2019
# include < stdio .h >
int main () {
int arr []={1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 0 , 1 , 2 , 5} , * ip = arr +4;
printf ( " % d \ n " , ip [1]);
return 0;
}

The number that will be displayed on execution of the program is .

Q 49. Consider the following C program segment: 2004

char p [20]; int i ;
char * s = " string " ;
int length = strlen ( s );
for ( i = 0; i < length ; i ++)
p [ i ] = s [ length - i ];
printf ( " % s " , p );

The output of the program is:

A. gnirts B. string C. gnirt D. no output is printed

Q 50. What is the output printed by the following C code? 2008IT

16
 C Programming and Data Structures Programming in C Page 17 of 107

# include < stdio .h >

int main ()
{
char a [6] = " world " ;
int i , j ;
for ( i = 0 , j = 5; i < j ; a [ i ++] = a [j - -]);
printf ( " % s \ n " , a );
}

A. dlrow B. Null String C. dlrld D. worow

Q 51. Consider the following function written in the C programming language: 2015Set2
void foo ( char * a )
{
if (* a && * a != ‘ ’)
{
foo ( a +1);
putchar (* a );
}
}

The output of the above function on input “ABCD EFGH” is

A. ABCD EFGH B. ABCD C. HGFE DCBA D. DCBA
Q 52. Consider the following C function definition: 2024Set2
int fX ( char * a ){
char * b = a ;
while (* b )
b ++;
return b - a ;
}

Which of the following statements is/are TRUE?

A. The function call fX(“abcd”) will always return a value
B. Assuming a character array c is declared as char c[] = “abcd” in main(), the function call fX(c) will
always return a value
C. The code of the function will not compile
D. Assuming a character pointer c is declared as char *c = “abcd” in main(), the function call fX(c) will
always return a value

Q 53. Consider the following program in C language: 2014Set1

# include < stdio .h >

main ()
{
int i ;
int * pi = & i ;

scanf ( " % d " , pi );

printf ( " % d \ n " , i +5);
}

Which one of the following statements is TRUE?

A. Compilation fails.

17
 C Programming and Data Structures Programming in C Page 18 of 107

B. Execution results in a run-time error.

C. On execution, the value printed is 5 more than the address of variable i.
D. On execution, the value printed is 5 more than the integer value entered.
Q 54. What does the following program print? 2010
# include < stdio .h >

void f ( int *p , int * q ) {

p=q;
* p =2;
}

int i =0 , j =1;

int main () {
f (& i , & j );
printf ( " % d % d \ n " , i , j );
return 0;
}

A. 2 2 B. 2 1 C. 0 1 D. 0 2
Q 55. The value printed by the following program is . 2016Set2
void f ( int * p , int m ) {
m = m + 5;
*p = *p + m;
return ;
}
void main () {
int i =5 , j =10;
f (& i , j );
printf ( " % d " , i + j );
}

Q 56. # include < stdio .h > 2025Set1

void foo ( int *p , int x ){
*p=x;
}
int main (){
int * z ;
int a = 20 , b = 25;
z = &a;
foo (z , b );
printf ( " % d " ,a );
return 0;
}

The output of the given C program is . (Answer in integer)

Q 57. Consider the following function implemented in C: 2017Set2

void printxy ( int x , int y ) {
int * ptr ;
x =0;
ptr =& x ;
y =* ptr ;

18
 C Programming and Data Structures Programming in C Page 19 of 107

* ptr =1;
printf ( " %d , % d " , x , y );
}

The output of invoking printxy(1,1) is

A. 0,0 B. 0,1 C. 1,0 D. 1,1
Q 58. What is printed by the following C program? 2008
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 ));

A. 18 B. 19 C. 21 D. 22
Q 59. Consider the C program below. What does it print? 2008IT
# include < stdio .h >
# define swapl (a , b ) tmp = a ; a = b ; b = tmp
void swap2 ( int a , int b ){
int tmp ;
tmp = a ; a = b ; b = tmp ;
}
void swap3 ( int *a , int * b ){
int tmp ;
tmp = * a ; * a = * b ; * b = tmp ;
}
int main (){
int num1 = 5 , num2 = 4 , tmp ;
if ( num1 < num2 ) { swap1 ( num1 , num2 );}
if ( num1 < num2 ) { swap2 ( num1 + 1 , num2 );}
if ( num1 > = num2 ) { swap3 (& num1 , & num2 );}
printf ( " %d , % d " , num1 , num2 );
}

A. 5, 5 B. 5, 4 C. 4, 5 D. 4, 4

Q 60. The output of the following C program is . 2015Set1

void f1 ( int a , int b ) {
int c;
c = a; a = b;
b = c;
}
void f2 ( int *a , int * b ) {
int c;

19
 C Programming and Data Structures Programming in C Page 20 of 107

c = *a; *a = *b; *b = c;
}
int main () {
int a = 4 , b = 5 , c = 6;
f1 (a , b );
f2 (& b , & c );
printf ( " % d " , c - a - b );
}

Q 61. Which one of the choices given below would be printed when the following program is executed? 2006IT
# include < stdio .h >
void swap ( int *x , int * y ){
static int * temp ;
temp = x ;
x = y;
y = temp ;
}
void printab (){
static int i , a = -3 , b = -6;
i = 0;
while ( i <= 4)
{
if (( i ++)%2 == 1) continue ;
a = a + i;
b = b + i;
}
swap (& a , & b );
printf ( " a =% d , b =% d \ n " , a , b );
}
void main (){
printab ();
printab ();
}

A. a = 0, b = 3 C. a = 3, b = 6
a = 0, b = 3 a = 3, b = 6
B. a = 3, b = 0 D. a = 6, b = 3
a = 12, b = 9 a = 15, b = 12

Q 62. Consider the following C program. 2016Set1

# include < stdio .h >
void mystery ( int * ptra , int * ptrb ) {
int * temp ;
temp = ptrb ;
ptrb = ptra ;
ptra = temp ;
}
int main () {
int a = 2016 , b = 0 , c = 4 , d = 42;
mystery (& a , & b );
if ( a < c )
mystery (& c , & a );
mystery (& a , & d );
printf ( " % d \ n " , a );

20
 C Programming and Data Structures Programming in C Page 21 of 107

The output of the program is .

Q 63. Consider the following C program: 2019
# include < stdio .h >
int main (){
int a [] = {2 , 4 , 6 , 8 , 10};
int i , sum =0 , * b = a +4;
for ( i =0; i <5; i ++)
sum = sum +(* b - i ) -*( b - i );
printf ( " % d \ n " , sum );
return 0;
}

The output of the above C program is .

Q 64. Consider the following C program: 2025Set2

# include < stdio .h >
int main (){
int a ;
int arr [5] = {30 ,50 ,10};
int * ptr ;
ptr = & arr [0] + 1;
a = * ptr ;
(* ptr )++;
ptr ++;
printf ( " % d " , a + (* ptr ) + arr [1]);
return 0;
}

The output of the above program is . (Answer in integer)

Q 65. What is printed by the following ANSI C program? 2022

# include < stdio .h >
int main ( int argc , char * argv []){
int x = 1 , z [2] = {10 , 11};
int * p = NULL ;
p = &x;
* p = 10;
p = & z [1];
*(& z [0] + 1) += 3;
printf ( " %d , %d , % d \ n " , x , z [0] , z [1]);
return 0;
}

A. 1, 10, 11 B. 1, 10, 14 C. 10, 14, 11 D. 10, 10, 14

Q 66. Consider the following ANSI C program. 2021Set2

# include < stdio .h >
int main ()
{
int arr [4][5];
int i , j ;
for ( i =0; i <4; i ++)
{

21
 C Programming and Data Structures Programming in C Page 22 of 107

for ( j =0; j <5; j ++)

{
arr [ i ][ j ] = 10 * i + j ;
}
}
printf ( " % d " , *( arr [1]+9));
return 0;
}

What is the output of the above program?

A. 14 B. 20 C. 24 D. 30
Q 67. What is the output of the following C program? 2024Set2
# include < stdio .h >
int main () {
double a [2]={20.0 , 25.0} , *p , * q ;
p = a;
q = p + 1;
printf ( " %d ,% d " , ( int )( q - p ) , ( int )(* q - * p ));
return 0;}

A. 4,8 B. 1,5 C. 8,5 D. 1,8

Q 68. Consider the following C program. 2018
# include < stdio .h >
struct Ournode {
char x , y , z ;
};
int main () {
struct Ournode p ={ ‘1 ’ , ‘0 ’ , ‘a ’ +2};
struct Ournode * q =& p ;
printf ("% c , % c " , *(( char *) q +1) , *(( char *) q +2));
return 0;
}

The output of this program is:

A. 0, c B. 0, a+2 C. ‘0’, ‘a+2’ D. ‘0’, ‘c’

Q 69. Consider the following C program 2015Set3

# include < stdio .h >
int main () {
static int a [] = {10 , 20 , 30 , 40 , 50};
static int * p [] = {a , a +3 , a +4 , a +1 , a +2};
int ** ptr = p ;
ptr ++;
printf ( " % d % d " , ptr -p , ** ptr );
}

The output of the program is .

Q 70. Consider the following C program: 2025Set2

# include < stdio .h >
void stringcopy ( char * , char *);
int main (){
char a [30] = " @ # Hello World ! " ;

22
 C Programming and Data Structures Programming in C Page 23 of 107

stringcopy (a , a + 2);
printf ( " % s \ n " , a );
return 0;
}
void stringcopy ( char *s , char * t ) {
while (* t )
* s ++ = * t ++;
}

Which ONE of the following will be the output of the program?

A. {@#Hello World!} C. ello World!

B. Hello World! D. Hello World!d!

Q 71. Consider the following C program: 2018

# include < stdio .h >

void fun1 ( char * s1 , char * s2 ){

char * temp ;
temp = s1 ;
s1 = s2 ;
s2 = temp ;
}
void fun2 ( char ** s1 , char ** s2 ){
char * temp ;
temp = * s1 ;
* s1 = * s2 ;
* s2 = temp ;
}
int main (){
char * str1 = " Hi " , * str2 = " Bye " ;
fun1 ( str1 , str2 ); printf ( " % s % s " , str1 , str2 );
fun2 (& str1 , & str2 ); printf ( " % s % s " , str1 , str2 );
return 0;
}

The output of the program above is:

A. Hi Bye Bye Hi C. Bye Hi Hi Bye

B. Hi Bye Hi Bye D. Bye Hi Bye Hi

Q 72. A C program is given below: 2008IT

# include < stdio .h >
int main ()
{
int i , j ;
char a [2][3] = {{ ‘ a ’ , ‘b ’ , ‘c ’} , { ‘ d ’ , ‘e ’ , ‘f ’ }};
char b [3][2];
char * p = * b ;
for ( i = 0; i < 2; i ++) {
for ( j = 0; j < 3; j ++) {
*( p + 2* j + i ) = a [ i ][ j ];
}
}
}

23
 C Programming and Data Structures Programming in C Page 24 of 107

What should be the contents of the array b at the end of the program?

A. a b B. a d C. a c D. a e
cd be eb dc
ef cf df bf

Q 73. Which one of the choices given below would be printed when the following program is executed? 2006IT
# include < stdio .h >
int a1 [] = {6 , 7 , 8 , 18 , 34 , 67};
int a2 [] = {23 , 56 , 28 , 29};
int a3 [] = { -12 , 27 , -31};
int * x [] = { a1 , a2 , a3 };
void print ( int * a [])
{
printf ( " %d , " , a [0][2]);
printf ( " %d , " , * a [2]);
printf ( " %d , " , *++ a [0]);
printf ( " %d , " , *(++ a )[0]);
printf ( " % d \ n " , a [ -1][+1]);
}
void main ()
{
print ( x );
}

A. 8, -12, 7, 23, 8 B. 8, 8, 7, 23, 7 C. -12, -12, 27, -31, 23 D. -12, -12, 27, -31, 56

Q 74. Which one of the choices given below would be printed when the following program is executed? 2006IT
# include < stdio .h >
struct test {
int i ;
char * c ;
} st [] = {5 , " become " , 4 , " better " , 6 , " jungle " , 8 , " ancestor " ,
7 , " brother " };

void main ()
{
struct test * p = st ;
p += 1;
++ p -> c ;
printf ( " %s , " , p ++ -> c );
printf ( " %c , " , *++ p -> c );
printf ( " %d , " , p [0]. i );
printf ( " % s \ n " , p -> c );
}

A. jungle, n, 8, nclastor C. cetter, k, 6, jungle

B. etter, u, 6, ungle D. etter, u, 8, ncestor

Q 75. Consider the following C program. 2020

# include < stdio .h >
int main () {
int a [4] [5] = {{1 , 2 , 3 , 4 , 5} ,
{6 , 7 , 8 , 9 , 10} ,

24
 C Programming and Data Structures Programming in C Page 25 of 107

{11 , 12 , 13 , 14 , 15} ,
{16 , 17 , 18 , 19 , 20}};
printf ( " % d \ n " , *(*( a +** a +2)+3));
return (0);
}

The output of the program is .

Q 76. What is the output of the following C code? Assume that the address of x is 2000 (in decimal) and an 2015Set1
integer requires four bytes of memory.
int main () {
unsigned int x [4][3] =
{{1 , 2 , 3} , {4 , 5 , 6} , {7 , 8 , 9} , {10 , 11 , 12}};

printf ( " %u , %u , % u " , x + 3 , *( x + 3) , *( x + 2) + 3);

}

A. 2036, 2036, 2036 B. 2012, 4, 2204 C. 2036, 10, 10 D. 2012, 4, 6

Q 77. Consider the following C program: 2004IT

# include < stdio .h >
typedef struct {
char * a ;
char * b ;
} t;
void f1 ( t s );
void f2 ( t * p );
main ()
{
static t s = { " A " , " B " };
printf ( " % s % s \ n " , s .a , s . b );
f1 ( s );
printf ( " % s % s \ n " , s .a , s . b );
f2 (& s );
}
void f1 ( t s )
{
s.a = "U";
s.b = "V";
printf ( " % s % s \ n " , s .a , s . b );
return ;
}
void f2 ( t * p )
{
p -> a = " V " ;
p -> b = " W " ;
printf ( " % s % s \ n " , p -> a , p -> b );
return ;
}

What is the output generated by the program?

A. A B B. A B C. A B D. A B
U V U V U V U V
V W A B U V V W
V W V W V W U V

25
 C Programming and Data Structures Programming in C Page 26 of 107

Q 78. Consider the following C program. 2016Set1

void f ( int , short );
void main ()
{
int i = 100;
short s = 12;
short * p = & s ;
____________ ; // call to f ()
}

Which one of the following expressions , when placed in the blank above, will NOT result in a type
checking error?
A. f(s, *s) B. i = f(i,s) C. f(i, *s) D. f(i, *p)

Q 79. Consider the following C function: 2004

void swap ( int a , int b ) {
int temp ;
temp = a ;
a = b;
b = temp ;
}

In order to exchange the values of two variables x and y

A. call swap(x,y)
B. call swap(&x,&y)
C. swap(x,y) cannot be used as it does not return any value
D. swap(x,y) cannot be used as the parameters are passed by value

Q 80. What is printed by the print statements in the program P1 assuming call by reference parameter 2001
passing?
Program P1 ()
{
x = 10;
y = 3;
func1 (y ,x , x );
print x ;
print y ;
}

func1 (x ,y , z )
{
y = y + 4;
z = x + y + z
}

A. 10, 3 B. 31, 3 C. 27, 7 D. None of the above

Q 81. The most appropriate matching for the following pairs 2000

X : m = malloc(5); m = NULL; 1 : using dangling pointers

Y : free(n); n → value = 5; 2: using uninitialized pointers
Z : char *p , *p = ‘a’ ; 3: lost memory

A. X-1 Y-3 Z-2 B. X-2 Y-1 Z-3 C. X-3 Y-2 Z-1 D. X-3 Y-1 Z-2

26
 C Programming and Data Structures Programming in C Page 27 of 107

Q 82. Match the following: 2017Set2

P. static char var ; i. Sequence of memory locations to store addresses

Q. m = malloc(10); m =NULL ; ii. A variable located in data section of memory
R. char *ptr[10] ; iii. Request to allocate a CPU register to store data
S. register int varl; iv. A lost memory which cannot be freed
A. P-ii; Q-iv; R-i; S-iii C. P-ii; Q-iv; R-iii; S-i
B. P-ii; Q-i; R-iv; S-iii D. P-iii; Q-iv; R-i; S-ii

Q 83. Consider the following three C functions: 2001

P1 P2 P3
int * g ( void ) int * g ( void ) int * g ( void )
{ { {
int x = 10; int * px ; int * px ;
return (& x ); * px = 10; px = ( int *) malloc ( sizeof ( int ));
} return px ; * px = 10;
} return px ;
}

Which of the above three functions are likely to cause problems with pointers?
A. Only P3 B. Only P1 and P3 C. Only P1 and P2 D. P1, P2 and P3

Q 84. Consider the following C code: 2017Set1

# include < stdio .h >
int * assignval ( int *x , int val ) {
* x = val ;
return x ;
}

void main () {
int * x = malloc ( sizeof ( int ));
if ( NULL == x ) return ;
x = assignval (x ,0);
if ( x ) {
x = ( int *) malloc ( sizeof ( int ));
if ( NULL == x ) return ;
x = assignval (x ,10);
}
printf ( " % d \ n " , * x );
free ( x );
}

The code suffers from which one of the following problems:

A. compiler error as the return of malloc is not typecast appropriately.
B. compiler error because the comparison should be made as x == NULL and not as shown.
C. compiles successfully but execution may result in dangling pointer.
D. compiles successfully but execution may result in memory leak.

1.6 Scoping

Q 85. What will be the output of the following pseudo-code when parameters are passed by reference and 2016Set1
dynamic scoping is assumed?

27
 C Programming and Data Structures Programming in C Page 28 of 107

a = 3;
void n ( x ) { x = x * a ; print ( x ); }
void m ( y ) { a = 1 ; a = y - a ; n ( a ); print ( a ); }
void main () { m ( a ); }

A. 6, 2 B. 4, 2 C. 6, 6 D. 4, 4
Q 86. The following program fragment is written in a programming language that allows global variables and 2003
does not allow nested declarations of functions.
global int i =100 , j =5;
void P ( x ) {
int i =10;
print ( x +10);
i =200;
j =20;
print ( x );
}
main () {
P ( i + j );
}

(i) If the programming language uses static scoping and call by need parameter passing mechanism,
the values printed by the above program are:
A. 115, 220 B. 25, 220 C. 25, 15 D. 115, 105
(ii) If the programming language uses dynamic scoping and call by name parameter passing mechanism,
the values printed by the above program are
A. 115, 220 B. 25, 220 C. 25, 15 D. 115, 105

1.7 More Questions

Q 87. Consider the following program operating on four variables u, v, x, y, and two constants X and Y . TIFR’10
x , y , u , v := X , Y , Y , X ;
while ( x ̸= y )
do
if ( x > y ) then x , v := x - y , v + u ;
else if ( y > x ) then y , u := y - x , u + v ;
od ;
print (( x + y ) / 2); print (( u + v ) / 2);

Given X > 0 ∧ Y > 0, pick the true statement out of the following:
A. The program prints gcd(X, Y ) and the first prime larger than both X and Y .
B. The program prints gcd(X, Y ) followed by lcm(X, Y ).
1
C. The program prints gcd(X, Y ) followed by 2 × lcm(X, Y )
1 1
D. The program prints 2 × gcd(X, Y ) followed by 2 × lcm(X, Y ).
E. The program does none of the above.

Q 88. Consider the following code. TIFR’14

def brian ( n ):
count = 0

while ( n != 0)
n = n & (n -1)

28
 C Programming and Data Structures Programming in C Page 29 of 107

count = count + 1

return count
Here n is meant to be an unsigned integer. The operator & considers its arguments in binary and
computes their bit wise AND. For example, 22 & 15 gives 6, because the binary (say 8-bit) representation
of 22 is 00010110 and the binary representation of 15 is 00001111, and the bit-wise AND of these binary
strings is 00000110, which is the binary representation of 6.
What does the function brian return?
A. The highest power of 2 dividing n, but zero if n is zero.
B. The number obtained by complementing the binary representation of n.
C. The number of ones in the binary representation of n.
D. The code might go into an infinite loop for some n.
E. The result depends on the number of bits used to store unsigned integers.
Q 89. Consider the following C program. ISI’15
# include < stdio .h >
main () {
int arr [] = {1 , 1 , 2 , 4 , 8 , 16 , 32 , 64};
int i , j , val , t = 16;
unsigned char c ;
for ( i = 0; i < 256; i ++) {
c = i;
val = 0;
for ( j = 0; j < 8; j ++)
val = val + (( c >> j ) & 0 x1 )* arr [ j ];
if ( val == t )
printf ( " % d \ n " , i );
}
}
(i) Trace the execution of the code inside the for loop indexed by i when i = 35.
(ii) What will be the output of the program? Justify your answer.
(iii) What will be the output of the program if t = 130 (instead of 16)? Justify.

Q 90. A computer program computes a function f {0, 1}∗ × {0, 1}∗ → {0, 1}∗ . Suppose f (a, b) has length | b |2 , TIFR’16
where | a | and | b | are the lengths of a and b. Suppose, using this program, the following computation
is performed.
x = " 01 "
for i =1 , ... , n do
x = f ( " 01 " , x )
Suppose at the end, the length of the string x is t. Which of the following is TRUE (assume n ≥ 10)?
n n
A. t ≤ 2n B. n < t ≤ n2 C. n2 < t ≤ nlog2 n D. nlog2 n < t ≤ 2(2 )
E. 2(2 )
<t
Q 91. Consider the following pseudocode fragment, where y is an integer that has been initialized. TIFR’17
int i =1
int j =1
while (i <10):
j=j*i
i = i +1
if ( i == y ):
break
end if
end while

29
 C Programming and Data Structures Programming in C Page 30 of 107

Consider the following statements:

(i) (i == 10) or (i == y)
(ii) if y > 10, then i == 10
(iii) if j = 6, then y == 4

Which of the above statements is/are TRUE at the end of the while loop? Choose from the following
options.
A. (i) only B. (iii) only C. (ii) and (iii) only D. (i), (ii), and (iii) E. None of the above

Q 92. Consider the two C programs given below. ISI’20

# include < stdio .h >
int main () {
int n =2 , * ptr =& n ; n *=3;
printf ( " % d " , (* ptr ** ptr )*(* ptr ** ptr ));
}

# include < stdio .h >

int main () {
int n =2 , * ptr =& n ; n *=3;
printf ( " % d " , * ptr ** ptr ** ptr ** ptr );
}

Given C codes (I) and (II) above, decide which of the following statements is TRUE.
A. Output of (I) is 36 and (II) is 216.
B. Output of (I) is 216 and (II) is 1296.
C. Output of (I) is 1296 and (II) is 216.
D. Output of both (I) and (II) is 1296.
E. None of the above
Q 93. What does the following function compute for x ̸= 0? ISI’20
float isi1 ( float x , int y ){
if ( y ==0){ return 1 ;}
else if (y >0) { return isi1 (x , - y );}
else { return isi1 (x , y +1)/ x ;}
}

Q 94. Given the pseudocode below for the function remains(), which of the following statements is true about TIFR’20
the output, if we pass it a positive integer n > 2?
int remains ( int n )
{
int x = n ;
for ( i =( n -1); i >1; i - -) {
x = x % i ;
}
return x ;
}

A. Output is always 0
B. Output is always 1
C. Output is 0 only if n is NOT a prime number
D. Output is 1 only if n is a prime number

30
 C Programming and Data Structures Programming in C Page 31 of 107

E. None of the above

Q 95. Let A be a matrix of size row × col. A has to be filled in a spiral clockwise fashion with successive ISI’21
integers from 1, 2, . . ., row × col starting from the top left corner. For example, a 3 × 4 matrix should
be filled in as follows:
1 2 3 4
10 11 12 5
9 8 7 6
Fill in all the blanks in the following code snippet to do the above job. In the answer script, write only
the while loop with the blanks filled-in.
# include < stdio .h >
# include < stdlib .h >
# define RIGHT 0
# define DOWN 1
# define LEFT 2
# define UP 3

void spiralFill ( int ** A , int r , int c ) {

int i , j , top , bottom , left , right , dir , k =1;
i = j = 0; dir = RIGHT ;
top = 0; bottom = r -1; left = 0; right = c -1;
while (( top <= _______ ) && ( left <= _______ )) {
A [ i ][ j ] = k ; k ++;
switch ( dir ) {
case RIGHT : if ( j < _______ ) _______ ;
else { dir = _______ ; top = _______ ; i = _______ ;}
break ;
case DOWN : if ( i < _______ ) _______ ;
else { dir = _______ ; right = _______ ; j = ______ ;}
break ;
case LEFT : if ( j > _______ ) _______ ;
else { dir = _______ ; bottom = _______ ; i = _____ ;}
break ;
case UP : if ( i > _______ ) _______ ;
else { dir = _______ ; left = _______ ; j = _______ ;}
break ;
}
}
}

int main () {
int ** A , row , col , i , j ;
printf ( " \ n Row and column size :: > " );
scanf ( " % d % d " , & row , & col );

A = ( int **) calloc ( row , sizeof ( int *));

for ( i =0; i < row ; i ++){
A [ i ] = ( int *) calloc ( col , sizeof ( int ));
}
spiralFill (A , row , col );
}

Q 96. Refer to the following two functions. CMI’22

int f ( int m ) { int g ( int m ) {
int a , b , c , d ; int a = 1;

31
 C Programming and Data Structures Programming in C Page 32 of 107

a = 0; b = 0; int i = 0;
c = 0; d = 1; while ( i < m ) {
while ( a < m ) { i = i + 1;
a = a + 1; a = 2 * a;
b = b + c; }
int temp = d ; return a ;
d = c; }
c = temp ;
}
return b ;
}

If g(f(n)) = 32, which of the following is a possible value of n?

A. 8 B. 11 C. 5 D. 64
Q 97. Consider the pseudocode below. Here n%6 denotes the remainder when n is divided by 6. The notation CMI’23
n//2 stands for integer division by 2. For example, 15 // 2 = 7, 36 // 2 = 18, 49 // 2 = 24, ...
function sixer ( n ):
count = 0
while n > 0:
if n % 6 == 0:
n = n- 1
else :
n = n // 2
count = count + 1
return count

Which of the following is true when sixer(n) is invoked with sufficiently large n, say n ≥ 106 ?
A. The value of count is approximately n/6
B. The value of count is approximately n/2
C. The value of count is approximately log2 (n)
D. The value of count is approximately (log2 (n))2

Q 98. Let A, B and C denote arrays of real numbers, where B has n − 1 entries and A, C have n entries each. CMI’23
Consider the following algorithm involving the three given arrays.
for k from 2 to n :
t = B [k -1]
B [k -1] = t / A [k -1]
A [ k ] = A [ k ] - t * B [k -1]
end for
for k from 2 to n :
C [ k ] = C [ k ] - B [k -1] * B [k -1]
end for
C [ n ] = C [ n ]/ A [ n ]
for k from n -1 to 1 with steps of -1:
C [ k ] = ( b [ k ]/ A [ k ]) - B [ k ] * b [ k +1]
end for

An arithmetic operation involves addition, subtraction, multiplication or division of real numbers. How
many arithmetic operations, in total, are performed in the algorithm above?
Note: Integer subtraction in array indices, like B[k-1], is not to be counted as an arithmetic operation.

Q 99. What does the following function compute in terms of n and d, for integer values of n and d, n > 1, ISI’23
d > 1? Note that a//b denotes the quotient (integer part) of a ÷ b, for integers a and b. For instance
7//3 is 2.

32
 C Programming and Data Structures Programming in C Page 33 of 107

function foo (n , d ){
x := 0;
while ( n >= 1) {
x := x +1;
n := n // d ;
}
return ( x );
}

A. The number of ways of choosing d elements from a set of size n.

B. The number of ways of rearranging d elements from a set of size n.
C. The number of digits in the base d representation of n.
D. The number of ways of partitioning n elements into groups of size d.

Q 100. In the following code, A is an array indexed from 0 whose elements are all positive integers, and n is CMI’24
the number of elements in A. It is given that n is at least 2. The operator ∗ denotes multiplication.
function foo (A , n ) {
if A [0] > A [1] {
first = A [0];
second = A [1];
} else {
first = A [1];
second = A [0];
}

for i from 2 to (n -1) {

if A [ i ] > second {
if A [ i ] > first {
second = first ;
first = A [ i ];
} else {
second = A [ i ];
}
}
}
return ( first * second );
}

If A = [15, 7, 16, 12, 17, 14, 16, 4, 13, 12], what will foo(A, 10) return?
A. 28 B. 144 C. 180 D. 272
Q 101. In the following code, A is an array indexed from 0 whose elements are all positive integers, and n is CMI’24
the number of elements in A.
function foo (A , n ) {
max = 0;
curr = 0;

for i from 1 to (n -1) {

if A [ i ] > A [i -1] {
curr = curr + 1;
if curr > max {
max = curr ;
}
} else {
curr = 0;

33
 C Programming and Data Structures Programming in C Page 34 of 107

}
}
return ( max +1);
}

If A = [1, 3, 5, 2, 4, 7, 6, 8], what will foo(A, 8) return?

A. 2 B. 3 C. 4 D. 5
Q 102. For any non-negative integers x and y, consider the following function ISI’24
f (x , y ){
if y is 0
return 0;
else
if y is even
return 2 f (x , [ y /2]);
else
return 2 f (x , [ y /2]) + x ;
}

Which of the following is true?

A. f(x+1, y+1) = 2f(x,y) + x + y C. f(x+1, y+1) = f(x,y) + x + y

B. f(x+1, y+1) = 2f(x,y) + x + y + 1 D. f(x+1, y+1) = f(x,y) + x + y + 1

Q 103. Consider the following algorithm that takes as input a positive integer n. TIFR’24
if ( n == 1) {
return " Neither prime nor composite . "
}
m = 2
while ( m < n ) {
if ( m divides n ) {
return " Composite . "
}
m = m +1
}
return " Prime . "

If n is a number of the form n = p2 q 3 r4 where p, q, r are natural numbers greater than 1, how many
times does the while loop in the algorithm run?
In the options below, for any real number m, ⌈m⌉ denotes the least integer greater than or equal to m.
A. The while loop runs at most ⌈n1/9 ⌉ times for all natural numbers p, q, r greater than one.
B. The while loop runs at most ⌈n1/9 ⌉ times only if p, q, r are all distinct.
C. The while loop runs at most ⌈n1/9 ⌉ times only if at least two of p, q, r are distinct.
D. The while loop runs at most ⌈n1/9 ⌉ times only if p, q, r are distinct primes.
E. The while loop runs at most ⌈n1/9 ⌉ times only if p, q, r are distinct primes or distinct prime powers.

Q 104. In the following pseudocode, assume that for any pair of integers x ≤ y, the function random(x, y) TIFR’24
produces an integer uniformly chosen from the set {x, x + 1, . . . , y}.
n = 9
for ( i = 1 to n ) {
A[i] = i
}
for ( i = 1 to n ) {

34
 C Programming and Data Structures Programming in C Page 35 of 107

r = random (i , n )
temp = A [ i ]
A[i] = A[r]
A [ r ] = temp
print A [ i ]
}

Which of the following statements is TRUE of the output of the code?

A. It outputs all permutations of 123456789 with equal probability.
B. It never outputs 123456789.
C. It outputs all cyclic permutations of 123456789 with equal probability, and does not print any other
output.
D. The output is always 987654321.
E. The output may not be a permutation of 123456789.

Q 105. The two arguments to the function foo(A, n) in the code below are: (i) an integer array A indexed CMI’25
from 0, and (ii) the number n of elements in A.
function foo (A , n ) {
count = 0;
for i from 0 to (n -1) {
for j from ( i +1) to (n -1) {
if ( A [ i ] > 2 * A [ j ]) {
count = count + 1;
}
}
}
return ( count );
}

Which of the following statements about the function foo(A, n) are correct?
A. foo(A, n) counts the number of index pairs (i, j) such that i < j and A[i] > 2 × A[j].
B. For the input A = [1,-4, 3,-5,-2], n = 5, the function returns 7.
C. For the input A = [1, 2, 3, 4, 5], n = 5, the function returns 0.
D. For the input A = [10, 5, 1], n = 3, the function returns 2.

Q 106. In the following code the operator % denotes the remainder after integer division. That is: for positive CMI’25
integers a, b the value a%b is the remainder obtained when a is divided by b.
function fizzbuzz ( n ) {
count = 0;
for i from 0 to (n -1) {
if (( i % 3) == 0) and (( i % 5) != 0) {
count = count + 1;
}
}
return ( count );
}

What does fizzbuzz(100) return?

A. 27 B. 33 C. 45 D. 60
Q 107. The next two questions pertain to the following code which takes a non-negative integer as input. CMI’25

35
 C Programming and Data Structures Programming in C Page 36 of 107

function foo ( n )
if ( n = 0) then
return 0
else if ( n = 1) then
return 1
else if ( n = 2) then
return 3
else return n + foo (n -1) + foo (n -2)
end if
end function

(i) What is the value returned by foo(5)?

A. 10 B. 14 C. 26 D. 35
(ii) Which of the following best describes the running time of foo(m)?

A. Linear in m. C. Cubic in m.
B. Quadratic in m. D. Exponential in m.

Q 108. Consider the following pseudocode. The program should take as
input n, and when it ends, the element TIFR’25
A[i] of the vector A should contain the binomial coefficient ni (with the index of A starting from 0).
In order to do so, what should replace the in the pseudocode?
procedure B i n om i a lC o e ff i c ie n t
input n
for i ← 0 to n do
A[i] ← 0
end for
A [0] ← 1
for i ← 1 to n do
B ← A
for j ← 1 to n do
A[j] ←
end for
end for
end procedure

B(j−1)×B(j)
A. B(j − 1) + B(j) D. 2
B. A(j − 1) + B(j − 1)
B(j)+B(n−j) A(j−1)+B(j−1)
C. 2 E. 2

36
 C Programming and Data Structures Programming in Python Page 37 of 107

Chapter 2 Programming in Python

Q 1. Consider the following Python code: 2024DA
def count ( child_dict , i ):
if i not in child_dict . keys ():
return 1
ans = 1
for j in child_dict [ i ]:
ans += count ( child_dict , j )
return ans

child_dict = dict ()
child_dict [0] = [1 ,2]
child_dict [1] = [3 ,4 ,5]
child_dict [2] = [6 ,7 ,8]
print ( count ( child_dict ,0))

Which ONE of the following is the output of this code?

A. 6 B. 1 C. 8 D. 9
Q 2. Consider the following Python function: 2024DA
def fun (D , s1 , s2 ):
if s1 < s2 :
D [ s1 ] , D [ s2 ] = D [ s2 ] , D [ s1 ]
fun (D , s1 +1 , s2 -1)

What does this Python function fun() do? Select the ONE appropriate option below.
A. It finds the smallest element in D from index s1 to s2, both inclusive.
B. It performs a merge sort in-place on this list D between indices s1 and s2, both inclusive.
C. It reverses the list D between indices s1 and s2, both inclusive.
D. It swaps the elements in D at indices s1 and s2, and leaves the remaining elements unchanged.

Q 3. Consider the following Python declarations of two lists. 2025DA

A =[1 ,2 ,3]
B =[4 ,5 ,6]

Which one of the following statements results in A= [1,2,3,4,5,6]?

A. [Link](B) B. [Link](B) C. [Link](B) D. [Link](B)

Q 4. Consider the following Python code snippet. 2025DA

A ={ " this " ," that " }
B ={ " that " ," other " }
C ={ " other " ," this " }
while " other " in C :
if " this " in A :
A ,B , C = A -B ,B -C ,C - A
if " that " in B :
A ,B , C = C |A , A |B , B | C

When the above program is executed, at the end, which of the following sets contains "this"?
A. Only A B. Only B C. Only C D. A,C

Q 5. Consider the following Python code snippet. 2025DA

37
C Programming and Data Structures Programming in Python Page 38 of 107

def f (a , b ):
if ( a ==0):
return b
if ( a %2==1):
return 2* f (( a -1)/2 , b )
return b + f (a -1 , b )

print ( f (15 ,10))

The value printed by the code snippet is . (Answer in integer)

38
 C Programming and Data Structures Recursion Page 39 of 107

Chapter 3 Recursion
Q 1. Consider the following C function definition 1999
int Trial ( int a , int b , int c )
{
if (( a >= b ) && (c < b )) return b ;
else if (a >= b ) return Trial (a , c , b );
else return Trial (b , a , c );
}

The function Trial:

A. Finds the maximum of a, b and c C. Finds the middle number of a, b and c

B. Finds the minimum of D. None of the above

Q 2. Consider the following C function: 2004

int f ( int n )
{
static int i = 1;
if ( n >= 5) return n ;
n = n+i;
i ++;
return f ( n );
}

The value returned by f(1) is:

A. 5 B. 6 C. 7 D. 8
Q 3. Choose the correct option to fill the ?1 and ?2 so that the program prints an input string in reverse 2004IT
order. Assume that the input string is terminated by a new line character.
# include < stdio .h >
void wrt_it ( void );
int main ( void ){
printf ( " Enter Text " );
printf ( " \ n " );
wrt_it ();
printf ( " \ n " );
return 0;
}
void wrt_it ( void ){
int c ;
if (?1)
wrt_it ();
?2
}

A. ?1 is getchar()! = ‘\n’ C. ?1 is c! =‘\n’

?2 is getchar(c); ?2 is putchar(c);
B. ?1 is (c = getchar())! = ‘\n’ D. ?1 is (c = getchar())! = ‘\n’
?2 is getchar(c); ?2 is putchar(c);

Q 4. Consider the following C-program: 2005

39
 C Programming and Data Structures Recursion Page 40 of 107

void foo ( int n , int sum ) {

int k = 0 , j = 0;
if ( n == 0) return ;
k = n % 10;
j = n /10;
sum = sum + k ;
foo (j , sum );
printf ( " %d , " ,k );
}

int main () {
int a = 2048 , sum = 0;
foo (a , sum );
printf ( " % d \ n " , sum );
}

What does the above program print?

A. 8, 4, 0, 2, 14 B. 8, 4, 0, 2, 0 C. 2, 0, 4, 8, 14 D. 2, 0, 4, 8, 0

Q 5. What is the output printed by the following program? 2005IT

# include < stdio .h >
int f ( int n , int k ) {
if ( n == 0) return 0;
else if ( n % 2) return f ( n /2 , 2* k ) + k ;
else return f ( n /2 , 2* k ) - k ;
}

int main () {
printf ( " % d " , f (20 , 1));
return 0;
}

A. 5 B. 8 C. 9 D. 20
m


Q 6. The following function computes the value of n correctly for all legal values m and n (m ≥ 1, n ≥ 0 2006IT
and m > n).
int func ( int m , int n )
{
if ( E ) return 1;
else return ( func ( m - 1 , n ) + func ( m - 1 , n - 1));
}

In the above function, which of the following is the correct expression for E?

A. (n==0) || (m = = 1) C. (n==0) || (m = = n)
B. (n==0) && (m = = 1) D. (n==0) && (m = = n)

Q 7. Consider the following C function: 2007

int f ( int n )
{
static int r = 0;
if ( n <= 0) return 1;
if ( n > 3)
{
r = n;

40
 C Programming and Data Structures Recursion Page 41 of 107

return f (n -2) + 2;
}
return f (n -1) + r ;
}

What is the value of f(5)?

A. 5 B. 7 C. 9 D. 18
Q 8. The function f is defined as follows: 2007IT
int f ( int n ) {
if ( n <= 1) return 1;
else if ( n % 2 == 0) return f ( n /2);
else return f (3 n - 1);
}

Assuming that arbitrarily large integers can be passed as a parameter to the function, consider the
following statements.
i. The function f terminates for finitely many different values of n ≥ 1.
ii. The function f terminates for infinitely many different values of n ≥ 1.
iii. The function f does not terminate for finitely many different values of n ≥ 1.
iv. The function f does not terminate for infinitely many different values of n ≥ 1.
Which one of the following options is true of the above?
A. i and iii B. i and iv C. ii and iii D. ii and iv
Q 9. Choose the correct option to fill ?1 and ?2 so that the program below prints an input string in reverse 2008
order. Assume that the input string is terminated by a new line character.
void reverse ( void )
{
int c ;
if (?1) reverse ();
?2
}
main ()
{
printf ( " Enter text " );
printf ( " \ n " );
reverse ();
printf ( " \ n " );
}

A. ?1 is getchar() ! = ‘\n’ C. ?1 is c! =‘\n’

?2 is getchar(c); ?2 is putchar(c);
B. ?1 is (c = getchar()); ! = ‘\n’ D. ?1 is (c = getchar()) ! = ‘\n’
?2 is getchar(c); ?2 is putchar(c);

Q 10. Consider the program below: 2009

# include < stdio .h >
int fun ( int n , int * f_p ) {
int t , f ;
if ( n <= 1) {
* f_p = 1;
return 1;

41
 C Programming and Data Structures Recursion Page 42 of 107

}
t = fun (n -1 , f_p );
f = t + * f_p ;
* f_p = t ;
return f ;
}

int main () {
int x = 15;
printf ( " % d / n " , fun (5 , & x ));
return 0;
}

The value printed is:

A. 6 B. 8 C. 14 D. 15
Q 11. What is the value printed by the following C program? 2010
# include < stdio .h >
int f ( int *a , int n )
{
if ( n <= 0) return 0;
else if (* a % 2 == 0) return * a + f ( a +1 , n -1);
else return * a - f ( a +1 , n -1);
}

int main ()
{
int a [] = (12 , 7 , 13 , 4 , 11 , 6);
printf ( " % d " , f (a , 6));
return 0;
}

A. -9 B. 5 C. 15 D. 19
Q 12. Consider the following recursive C function that takes two arguments. 2011
unsigned int foo ( unsigned int n , unsigned int r ) {
if (n >0) return (( n % r ) + foo ( n /r , r ));
else return 0;
}

(i) What is the return value of the function foo when it is called as foo(345, 10)?
A. 345 B. 12 C. 5 D. 3
(ii) What is the return value of the function foo when it is called as foo(513, 2)?
A. 9 B. 8 C. 5 D. 2
Q 13. What is the return value of f(p,p), if the value of p is initialized to 5 before the call? Note that the 2013
first parameter is passed by reference, whereas the second parameter is passed by value.
int f ( int &x , int c ) {
c = c - 1;
if ( c ==0) return 1;
x = x + 1;
return f (x , c ) * x ;
}

A. 3024 B. 6501 C. 55440 D. 161051

42
 C Programming and Data Structures Recursion Page 43 of 107

Q 14. Consider the following function. 2014Set2

double f ( double x ){
if ( abs ( x * x - 3) < 0.01)
return x ;
else
return f ( x /2 + 1.5/ x );
}

Give a value q (to 2 decimals) such that f(q) will return q: .

Q 15. Consider the following C function. 2015Set2

int fun ( int n ) {
int x =1 , k ;
if ( n ==1) return x ;
for ( k =1; k < n ; ++ k )
x = x + fun ( k ) * fun (n - k );
return x ;
}

The return value of fun(5) is .

Q 16. Consider the following recursive C function. 2015Set3
void get ( int n )
{
if (n <1) return ;
get (n -1);
get (n -3);
printf ( " % d " , n );
}

If get(6) function is being called in main() then how many times will the get() function be invoked
before returning to the main()?
A. 15 B. 25 C. 35 D. 45

Q 17. Consider the following program: 2016Set2

int f ( int * p , int n )
{
if ( n <= 1) return 0;
else return max ( f ( p +1 , n -1) , p [0] - p [1]);
}
int main ()
{
int a [] = {3 , 5 , 2 , 6 , 4};
printf ( " % d " , f (a , 5));
}

Note: max(x,y) returns the maximum of x and y.

The value printed by this program is .

Q 18. Consider the C functions foo and bar given below: 2017Set1

43
 C Programming and Data Structures Recursion Page 44 of 107

int foo ( int val ) { int bar ( int val ) {

int x = 0; int x = 0;
while ( val > 0) { while ( val > 0) {
x = x + foo ( val - -); x = x + bar ( val -1);
} }
return val ; return val ;
} }

Invocations of foo(3) and bar(3) will result in:

A. Return of 6 and 6 respectively.
B. Infinite loop and abnormal termination respectively.
C. Abnormal termination and infinite loop respectively.
D. Both terminating abnormally.

Q 19. Consider the following two functions: 2017Set1

void fun1 ( int n ) { void fun2 ( int n ) {

if ( n == 0) return ; if ( n == 0) return ;
printf ( " % d " , n ); printf ( " % d " , n );
fun2 ( n - 2); fun1 (++ n );
printf ( " % d " , n ); printf ( " % d " , n );
} }

The output printed when fun1(5) is called is

A. 53423122233445 B. 53423120112233 C. 53423122132435 D. 53423120213243
Q 20. Consider the following C program: 2018
# include < stdio .h >
int counter =0;

int calc ( int a , int b ) {

int c ;
counter ++;
if ( b ==3) return ( a * a * a );
else {
c = calc (a , b /3);
return ( c * c * c );
}
}
int main () {
calc (4 , 81);
printf ( " % d " , counter );
}

The output of this program is .

Q 21. Consider the following program written in pseudo-code. Assume that x and y are integers. 2018
Count (x , y ) {
if ( y != 1 ) {
if ( x != 1) {
print ( " * " );
Count ( x /2 , y );
}

44
 C Programming and Data Structures Recursion Page 45 of 107

else {
y =y -1;
Count (1024 , y );
}
}
}

The number of times that the print statement is executed by the call Count(1024,1024) is .

Q 22. Consider the following C function. 2019

void convert ( int n ) {
if (n <0)
printf { " % d " , n );
else {
convert ( n /2);
printf ( " % d " , n %2);
}
}

Which one of the following will happen when the function convert is called with any positive integer n
as argument?
A. It will print the binary representation of n and terminate
B. It will print the binary representation of n in the reverse order and terminate
C. It will print the binary representation of n but will not terminate
D. It will not print anything and will not terminate
Q 23. Consider the following C functions. 2020

int fun1 ( int n ) { int fun2 ( int n ) {

static int i = 0; static int i = 0;
if ( n > 0) { if (n >0) {
++ i ; i = i + fun1 ( n );
fun1 (n -1); fun2 (n -1);
} }
return ( i ); return ( i );
} }

The return value of fun2(5) is .

Q 24. Consider the following C functions. 2020

int tob ( int b , int * arr ) { int pp ( int a , int b ) {

int i ; int arr [20];
for ( i = 0; b >0; i ++) { int i , tot = 1 , ex , len ;
if ( b %2) arr [ i ] = 1; ex = a ;
else arr [ i ] = 0; len = tob (b , arr );
b = b /2; for ( i =0; i < len ; i ++) {
} if ( arr [ i ] == 1)
return ( i ); tot = tot * ex ;
} ex = ex * ex ;
}
return ( tot ) ;
}

The value returned by pp(3,4) is .

45
 C Programming and Data Structures Recursion Page 46 of 107

Q 25. Consider the following ANSI C function: 2021Set2

int SomeFunction ( int x , int y )
{
if (( x == 1) || ( y == 1)) return 1;
if ( x == y ) return x ;
if ( x > y ) return SomeFunction (x -y , y );
if ( y > x ) return SomeFunction (x , y - x );
}

The value returned by SomeFunction(15,255) is .

Q 26. Consider the following ANSI C program. 2021Set2

# include < stdio .h >
int foo ( int x , int y , int q )
{
if (( x <=0) && (y <=0))
return q ;
if (x <=0)
return foo (x , y -q , q );
if (y <=0)
return foo (x -q , y , q );
return foo (x , y -q , q ) + foo (x -q , y , q );
}
int main ( )
{
int r = foo (15 , 15 , 10);
printf ( " % d " , r );
return 0;
}

The output of the program upon execution is .

Q 27. Consider the following program: 2023

int main () { int f1 () { int f2 ( int X ) { int f3 () {

f1 (); return (1); f3 (); return (5);
f2 (2); } if ( X ==1) }
f3 (); return f1 ();
return (0); else
} return ( X * f2 (X -1));
}

Which one of the following options represents the activation tree corresponding to the main function?

A. B. C. D.
Q 28. Consider the following C program: 2024Set1

46
 C Programming and Data Structures Recursion Page 47 of 107

# include < stdio .h > void fX (){

void fX (); char a ;
int main (){ if (( a = getchar ()) != ‘\ n ’)
fX (); fX ();
return 0; if ( a != ‘\ n ’)
} putchar ( a );
}

Assume that the input to the program from the command line is 1234 followed by a newline character.
Which one of the following statements is CORRECT?
A. The program will not terminate
B. The program will terminate with no output
C. The program will terminate with 4321 as output
D. The program will terminate with 1234 as output

Q 29. Consider the following C program. Assume parameters to a function are evaluated from right to left. 2024Set2
# include < stdio .h >

int g ( int p ) { printf ( " % d " , p ); return p ; }

int h ( int q ) { printf ( " % d " , q ); return q ; }

void f ( int x , int y ) {

g ( x );
h ( y );
}
int main () {
f ( g (10) , h (20));
}

Which one of the following options is the CORRECT output of the above C program?
A. 20101020 B. 10202010 C. 20102010 D. 10201020

Q 30. # include < stdio .h > 2025Set1

int foo ( int S [] , int size ){
if ( size == 0) return 0;
if ( size == 1) return 1;
if ( S [0] != S [1]) return 1+ foo ( S +1 , size -1);
return foo ( S +1 , size -1);
}
int main (){
int A []={0 ,1 ,2 ,2 ,2 ,0 ,0 ,1 ,1};
printf ( " % d " , foo (A ,9));
return 0;
}

The value printed by the given C program is . (Answer in integer)

Q 31. Consider the following C program: 2025Set2

# include < stdio .h >
int g ( int n ) {
return ( n +10);
}
int f ( int n ) {

47
 C Programming and Data Structures Recursion Page 48 of 107

return g ( n *2);
}

int main () {
int sum , n ;
sum =0;
for ( n =1; n <3; n ++)
sum += g ( f ( n ));
printf ( " % d " , sum );
return 0;
}
The output of the above program is . (Answer in integer)
Q 32. A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array 2000
f [0 . . . m] with all elements initialized to 0.
fib ( n ) {
if ( n > m ) error ();
if ( n == 0) return 1;
if ( n == 1) return 1;
if ( _ ) _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ (1)
return __ _ _ __ _ _ _ __ _ _ __ _ _ __ (2)
t = fib ( n - 1) + fib ( n - 2);
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ (3)
return t ;
}
(i) Fill in the boxes with expressions/statement to make fib() store and reuse computed Fibonacci
values. Write the box number and the corresponding contents in your answer book.
(ii) What is the time complexity of the resulting program when computing fib()?
Q 33. The following recursive function in C is a solution to the Towers of Hanoi problem. 2002
void move ( int n , char A , char B , char C ) {
if ( . . . . . . . . . . . . . . . . . . . . . . ) {
move ( . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ) ;
printf ( " Move disk % d from pole % c to pole % c \ n " , n , A , C );
move ( . . . . . . . . . . . . . . . . . . . . . ) ;
}
}
Fill in the dotted parts of the solution.
Q 34. Consider the following function. 1997
Function F(n, m:integer:integer);
begin
if (n<=0) or (m<=0) then F:=1
else
F:=F(n-1, m) + F(n-1, m-1);
end;
     
n n−1 n−1
Use the recurrence relation = + to answer the following questions. Assume that
k k k−1
n, m are positive integers. Write only the answers without any explanation.
(i) What is the value of F (n, 2)?
(ii) What is the value of F (n, m)?
(iii) How many recursive calls are made to the function F , including the original call, when evaluating
F (n, m)?

48
 C Programming and Data Structures Recursion Page 49 of 107

3.1 More Questions

Q 35. Consider the recursive function mc91: TIFR’16

int mc91 ( int n )
{
print n
if ( n > 100) {
return n -10;
}
else {
return mc91 ( mc91 ( n +11));
}
}

Let
Out = {n : there is an x ∈ {0, 1, . . . , 100} such that n is one of the integers printed by mc91(x)}
Then which of the following is Out?
A. {n : −∞ < n ≤ 100}
B. {n : 0 ≤ n ≤ 101}
C. {n : 0 ≤ n ≤ 110}
D. {n : 0 ≤ n ≤ 111}
E. {n : 0 ≤ n < +∞}

Q 36. Consider the following function definition. TIFR’18

void greet ( int n )
{
if (n >0)
{
printf ( " hello " );
greet (n -1);
}
printf ( " world " );
}

If you run greet(n) for some non-negative integer n, what would it print?
A. n times “hello”, followed by n + 1 times “world”
B. n times “hello”, followed by n times “world”
C. n times “helloworld”
D. n + 1 times “helloworld”
E. n times “helloworld”, followed by “world”

Q 37. Given the following pseudocode for function printx() below, how many times is x printed if we execute TIFR’19
printx(5)?
void printx ( int n ) {
if ( n ==0){
printf ( " x " );
}
for ( int i =0; i <= n -1;++ i ){
printx (n -1);
}
}

49
 C Programming and Data Structures Recursion Page 50 of 107

A. 625 B. 256 C. 120 D. 24 E. 5

Q 38. Consider the following pseudocode: TIFR’21
procedure HowManyDash ( n )
if n =0 then
print ‘- ’
else if n =1 then
print ‘- ’
else
HowManyDash (n -1)
HowManyDash (n -2)
end if
end procedure

How many ‘-’ does HowManyDash(10) print?

A. 9 B. 10 C. 55 D. 89 E. 1024
Q 39. The next two questions refer to the following two functions. We assume that all the arguments are CMI’23
non-negative integers. The operation x div 2 divides x by 2 and returns an integer, discarding the
fractional part.

int f ( int x , int i ) { int g ( int x ) {

if ( i == 0) { if ( x <= 2)
if ( even x ) return 1;
return 0; else
else return 1 + g ( x div 3);
return 1; }
} else {
return f ( x div 2 , i -1);
}
}

(i) For how many values of i will f(1000,i) return 1?

A. 2 B. 5 C. 6 D. 10
(ii) What is the value of g(10000)?
A. 3 B. 9 C. 12 D. 15
Q 40. Consider the following pseudocodes of two functions, where u % 2 denotes the remainder when u is CMI’23
divided by 2. The function abs(v) returns the absolute value of an integer v.
function foo1 ( u ):
if u % 2 == 0 AND abs ( u ) > 0:
u = u + foo2 (u -1)
return u

function foo2 ( v ):
if v % 2 == 1 AND abs ( v ) > 1:
v = v + foo1 (v -1)
return v

Which of the following is/are true?

A. foo1, when called on a positive integer u, returns u(u + 1)/2
B. foo2, when called on an odd positive integer v, returns v(v + 1)/2
C. foo2(-13) goes into innite recursion
D. foo1(14) returns 105

50
 C Programming and Data Structures Time Complexity Page 51 of 107

Chapter 4 Time Complexity

4.1 Solve Recurrence

Q 1. Solve the recurrence equation T (n) = T (n − 1) + n, T (1) = 1. 1987

Q 2. Solve the recurrence equations T (n) = T (n/2) + 1, T (1) = 1. 1988

Q 3. Find a solution to the following recurrence equation: 1989

√
• T (n) = n + T n2

• T (1) = 1

Q 4. Solve the recurrence relation 1998

xn = 2xn−1 − 1, n > 1
x1 = 2
Q 5. The solution of the recurrence equation T (2k ) = 3T (2k−1 ) + 1, T (1) = 1 is 2002
k+1
(3 −1)
A. 2k B. 2 C. 3log2 k D. 2log3 k

Q 6. Consider the following recurrence relation 2003

T (1) = 1 √
T (n + 1) = T (n) + ⌊ n + 1⌋ for all n ≥ 1
The value of T (m2 ) for m ≥ 1 is

m m


A. 6 (21m − 39) + 4 C. 2 3m2.5 − 11m + 20 − 5
m m 5



B. 6 4m2 − 3m + 5 D. 6 5m3 − 34m2 + 137m − 104 + 6

Q 7. The recurrence equation 2004

T (1) = 1
T (n) = 2T (n − 1) + n, n ≥ 2
evaluates to
A. 2n+1 − n − 2 B. 2n − n C. 2n+1 − 2n − 2 D. 2n + n
Q 8. (MSQ) Consider the following recurrence: 2022

f (1) = 1;
f (2n) = 2f (n) − 1, for n ≥ 1;
f (2n + 1) = 2f (n) + 1, for n ≥ 1.

Then, which of the following statements is/are TRUE?

A. f (2n − 1) = 2n − 1 B. f (2n ) = 1 C. f (5 · 2n ) = 2n+1 + 1 D. f (2n + 1) = 2n + 1

Q 9. Let T (n) be the recurrence relation defined as follows: 2024Set2

T (0) = 1,
T (1) = 2, and
T (n) = 5T (n − 1) − 6T (n − 2) for n ≥ 2

Which one of the following statements is TRUE?

A. T (n) = Θ (2n ) B. T (n) = Θ (n2n ) C. T (n) = Θ (3n ) D. T (n) = Θ (n3n )

51
 C Programming and Data Structures Time Complexity Page 52 of 107

4.2 Asymptotic Analysis

X
Q 10. O(n), where O(n) stands for order n is: 1993
1≤k≤n

A. O(n) B. O(n2 ) C. O(n3 ) D. O(3n2 ) E. O(1.5n2 )

Q 11. Consider the following two functions: 1994

( (
n3 for 0 ≤ n ≤ 10, 000 n for 0 ≤ n ≤ 100
g1 (n) = g2 (n) =
n2 for n > 10, 000 n3 for n > 100

Which of the following is true?

A. g1 (n) is O(g2 (n)) B. g1 (n) is O(n3 ) C. g2 (n) is O(g1 (n)) D. g2 (n) is O(n)

Q 12. Which of the following is False? 1996

A. 100n log n = O( n 100

log n
) C. If 0 < x < y then nx = O (ny )
√
B. log n = O(log log n) D. 2n ̸= O (nk)

Q 13. The recurrence relation 1996

• T (1) = 2
• T (n) = 3T ( n4 ) + n
has the solution T (n) equal to
 3
A. O(n) B. O(log n) C. O n 4 D. None of the above
√
Q 14. Let T(n) be the function defined by T (1) = 1, T (n) = 2T (⌊ n2 ⌋) + n for n ≥ 2. Which of the following 1997
statements is true?
√
A. T (n) = O n B. T (n) = O(n) C. T (n) = O(log n) D. None of the above

Q 15. If T1 = O(1), give the correct matching for the following pairs: 1999

(M) Tn = Tn−1 + n (U) Tn = O(n)

(N) Tn = Tn/2 + n (V) Tn = O(n log n)
(O) Tn = Tn/2 + n log n (W) Tn = O(n2 )
(P) Tn = Tn−1 + log n (X) Tn = O(log2 n)
A. M-W, N-V, O-U, P-X C. M-V, N-W, O-X, P-U
B. M-W, N-U, O-X, P-V D. M-W, N-U, O-V, P-X

Q 16. Consider the following functions 2000

√
n
f (n) = 3n
√
g(n) = 2 nlog2 n
h(n) = n!
Which of the following is true?
A. h(n) is O(f (n)) B. h(n) is O(g(n)) C. g(n) is not O(f (n)) D. f (n) is O(g(n))

Q 17. Let f (n) = n2 log n and g(n) = n(log n)10 be without positive functions of n. Which of the following 2001
statements is correct?

52
 C Programming and Data Structures Time Complexity Page 53 of 107

A. f (n) = O(g(n)) and g(n) ̸= O(f (n)) C. f (n) ̸= O(g(n)) and g(n) ≥ O(f (n))
B. g(n) = O(f (n)) and f (n) ̸= O(g(n)) D. f (n) = O(g(n)) and g(n) = O(f (n))

Q 18. Consider the following three claims: 2003

I. (n + k)m = Θ(nm ) where k and m are constants
II. 2n+1 = O(2n )
III. 22n+1 = O(2n )
Which of the following claims are correct?
A. I and II B. I and III C. II and III D. I, II, and III
Q 19. Let f (n), g(n) and h(n) be functions defined for positive integers such that f (n) = O(g(n)), g(n) ̸= 2004IT
O(f (n)), g(n) = O(h(n)) and h(n) = O(g(n)).
Which one of the following statements is FALSE?

A. f (n) + g(n) = O(h(n) + h(n)) C. h(n) ̸= O(f (n))

B. f (n) = O(h(n)) D. f (n)h(n) ̸= O(g(n)h(n))

Q 20. Suppose T (n) = 2T ( n2 ) + n, T (0) = T (1) = 1 2005

Which one of the following is FALSE?
A. T (n) = O(n2 ) B. T (n) = Θ(n log n) C. T (n) = Ω(n2 ) D. T (n) = O(n log n)

Q 21. Let T(n) be a function defined by the recurrence 2005IT

√
T (n) = 2T (n/2) + n for n ≥ 2 and T (1) = 1
Which of the following statements is TRUE?
√
A. T (n) = Θ(log n) B. T (n) = Θ( n) C. T (n) = Θ(n) D. T (n) = Θ(n log n)

Q 22. Consider the following recurrence: 2006

√
T (n) = 2T ( n) + 1, T (1) = 1
Which one of the following is true?
√
A. T (n) = Θ(log log n) B. T (n) = Θ(log n) C. T (n) = Θ( n) D. T (n) = Θ(n)

Q 23. Consider the following functions: 2008

• f (n) = 2n • g(n) = n! • h(n) = nlog n

Which of the following statements about the asymptotic behavior of f (n), g(n) and h(n) is true?

A. f (n) = O (g (n)) ; g (n) = O (h (n)) C. g (n) = O (f (n)) ; h (n) = O (f (n))

B. f (n) = Ω (g (n)) ; g(n) = O (h (n)) D. h (n) = O (f (n)) ; g (n) = Ω (f (n))
√ √
Q 24. When n = 22k for some k ≥ 0, the recurrence relation T (n) = 2T (n/2) + n, T (1) = 1 evaluates to : 2008IT
√ √ √ √ √
A. n(log n + 1) B. n log n C. n log n D. n log n

Q 25. The running time of an algorithm is represented by the following recurrence relation: 2009
(
n n≤3
T (n) = n
T ( 3 ) + cn otherwise
Which one of the following represents the time complexity of the algorithm?
A. Θ(n) B. Θ(n log n) C. Θ(n2 ) D. Θ(n2 log n)

Q 26. Which of the given options provides the increasing order of asymptotic complexity of functions f1 , f2 , 2011
f3 and f4 ?

53
 C Programming and Data Structures Time Complexity Page 54 of 107

• f1 (n) = 2n • f2 (n) = n3/2 • f3 (n) = n log2 n • f4 (n) = nlog2 n

A. f3 , f2 , f4 , f1 C. f2 , f3 , f1 , f4
B. f3 , f2 , f1 , f4 D. f2 , f3 , f4 , f1

Q 27. Let W (n) and A(n) denote respectively, the worst case and average case running time of an algorithm 2012
executed on an input of size n. Which of the following is ALWAYS TRUE?
A. A(n) = Ω(W (n)) B. A(n) = Θ(W (n)) C. A(n) = O(W (n)) D. A(n) = o(W (n))

Q 28. Which one of the following correctly determines the solution of the recurrence relation with T (1) = 1? 2014Set2
T (n) = 2T n2 + log n

A. Θ(n) B. Θ(n log n) C. Θ(n2 ) D. Θ(log n)

n
X
Q 29. Consider the equality i3 = X and the following choices for X: 2015Set3
i=0

I. Θ(n4 ) II. Θ(n5 ) III. O(n5 ) IV. Ω(n3 )

The equality above remains correct if X is replaced by

A. Only I B. Only II C. I or III or IV but not II D. II or III or IV but not I

Q 30. Consider the following functions from positive integers to real numbers: 2017Set1
√
10, n, n, log2 n, 100
n
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
100 √ 100 √
A. log2 n, n , 10, n, n C. 10, n , n, log2 n, n
100 √ 100 √
B. n , 10, log2 n, n, n D. n , log2 n, 10, n, n

Q 31. Consider the recurrence function 2017Set2

( √
2T ( n) + 1, n > 2
T (n) =
2, 0<n≤2

Then T (n) in terms of Θ notation is

√
A. Θ(log log n) B. Θ(log n) C. Θ( n) D. Θ(n)

Q 32. For parameters a and b, both of which are ω(1), T (n) = T (n1/a ) + 1, and T (b) = 1. Then T (n) is 2020
A. Θ(loga logb n) B. Θ(logab n) C. Θ(logb loga n) D. Θ(log2 log2 n)

Q 33. Consider the following three functions. 2021Set1

√
f1 = 10n f2 = nlog n f3 = n n

Which one of the following options arranges the functions in the increasing order of asymptotic growth
rate?
A. f3 , f2 , f1 B. f2 , f1 , f3 C. f1 , f2 , f3 D. f2 , f3 , f1

Q 34. Consider the following recurrence relation. 2021Set1


T (n/2) + T (2n/5) + 7n if n > 0
T (n) =
1 if n = 0
Which one of the following options is correct?
A. T (n) = Θ(n5/2 ) B. T (n) = Θ(n log n) C. T (n) = Θ(n) D. T (n) = Θ((log n)5/2 )

54
 C Programming and Data Structures Time Complexity Page 55 of 107

Q 35. For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers: 2021Set2
n
T (n) = a · T + f (n)
b

Which one of the following options is correct about the recurrence T (n)?
A. If f (n) is n log2 (n), then T (n) is Θ(n log2 (n)).
n
B. If f (n) is , then T (n) is Θ(log2 (n)).
log2 (n)
C. If f (n) is O(nlogb (a)−ϵ ) for some ϵ > 0, then T (n) is Θ(nlogb (a) )
D. If f (n) is Θ(nlogb (a) ), then T (n) is Θ(nlogb (a) )

Q 36. (MSQ) Let f and g be functions of natural numbers given by f (n) = n and g(n) = n2 . Which of the 2023
following statements is/are TRUE?
A. f ∈ O(g) B. f ∈ Ω(g) C. f ∈ o(g) D. f ∈ Θ(g)

Q 37. Consider the following recurrence relation: 2024Set1

(√ √
n T ( n) + n for n ≥ 1
T (n) =
1 for n = 1

Which one of the following options is CORRECT?

A. T (n) = Θ(n log log n) B. T (n) = Θ(n log n) C. T (n) = Θ(n2 log n) D. T (n) = Θ(n2 log log n)

Q 38. Consider the following recurrence relation: 2025Set1

n
T (n) = 2T (n − 1) + n2 for n > 0, T (0) = 1.
Which ONE of the following options is CORRECT?
A. T (n) = Θ(n2 2n ) B. T (n) = Θ(n2n ) C. T (n) = Θ((log n)2 2n ) D. T (n) = Θ(4n )

4.3 Code Analysis

Q 39. The running time of the following algorithm: 2002

Procedure A(n)
√
If n ≤ 2 return (1) else return (A(⌈ n⌉));
is best described by
A. O(n) B. O(log n) C. O(log log n) D. O(1)

Q 40. The time complexity of the following C function is (assume n > 0): 2004
int recursive ( int n ) {
if ( n == 1)
return (1);
else
return ( recursive (n -1) + recursive (n -1));
}

A. O(n) B. O(n log n) C. O(n2 ) D. O(2n )

Q 41. Consider the following C-program fragment in which i, j, and n are integer variables. 2006
for ( i = n , j = 0; i > 0; i /= 2 , j += i );

55
 C Programming and Data Structures Time Complexity Page 56 of 107

Let val(j) denote the value stored in the variable j after termination of the for loop. Which one of the
following is true?
√
A. val(j) = Θ(log n) B. val(j) = Θ( n) C. val(j) = Θ(n) D. val(j) = Θ(n log n)

Q 42. The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except 2016Set2
for the recursive calls, have O(1) time complexity. If the worst case time complexity of this function is
O(nα ), then the least possible value (accurate up to two decimal positions) of α is .

Figure 1: Flow chart for Recursive Function A(n)

Q 43. Consider the following segment of C-code: 2007

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:
A. ⌈log2 n⌉ + 1 B. n C. ⌈log2 n⌉ D. ⌊log2 n⌋ + 1

Q 44. What is the time complexity of the following recursive function: 2007
int DoSomething ( int n ) {
if ( n <= 2)
return 1;
else
return ( DoSomething ( floor ( sqrt ( n ))) + n );
}

A. Θ(n2 ) B. Θ(n log2 n) C. Θ(log2 n) D. Θ(log2 log2 n)

Q 45. Consider the following C program segment: 2007

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

56
 C Programming and Data Structures Time Complexity Page 57 of 107

Let T (n) denote number of times the for loop is executed by the program on input n. Which of the
following is TRUE?
√ √ √
A. T (n) = O( n) and T (n) = Ω( n) C. T (n) = O(n) and T (n) = Ω( n)
√
B. T (n) = O( n) and T (n) = Ω(1) D. None of the above

Q 46. Consider the following C functions: 2008

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

(i) f1(8) and f2(8) return the values

A. 1661 and 1640 B. 59 and 59 C. 1640 and 1640 D. 1640 and 1661
(ii) The running time of f1(n) and f2(n) are:
A. Θ(n) and Θ(n) B. Θ(2n ) and Θ(n) C. Θ(n) and Θ(2n ) D. Θ(2n ) and Θ(2n )

Q 47. Consider the following function: 2013

int unknown ( int n ){

int i , j , k =0;
for ( i = n /2; i <= n ; i ++)
for ( j =2; j <= n ; j = j *2)
k = k + n /2;
return ( k );
}

The return value of the function is

A. Θ(n2 ) B. Θ(n2 log n) C. Θ(n3 ) D. Θ(n3 log n)

Q 48. Consider the following C function. 2015Set1

int fun1 ( int n ) {
int i , j , k , p , q = 0;
for ( i = 1; i < n ; ++ i )
{
p = 0;
for ( j = n ; j > 1; j = j /2)
++ p ;

57
 C Programming and Data Structures Time Complexity Page 58 of 107

for ( k = 1; k < p ; k = k * 2)
++ q ;
}
return q ;
}

Which one of the following most closely approximates the return value of the function fun1?
A. n3 B. n(log n)2 C. n log n D. n log(log n)

Q 49. Consider the following C function 2017Set2

int fun ( int n ) {
int i , j ;
for ( i =1; i <= n ; i ++) {
for ( j =1; j < n ; j += i ) {
printf ( " % d % d " , i , j );
}
}
}

Time complexity of fun in terms of Θ notation is

√
A. Θ(n n) B. Θ(n2 ) C. Θ(n log n) D. Θ(n2 log n)

Q 50. Consider functions Function 1 and Function 2 expressed in pseudocode as follows: 2023

Function_1 Function_2
while n > 1 do for i = 1 to 100* n do
for i = 1 to n do x = x +1;
x = x +1; end for
end for
n = n /2;
end while

Let f1 (n) and f2 (n) denote the number of times the statement ‘‘x = x + 1’’ is executed in Function 1
and Function 2 respectively.
Which of the following statements is/are TRUE?

A. f1 (n) ∈ Θ (f2 (n)) C. f1 (n) ∈ ω (f2 (n))

B. f1 (n) ∈ o (f2 (n)) D. f1 (n) ∈ O(n)

Q 51. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n 2012
discs is

A. T (n) = 2T (n − 2) + 2 C. T (n) = 2T (n/2) + 1

B. T (n) = 2T (n − 1) + n D. T (n) = 2T (n − 1) + 1

Q 52. Consider the following pseudo code. What is the total number of multiplications to be performed? 2014Set1
D = 2
for i = 1 to n do
for j = i to n do
for k = j + 1 to n do
D = D * 3

A. Half of the product of the 3 consecutive integers.

58
 C Programming and Data Structures Time Complexity Page 59 of 107

B. One-third of the product of the 3 consecutive integers.

C. One-sixth of the product of the 3 consecutive integers.
D. None of the above
Q 53. In the following C function, let n ≥ m. 2007
int gcd (n , m ) {
if ( n % m == 0) return m ;
n = n%m;
return gcd (m , n );
}

How many recursive calls are made by this function?

√
A. Θ(log2 n) B. Ω(n) C. Θ(log2 log2 n) D. Θ( n)

Q 54. Consider the following C function: 2005

double foo ( int n )
{
int i ;
double sum ;
if ( n == 0)
{
return 1.0;
}
else
{
sum = 0.0;
for ( i = 0; i < n ; i ++)
{
sum += foo ( i );
}
return sum ;
}
}

(i) The space complexity of the above function is:

A. O(1) B. O(n) C. O(n!) D. O(nn )
(ii) Suppose we modify the above function foo() and store the values of foo(i), 0 ≤ i < n, as and when
they are computed. With this modification, the time complexity for function foo() is significantly
reduced. The space complexity of the modified function would be:
A. O(1) B. O(n) C. O(n2 ) D. O(n!)

4.4 More Questions

Q 55. Solve the following recurrence (n is a natural number): ISI’11

(
7T (n ÷ 3) + n2 ; n > 2
T (n) =
1 ; n ≤ 2.

Q 56. Let n be a large integer. Which of the following statements is TRUE? TIFR’11
√ 1 p 1
A. n log2 n < log2 n < n 100
1 √ 1 p
B. n 100 < n log2 n < log2 n

59
 C Programming and Data Structures Time Complexity Page 60 of 107

1 √ 1 p
C. n 100 < n log2 n < log2 n
p √ 1 1
D. log2 n < n log2 n < n 100
p 1 √ 1
E. log2 n < n 100 < n log2 n

Q 57. Let n be a large integer. Which of the following statements is TRUE? TIFR’12
√
2 log n n
A. 2 < log n < n1/3
√
n 1/3
B. log n < n < 2 2 log n
√
C. 2 2 log n < n1/3 < logn n
√
D. n1/3 < 2 2 log n < logn n
√
n 2 log n<n1/3
E. log n < 2

Q 58. Which of the following statements is TRUE for all sufficiently large n? TIFR’14
√
log log n log n
A. (log n) <2 < n1/4
√
log n log log n
B. 2 < n1/4 < (log n)
√
log log n
C. n1/4 < (log n) <2 log n
√
log log n
D. (log n) < n1/4 < 2 log n
√
log n log log n
E. 2 < (log n) < n1/4

Q 59. Which of these functions grows fastest with n? TIFR’14

n n−0.9 log n n n−1
A. e /n. B. e . C. 2 . D. (log n) . E. None of the above.

Q 60. Consider the following recurrence relation: TIFR’14

(
T nk + T 3n



4 + n if n ≥ 2
T (n) =
1 if n = 1
Which of the following statements is FALSE?
A. T (n) is O(n3/2 ) when k = 3.
B. T (n) is O(n log n) when k = 3.
C. T (n) is O(n log n) when k = 4.
D. T (n) is O(n log n) when k = 5.
E. T (n) is O(n) when k = 5.

Q 61. Consider the following recurrence relation: TIFR’15

( √
2T (⌊ n⌋) + log n if n ≥ 2
T (n) =
1 if n = 1

Which of the following statements is TRUE?

A. T (n) is O(log n).
B. T (n) is O(log n · log log n) but not O(log n).
C. T (n) is O(log3/2 n) but not O(log n · log log n).
D. T (n) is O(log2 n) but not O(log3/2 n).
E. T (n) is O(log2 n · log log n) but not O(log2 n).

60
 C Programming and Data Structures Time Complexity Page 61 of 107

Q 62. Consider the following code fragment in the C programming language when run on a non-negative TIFR’15
integer n.
int f ( int n )
{
if ( n ==0 || n ==1)
return 1;
else
return f ( n - 1) + f ( n - 2);
}

Assuming a typical implementation of the language, what is the running time of this algorithm and how
does it compare to the optimal running time for this problem?
A. This algorithm runs in polynomial time in n but the optimal running time is exponential in n.
B. This algorithm runs in exponential time in n and the optimal running time is exponential in n.
C. This algorithm runs in exponential time in n but the optimal running time is polynomial in n.
D. This algorithm runs in polynomial time in n and the optimal running time is polynomial in n.
E. The algorithm does not terminate.

Q 63. Let n = m!. Which of the following is TRUE? TIFR’16

A. m = Θ(log n/ log log n)
B. m = Ω(log n/ log log n) but not m = O(log n/ log log n)
C. m = Θ(log2 n)
D. m = Ω(log2 n) but not m = O(log2 n)
E. m = Θ(log1.5 n)

Q 64. Which of the following functions asymptotically grows the fastest as n goes to infinity? TIFR’17
√
log n log log log n log log n log log n
A. (log log n)! B. (log log n) C. (log log n) D. (log n) E. 2

Q 65. Let T (a, b) be the function with two arguments (both nonnegative integral powers of 2) defined by the TIFR’17
following recurrence:
T (a, b) = T a2 , b + T a, 2b



if a, b ≥ 2
T (a, 1) = T a2 , 1


if a ≥ 2
b


T (1, b) = T 1, 2 if b ≥ 2
T (1, 1) = 1
What is T (2r , 2s )?
2r + 2s
   
r+s
A. rs B. r + s C. D. E. 2r−s if r ≥ s, otherwise 2s−r
2r r

Q 66. You can climb up a staircase of n stairs by taking steps of one or two stairs at a time. ISI’18
1. Formulate a recurrence relation for counting an , the number of distinct ways in which you can climb
up the staircase.
2. Mention the boundary conditions for your recurrence relation.
3. Find a closed form expression for an by solving your recurrence.

Q 67. Which of the following statements is TRUE for all sufficiently large integers n? TIFR’18

61
 C Programming and Data Structures Time Complexity Page 62 of 107
√ √ √ √
log log n log log n
A. 22 < 2 log√ n < n D. n < 22 <2 log n
√ log log n
B. 2 log n < n < 22√
√ log log n √ √
log log n
C. n < 2 log n < 22 E. 2 log n
< 22 <n

Q 68. Which of the following functions, given by their recurrences, grows the fastest asymptotically? TIFR’18
A. T (n) = 4T n2 + 10n

B. T (n) = 8T n3 + 24n2

C. T (n) = 16T n4 + 10n2

1.99
D. T (n) = 25T n5 + 20 (n log n)

E. They are all asymptotically the same.

Q 69. Stirling’s approximation for n! states for some constants c1 , c2 , TIFR’19

1 1
c1 nn+ 2 e−n ≤ n! ≤ c2 nn+ 2 e−n .

What are the tightest asymptotic bounds that can be placed on n!?
1 1 1
A. n! = Ω(nn ) and n! = O(nn+ 2 ) B. n! = Θ(nn+ 2 ) C. n! = Θ(( ne )n ) D. n! = Θ(( ne )n+ 2 )
1
E. n! = Θ(nn+ 2 2−n )

Q 70. Consider the following algorithm (Note: For positive integers, p, q, p/q denotes the floor of the rational TIFR’20
p
number , assume that given p, q, p/q can be computed in one step):
q
Input: Two positive integers a, b, a ≥ b.
Output: A positive integers g.
while (b >0) {
x = a - ( a / b )* b ;
a = b;
b = x;
}
g = a;

Suppose K is an upper bound on a. How many iterations does the above algorithm take in the worst
case?
A. Θ(log K) B. Θ(K) C. Θ(K log K) D. Θ(K 2 ) E. Θ(2K )

Q 71. Among the following asymptotic expressions, which of these functions grows the slowest (as a function TIFR’20
of n) asymptotically?
√ 2 √ √
log log n
A. 2log n B. n10 C. ( log n)log n D. (log n) log n E. 22

Q 72. Consider the following algorithm for computing the factorial of a positive integer TIFR’22
prod ← 1
for i from 1 to n
prod ← prod × i
output prod

Assume that the number of bit operations required to multiply a k-bit positive integer with an l-bit
positive integer is at least Ω(k + l) and at most O(kl). Then, the number of bit operations required by
this algorithm is
A. O(n)
B. O(n log n) but ω(n)


C. O n2 but ω(n log n)

62
 C Programming and Data Structures Time Complexity Page 63 of 107

D. O n3 but ω n2
E. None of the above
Q 73. Let f : N → N and g : N → N be functions over the set N of natural numbers. We will say: CMI’23
• f (n) = O(g(n)) if there exist natural numbers c and x0 such that f (n) ≤ cg(n) for all n ≥ x0
• f (n) = 2O(g(n)) if there exist natural numbers c and x0 such that f (n) ≤ 2(cg(n)) for all n ≥ x0 .
Consider the following statements
(I) 3n = O(2n )
(II) 3n = 2O(n)

A. Both (I) and (II) are true C. (I) is false and (II) is true
B. (I) is true and (II) is false D. Both (I) and (II) are false

Q 74. What is the solution to the following recurrence? TIFR’23

(
1 if n ≤ 10.
T (n) = √ √
n.T ( n) + n if n > 10.

A. T (n) = Θ(n2 ) D. T (n) = Θ(n log log n)

B. T (n) = Θ(n log n)
√
C. T (n) = Θ(n log n) E. None of the above

Q 75. Consider the following two recurrence relations: CMI’24

• T1 (n) = T1 ( n2 ) + T1 ( n3 ) + Θ(n), T1 (1) = 2
• T2 (n) = T2 ( 2n n
3 ) + T 2( 3 ) + Θ(n), T2 (1) = 2

Which of the following statements is true?

A. T1 (n) = Θ(n) and T2 (n) = Θ(n)
B. T1 (n) = Θ(n log n) and T2 (n) = Θ(n log n)
C. T1 (n) = Θ(n) and T2 (n) = Θ(n log n)
D. T1 (n) = Θ(n log n) and T2 (n) = Θ(n)

Q 76. Express the output f(n) of the following code fragment as a mathematical function of n (where n is a ISI’24
natural number).
f ( n ){
if n is 0
return 0;
return 2 * f (n -1) + 1;
}

A. f (n) = 2n+1 − 2 C. f (n) = n! − 1

B. f (n) = 2n − 1 D. f (n) = n2n−1

Q 77. What is the solution to the following recursion? TIFR’25

T (n) = T ( n2 ) + T ( n3 ) + T ( n6 ) + O(n),
T (n) = 5∀n < 100.
A. T (n) = Θ(n log n)

63
C Programming and Data Structures Time Complexity Page 64 of 107

B. T (n) = Θ(n log2 n)

C. T (n) = Θ(n2 )
D. T (n) = Θ(n2 log n)
E. T (n) = 2Θ(n)

64
 C Programming and Data Structures Arrays Page 65 of 107

Chapter 5 Arrays
Q 1. In a compact single dimensional array representation for lower triangular matrices (i.e all the elements 1994
above the diagonal are zero) of size n × n, non-zero elements, (i.e elements of lower triangle) of each row
are stored one after another, starting from the first row, the index of the (i, j)th element of the lower
triangular matrix in this new representation is:
i(i−1) j(j−1)
A. i + j B. i + j − 1 C. (j − 1) + 2 D. i + 2

Q 2. Let A be a two-dimensional array declared as follows: 1998

A: array [1 . . . 10][1 . . . 15] of integer;
Assuming that each integer takes one memory locations the array is stored in row-major order and the
first element of the array is stored at location 100, what is the address of element A[i][j]?
A. 15i + j + 84 B. 15j + i + 84 C. 10i + j + 89 D. 10j + i + 89
Q 3. Consider the following declaration of a two-dimensional array in C: 2002

char a[100][100];

Assuming that the main memory is byte addressable and that the array is stored starting from address
0, the address of a[40][50] is
A. 4040 B. 4050 C. 5040 D. 5050

Q 4. A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any 2015Set2
unfilled entries are marked with ∞, and hence there cannot be any entry to the right of ∞, or below a
∞. The following Young tableau consists of unique entries.

1 2 5 14
3 4 6 23
10 12 18 25
31 ∞ ∞ ∞

When an element is removed from a Young tableau, other elements should be moved into its place
so that the resulting table is still a Young tableau (unfilled entries may be filled with a ∞). The
minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is
.

Q 5. Suppose you are given an array s[1 . . . n] and a procedure reverse(s, i, j) which reverses the order 2000
of elements in s between positions i and j (both inclusive). What does the following sequence do, where
1 ≤ k ≤ n:
reverse (s , 1 , k );
reverse (s , k +1 , n );
reverse (s , 1 , n );

A. Rotates s left by k positions C. Reverses all elements of s

B. Leaves s unchanged D. None of the above

Q 6. Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to 2000
determine if there are two elements with sum less than 1000 in s. Which of the following statements is
true?

n
A. t(n) is O(1) C. n log2 n ≤ t(n) < 2
n
B. n ≤ t(n) ≤ n log2 n D. t(n) = 2

65
 C Programming and Data Structures Arrays Page 66 of 107

Q 7. Let a be an array containing n integers in increasing order. The following algorithm determines whether 2005IT
there are two distinct numbers in the array whose difference is a specified number S > 0.
i = 0; j = 1;
while ( j < n ){
if ( E ) j ++;
else if ( a [ j ] - a [ i ] == S ) break ;
else i ++;
}
if ( j < n ) printf ( " yes " ) else printf ( " no " );

Choose the correct expression for E.

A. a[j] − a[i] > S B. a[j] − a[i] < S C. a[i] − a[j] < S D. a[i] − a[j] > S

Q 8. A program P reads in 500 integers in the range [0, 100] representing the scores of 500 students. It then 2005
prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

A. An array of 50 numbers C. An array of 500 numbers

B. An array of 100 numbers D. A dynamically allocated array of 550 numbers

Q 9. Suppose we want to arrange the n numbers stored in an array such that all negative values occur before 1999
all positive ones. Minimum number of exchanges required in worst case is:
A. n − 1 B. n C. n + 1 D. None of the above

Q 10. An element in an array X is called a leader if it is greater than all elements to the right of it in X. The 2006
best algorithm to find all leader in an array
A. Solves it in linear time using a left to right pass of the array
B. Solves it in linear time using a right to left pass of the array
C. Solves it using divide and conquer in time Θ(n log n)
D. Solves it in time θ(n2 )

Q 11. Consider the following C-function in which a[n] and b[n] are two sorted integer arrays and c[n + m] be 2006
another array.
void xyz ( int a [] , int b [] , int c []){
int i ,j , k ;
i = j = k =0;
while (( i < n ) && (j < m ))
if ( a [ i ] < b [ j ]) c [ k ++] = a [ i ++];
else c [ k ++] = b [ j ++];
}

Which of the following condition(s) hold(s) after the termination of the while loop?
i. j < m, k = n + j − 1 and a[n − 1] < b[j] if i = n
ii. i < n, k = m + i − 1 and b[m − 1] ≤ a[i] if j = m
A. only (i) B. only (ii) C. either (i) or (ii) but not both D. neither (i) nor (ii)

Q 12. Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of 2003
sequences, B and C are there such that
• each is sorted in ascending order,
• B has 5 and C has 3 elements, and
• the result of merging B and C gives A

66
 C Programming and Data Structures Arrays Page 67 of 107

A. 2 B. 30 C. 56 D. 256
Q 13. Let A[1 . . . n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time 2004
complexity is Θ(m). Consider the following program fragment written in a C like language:
counter = 0;
for ( i =1; i <= n ; i ++)
{
if ( A [ i ] == 1) counter ++;
else { f ( counter ); counter = 0;}
}

The complexity of this program fragment is

A. Ω(n2 ) B. Ω(n log n) and O(n2 ) C. Θ(n) D. o(n)

Q 14. Consider the following C function in which size is the number of elements in the array E: 2014Set1
int MyX ( int *E , unsigned int size )
{
int Y = 0;
int Z ;
int i , j , k ;

for ( i = 0; i < size ; i ++)

Y = Y + E [ i ];

for ( i =0; i < size ; i ++)

for ( j = i ; j < size ; j ++)
{
Z = 0;
for ( k = i ; k <= j ; k ++)
Z = Z + E [ k ];
if ( Z > Y )
Y = Z;
}
return Y ;
}

The value returned by the function MyX is the

A. maximum possible sum of elements in any sub-array of array E.
B. maximum element in any sub-array of array E.
C. sum of the maximum elements in all possible sub-arrays of array E.
D. the sum of all the elements in the array E.

Q 15. Suppose c = ⟨c[0], . . . , c[k − 1]⟩ is an array of length k, where all the entries are from the set {0, 1}. For 2015Set3
any positive integers a and n, consider the following pseudocode.
DOSOMETHING (c , a , n )

z ← 1
for i ← 0 to k -1
do z ← z 2 mod n
if c [ i ]=1
then z ← ( z × a ) mod n
return z

If k = 4, c = ⟨1, 0, 1, 1⟩, a = 2, and n = 8, then the output of DOSOMETHING(c, a, n) is .

67
 C Programming and Data Structures Arrays Page 68 of 107

Q 16. The following function computes the maximum value contained in an integer array p[] of size n(n >= 1). 2016Set1
int max ( int *p , int n ) {
int a = 0 , b = n -1;

while ( __________ ) {
if ( p [ a ] <= p [ b ]) { a = a +1;}
else { b = b -1;}
}
return p [ a ];
}

The missing loop condition is:

A. a!=n B. b!=0 C. b>(a+1) D. b!= a
Q 17. Consider the following ANSI C function: 2021Set1
int SimpleFunction ( int Y [] , int n , int x )
{
int total = Y [0] , loopIndex ;
for ( loopIndex = 1; loopIndex <= n -1; loopIndex ++)
total = x * total + Y [ loopIndex ];
return total ;
}

Let Z be an array of 10 elements with Z[i] = 1, for all i such that 0 ≤ i ≤ 9. The value returned by
SimpleFunction(Z,10,2) is .

Q 18. In the following C program fragment j, k, n and and T woLog n are integer variables, and A is an array 2003
of integers. The variable n is initialized to an integer ≥ 3, and T woLog n is initialized to the value of
2∗ ⌈log2 (n)⌉.
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 numbers printed by this program fragment is

A. {m | m ≤ n, (∃i) [m = i!]} C. {m | m ≤ n, m is prime}

  
B. m | m ≤ n, (∃i) m = i2 D. {}

5.1 More Questions

Q 19. Consider an array A[1...n]. It consists of a permutation of numbers 1....n. Now compute another array TIFR’11
B[1...n] as follows: B[A[i]] := i for all i. Which of the following is true?
A. B will be a sorted array.
B. B is a permutation of array A.
C. Doing the same transformation twice will not give the same array.
D. B is not a permutation of array A.
E. None of the above.

68
 C Programming and Data Structures Arrays Page 69 of 107

Q 20. The first n cells of an array L contain positive integers sorted in decreasing order, and the remaining TIFR’11
m − n cells all contain 0. Then, given an integer x, in how many comparisons can one find the position
of x in L?
A. At least n comparisons are necessary in the worst case.
B. At least log m comparisons are necessary in the worst case.
C. O(log(m − n)) comparisons suffice.
D. O(log n) comparisons suffice.
E. O(log(m/n)) comparisons suffice.

Q 21. Consider the following program modifying an n × n square matrix A: TIFR’17

for i =1 to n :
for j =1 to n :
temp = A [ i ][ j ]+10
A [ i ][ j ]= A [ j ][ i ]
A [ j ][ i ]= temp -10
end for
end for

Which of the following statements about the contents of the matrix A at the end of this program must
be TRUE ?
A. the new A is the transpose of the old A
B. all elements above the diagonal have their values increased by 10 and all the values below have their
values decreased by 10
C. all elements above the diagonal have their values decreased by 10 and all the values below have their
values increased by 10
D. A is symmetric, that is, A[i][j] = A[j][i] for all 1 ≤ i, j ≤ n
E. A remains unchanged

Q 22. Consider an array of length n consisting only of positive and negative integers. Design an algorithm to ISI’18
rearrange the array so that all the negative integers appear before all the positive integers, using O(n)
time and only a constant amount of extra space.

Q 23. Let A[0...n − 1] and B[0...n − 1] be two arrays containing n real numbers such that A[k] ≤ A[k + 1] and ISI’22
B[k] ≤ B[k + 1] for all k ∈ {0, 1, ..., n − 2}. Design an efficient
√ algorithm to find whether there exists
any k ∈ {0, 1, ..., n − 1} such that A[k] + iB[k], where i = −1, forms a complex root of the equation
x2 + 2cx + c2 + d2 = 0 and c and d are real numbers. State and justify the time complexity of your
algorithm.

69
 C Programming and Data Structures Stacks Page 70 of 107

Chapter 6 Stacks

6.1 Introduction
Q 1. The following sequence of operations is performed on a stack: 1991
PUSH (10), PUSH (20), POP, PUSH (10), PUSH (20), POP, POP, POP, PUSH (20), POP.
The sequence of values popped out is:
A. 20, 10, 20, 10, 20 B. 20, 20, 10, 10, 20
C. 10, 20, 20, 10, 20 D. 20, 20, 10, 20, 10
E. None of the above
Q 2. Which of the following permutation can be obtained in the output (in the same order) using a stack 1994
assuming that the input is the sequence 1, 2, 3, 4, 5 in that order?
A. 3, 4, 5, 1, 2 B. 3, 4, 5, 2, 1 C. 1, 5, 2, 3, 4 D. 5, 4, 3, 1, 2

Q 3. A program attempts to generate as many permutations as possible of the string ‘abcd’ by pushing the 2004IT
characters a, b, c, d in the same order onto a stack, but it may pop off the top character at any time.
Which one of the following strings CANNOT be generated using this program?
A. abcd B. dcba C. cbad D. cabd
Q 4. Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of 2 elements. S1 already 2024Set2
has 4 elements: 100, 200, 300, and 400, whereas S2 is empty, as shown below.

400 (Top)
300
200
100
Table 2: *
Table 1: * Stack S2
Stack S1

Only the following three operations are available:

PushToS2: Pop the top element from S1 and push it on S2.
PushToS1: Pop the top element from S2 and push it on S1.
GenerateOutput: Pop the top element from S1 and output it to the user.

Note that the pop operation is not allowed on an empty stack and the push operation is not allowed on
a full stack.
Which of the following output sequences can be generated by using the above operations?

A. 100, 200, 400, 300 C. 400, 200, 100, 300

B. 200, 300, 400, 100 D. 300, 200, 400, 100

Q 5. Consider the following pseudocode. 2025DA

Create empty stack S
Set x =0 , flag =0 , sum =0
Push x onto S
while ( S is not empty ){
if ( flag equals 0){
Set x = x +1
Push x onto S }
if ( x equals 8):
Set flag =1

70
 C Programming and Data Structures Stacks Page 71 of 107

if ( flag equals 1){

x = Pop ( S )
if ( x is odd ):
Pop ( S )
Set sum = sum + x }
}
Output sum

The value of sum output by a program executing the above pseudocode is . (Answer in
integer)

Q 6. Consider the C program below 2015Set2

# include < stdio .h >
int *A , stkTop ;
int stkFunc ( int opcode , int val )
{
static int size =0 , stkTop =0;
switch ( opcode ) {
case -1: size = val ; break ;
case 0: if ( stkTop < size ) A [ stkTop ++]= val ; break ;
default : if ( stkTop ) return A [ - - stkTop ];
}
return -1;
}
int main ()
{
int B [20]; A = B ; stkTop = -1;
stkFunc ( -1 , 10);
stkFunc (0 , 5);
stkFunc (0 , 10);
printf ( " % d \ n " , stkFunc (1 , 0) + stkFunc (1 , 0));
}

The value printed by the above program is .

Q 7. A function f defined on stacks of integers satisfies the following properties f (ϕ) = 0 and f (push(S, i)) = 2005IT
max(f (S), 0) + i for all stacks S and integers i.
If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?
A. 6 B. 4 C. 3 D. 2
Q 8. Let S be a stack of size n ≥ 1. Starting with the empty stack, suppose we Push the first n natural 2003
numbers in sequence, and then perform n Pop operations. Assume that Push and Pop operations take
X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the
next operation. For m ≥ 1, define the stack-life of m as the time elapsed from the end of Push(m) to the
start of the Pop operation that removes m from S. The average stack-life of an element of this stack is
A. n(X + Y ) B. 3Y + 2X C. n(X + Y ) − X D. Y + 2X

Q 9. A single array A[1 . . . MAXSIZE] is used to implement two stacks. The two stacks grow from opposite 2004
ends of the array. Variables top1 and top2 (top1 < top2) point to the location of the topmost element in
each of the stacks. If the space is to be used efficiently, the condition for ‘stack full’ is
A. (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2 + 1)
B. top1 + top2 = MAXSIZE
C. (top1 = MAXSIZE/2) or (top2 = MAXSIZE)
D. top1 = top2 − 1

71
 C Programming and Data Structures Stacks Page 72 of 107

6.2 Infix and Postfix Expressions

Q 10. The postfix expression for the infix expression A + B ∗ (C + D)/F + D ∗ E is: 1995

A. AB + CD + ∗F/D + E∗ C. A ∗ B + CD/F ∗ DE + +
B. ABCD + ∗F/DE ∗ ++ D. A + ∗BCD/F ∗ DE + +

Q 11. Compute the postfix equivalent of the following infix expression. 1998
3 ∗ log(x + 1) − a/2

Q 12. The following post fix expression, containing single digit operands and arithmetic operators + and ∗, is 2000
evaluated using a stack.
5 2 ∗ 3 4 + 5 2 ∗ ∗+
Show the contents of the stack
(i) After evaluating 5 2 ∗ 3 4+
(ii) After evaluating 5 2 ∗ 3 4 + 5 2
(iii) At the end of evaluation

Q 13. Assume that the operators +, −, × are left associative and ˆ is right associative. The order of precedence 2004
(from highest to lowest) is ˆ, ×, +, −. The postfix expression corresponding to the infix expression
a + b × c − dˆeˆf is

A. abc × +def ˆˆ− C. ab + c × d − eˆf ˆ

B. abc × +deˆf ˆ− D. − + a × bcˆˆdef

Q 14. The following postfix expression with single digit operands is evaluated using a stack: 2007
8 2 3 ˆ/ 2 3 ∗ +5 1 ∗ −
Note that ˆ is the exponentiation operator. The top two elements of the stack after the first ∗ is evaluated
are
A. 6, 1 B. 5, 7 C. 3, 2 D. 1, 5

Q 15. The result evaluating the postfix expression 10 5 + 60 6/ ∗ 8− is 2015Set3

A. 284 B. 213 C. 142 D. 71
Q 16. Consider the following C program: 2007IT
# include < stdio .h >
# define EOF -1
void push ( int ); /* push the argument on the stack */
int pop ( void ); /* pop the top of the stack */
void flagError ();

int main ()
{
int c , m , n , r ;
while (( c = getchar ()) != EOF )
{
if ( isdigit ( c ) )
push ( c );
else if (( c == ‘+ ’) || ( c == ‘* ’ ))
{
m = pop ();
n = pop ();

72
 C Programming and Data Structures Stacks Page 73 of 107

r = ( c == ‘+ ’) ? n + m : n * m ;
push ( r );
}
else if ( c != ‘ ’)
flagError ();
}
printf ( " % c " , pop ());
}

What is the output of the program for the following input?

5 2 ∗ 3 3 2 + ∗+
A. 15 B. 25 C. 30 D. 150
Q 17. Which of the following is essential for converting an infix expression to the postfix form efficiently? 1997

A. An operator stack C. An operand stack and an operator stack

B. An operand stack D. A parse tree

Q 18. The best data structure to check whether an arithmetic expression has balanced parenthesis is a 2004
A. Queue B. Stack C. Tree D. List

Q 19. (MSQ) Consider a stack data structure into which we can PUSH and POP records. Assume that each 2025Set2
record pushed in the stack has a positive integer key and that all keys are distinct.
We wish to augment the stack data structure with an O(1) time MIN operation that returns a pointer
to the record with smallest key present in the stack
1. without deleting the corresponding record, and
2. without increasing the complexities of the standard stack operations.
Which one or more of the following approach(es) can achieve it?
A. Keep with every record in the stack, a pointer to the record with the smallest key below it.
B. Keep a pointer to the record with the smallest key in the stack.
C. Keep an auxiliary array in which the key values of the records in the stack are maintained in sorted
order.
D. Keep a Min-Heap in which the key values of the records in the stack are maintained.

6.3 More Questions

Q 20. We have an implementation that supports the following operations on a stack (in the instructions below, TIFR’17
s is the name of the stack).
isempty(s): returns True if s is empty, and False otherwise.
top(s): returns the top element of the stack, but does not pop the stack; returns null if the stack is empty.
push(s, x): places x on top of the stack.
pop(s): pops the stack; does nothing if s is empty.
Consider the following code:
pop_ray_pop ( x ):
s = empty
for i =1 to length ( x ):
if ( x [ i ] == ‘( ’ ):
push (s , x [ i ])
else :
while ( top ( s )== ‘( ’ ):

73
C Programming and Data Structures Stacks Page 74 of 107

pop ( s )
end while
push (s , ‘) ’)
end if
end for
while not isempty ( s ):
print top ( s )
pop ( s )
end while

What is the output of this program when

pop ray pop(“(((()((())((((′′ )
is executed?
A. (((( B. )))(((( C. ))) D. (((())) E. ()()

74
 C Programming and Data Structures Queues Page 75 of 107

Chapter 7 Queues
Q 1. Consider the following sequence of operations on an empty stack. 2021Set1

push(54); push(52); pop(); push(55); push(62); s = pop();

Consider the following sequence of operations on an empty queue.

enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue();

The value of s+q is .

Q 2. Consider a sequence a of elements a0 = 1, a1 = 5, a2 = 7, a3 = 8, a4 = 9, and a5 = 2. The following 2023

operations are performed on a stack S and a queue Q, both of which are initially empty.

I: push the elements of a from a0 to a5 in that order into S.

II: enqueue the elements of a from a0 to a5 in that order into Q.
III: pop an element from S.
IV: dequeue an element from Q.
V: pop an element from S.
VI: dequeue an element from Q.
VII: dequeue an element from Q and push the same element into S.
VIII: Repeat operation VII three times.
IX: pop an element from S.
X: pop an element from S.
The top element of S after executing the above operations is .

Q 3. The fundamental operations in a double-ended queue D are: 2024DA

insertFirst(e) – Insert a new element e at the beginning of D.
insertLast(e) – Insert a new element e at the end of D.
removeFirst() – Remove and return the first element of D.
removeLast() – Remove and return the last element of D.
In an empty double-ended queue, the following operations are performed:
insertFirst(10)
insertLast(32)
a ← removeFirst()
insertLast(28)
insertLast(17)
a ← removeFirst()
a ← removeLast()
The value of a is .
Q 4. Suppose you are given an implementation of a queue of integers. The operations that can be performed 2007IT
on the queue are:
i. isEmpty(Q) - returns true if the queue is empty, false otherwise.
ii. delete(Q) - deletes the element at the front of the queue and returns its value.
iii. insert(Q,i) - inserts the integer i at the rear of the queue.
Consider the following function:

75
 C Programming and Data Structures Queues Page 76 of 107

void f ( queue Q ) {
int i ;
if (! isEmpty ( Q )) {
i = delete ( Q );
f ( Q );
insert (Q , i );
}
}

What operation is performed by the above function f?

A. Leaves the queue Q unchanged
B. Reverses the order of the elements in the queue Q
C. Deletes the element at the front of the queue Q and inserts it at the rear keeping the other elements
in the same order
D. Empties the queue Q
Q 5. Consider the queues Q1 containing four elements and Q2 containing none (shown as the Initial State in 2022
the figure). The only operations allowed on these two queues are Enqueue(Q,element) and Dequeue(Q).
The minimum number of Enqueue operations on Q1 required to place the elements of Q1 in Q2 in reverse
order (shown as the Final State in the figure) without using any additional storage is .

Q 6. Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the 2016Set1
element at the head of the queue Q without removing it from Q. Similarly T op(S) returns the element
at the top of S without removing it from S. Consider the algorithm given below.

while Q is not Empty do

if S is Empty OR Top(S) ≤ Head (Q) then
x:= Dequeue (Q);
Push (S, x);
else
x:= Pop(S);
Enqueue (Q, x);
end
end

The maximum possible number of iterations of the while loop in the algorithm is .
Q 7. Suppose a circular queue of capacity (n − 1) elements is implemented with an array of n elements. 2012
Assume that the insertion and deletion operations are carried out using REAR and FRONT as array
index variables, respectively. Initially, REAR=FRONT=0. The conditions to detect queue full and queue
empty are

76
 C Programming and Data Structures Queues Page 77 of 107

A. full: (REAR+1)mod n == FRONT C. full: REAR == FRONT

empty: REAR == FRONT empty: (REAR+1)mod n == FRONT
B. full: (REAR+1)mod n == FRONT D. full: (FRONT+1)mod n == REAR
empty: (FRONT+1)mod n == REAR empty: REAR == FRONT

Q 8. What is the minimum number of stacks of size n required to implement a queue of size n? 2001
A. One B. Two C. Three D. Four
Q 9. Suppose a stack implementation supports, in addition to PUSH and POP, an operation REVERSE, 2000
which reverses the order of the elements on the stack. To implement a queue using the above stack
implementation, show how to implement ENQUEUE using a single operation and DEQUEUE using a
sequence of 3 operations.

Q 10. Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements 2014Set2
on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is
TRUE (with respect to this modified stack)?
A. A queue cannot be implemented using this stack.
B. A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a
sequence of two instructions.
C. A queue can be implemented where ENQUEUE takes a sequence of three instructions and DE-
QUEUE takes a single instruction.
D. A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.
Q 11. An implementation of queue Q, using stacks S1 and S2 is given below: 2006
void insert (Q , x ) {
push ( S1 , x );
}
void delete ( Q ) {
if ( stack - empty ( S2 )) then
if ( stack - empty ( S1 )) then {
print ( " Q is empty " );
return ;
}
else while (!( stack - empty ( S1 ))){
x = pop ( S1 );
push ( S2 , x );
}
x = pop ( S2 );
}

Let n insert and m(≤ n) delete operations be performed in an arbitrary order on an empty queue Q.
Let x and y be the number of push and pop operations performed respectively in the process. Which
one of the following is true for all m and n?

A. n + m ≤ x < 2n and 2m ≤ y ≤ n + m C. 2m ≤ x < 2n and 2m ≤ y ≤ n + m

B. n + m ≤ x < 2n and 2m ≤ y ≤ 2n D. 2m ≤ x < 2n and 2m ≤ y ≤ 2n

Q 12. A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed 2016Set1
efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the
queue)?
A. Both operations can be performed in O(1) time
B. At most one operation can be performed in O(1) time but the worst case time for the operation will
be Ω(n)

77
 C Programming and Data Structures Queues Page 78 of 107

C. The worst case time complexity for both operations will be Ω(n)
D. Worst case time complexity for both operations will be Ω(log n)

Q 13. Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a 2013
global parameter.
MultiDequeue ( Q ){
m = k
while ( Q is not empty ) and ( m > 0) {
Dequeue ( Q )
m = m - 1
}
}

What is the worst case time complexity of a sequence of n queue operations on an initially empty queue?
A. Θ(n) B. Θ(n + k) C. Θ(nk) D. Θ(n2 )

Q 14. A queue Q containing n items and an empty stack S are given. It is required to transfer all the items 1994
from the queue to the stack, so that the item at the front of queue is on the TOP of the stack, and the
order of all other items are preserved. Show how this can be done in O(n) time using only a constant
amount of additional storage. Note that the only operations which can be performed on the queue and
stack are Delete, Insert, Push and Pop. Do not assume any implementation of the queue or stack.

78
 C Programming and Data Structures Linked Lists Page 79 of 107

Chapter 8 Linked Lists

Q 1. Let p be a pointer as shown in the figure in a singly linked list. 1998

What do the following assignment statements achieve?

q := p -> next
p -> next := q -> next
q -> next :=( q -> next ) -> next
( p -> next ) -> next := q

Q 2. The following C function takes a singly linked list of integers as a parameter and rearranges the elements 2005IT
of the list. The list is represented as pointer to structure. The function is called with the list containing
integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function
completes?
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

Q 3. The following C function takes a single-linked list of integers as a parameter and rearranges the elements 2008
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 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;
}
}

79
 C Programming and Data Structures Linked Lists Page 80 of 107

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

Q 4. Let LIST be a datatype for an implementation of linked list defined as follows: 2025Set1
typedef struct list {
int data ;
struct list * next ;
} LIST ;

Suppose a program has created two linked lists, L1 and L2, whose contents are given in the figure below
(code for creating L1 and L2 is not provided here). L1 contains 9 nodes, and L2 contains 7 nodes.
Consider the following C program segment that modifies the list L1. The number of nodes that will be
there in L1 after the execution of the code segment is . (Answer in integer)

int find ( int query , LIST * list ) {

while ( list != NULL ){
if ( list - > data == query ) return 1;
list = list - > next ;
}
return 0;
}
int main () {
... ... ...
ptr1 = L1 ; ptr2 = L2 ;
while ( ptr1 - > next != NULL ){
query = ptr1 - > next - > data ;
if ( find ( query , L2 ))
ptr1 - > next = ptr1 - > next - > next ;
else ptr1 = ptr1 - > next ;
}
... ... ...
return 0;
}

Q 5. Consider a singly linked list having n nodes. The data items d1 , d2 , . . . dn are stored in these n nodes. 1993
Let X be a pointer to the j th node (1 ≤ j ≤ n) in which dj is stored. A new data item d stored in node
with address Y is to be inserted. Give an algorithm to insert d into the list to obtain a list having items
d1 , d2 , . . . , dj−1 , d, dj , . . . , dn in order without using the header.

Q 6. Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the 2004IT
worst-case time complexity of the best-known algorithm to delete the node x from the list?
A. O(n) B. O(log2 n) C. O(log n) D. O(1)

Q 7. Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and 2023
a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a
doubly-linked list given a pointer to the node and a pointer to the head of the list.
Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE
about the worst-case time complexity of SLLdel and DLLdel?
A. SLLdel is O(1) and DLLdel is O(n)
B. Both SLLdel and DLLdel are O(log(n))

80
 C Programming and Data Structures Linked Lists Page 81 of 107

C. Both SLLdel and DLLdel are O(1)

D. SLLdel is O(n) and DLLdel is O(1)

Q 8. The following C function takes a singly-linked list as input argument. It modifies the list by moving the 2010
last element to the front of the list and returns the modified list. Some part of the code is left blank.
typedef struct node
{
int value ;
struct node * next ;
} node ;
Node * move_to - front ( Node * head )
{
Node *p , * q ;
if (( head == NULL ) || ( head -> next == NULL ))
return head ;
q = NULL ;
p = head ;
while (p - > next != NULL )
{
q = p;
p = p -> next ;
}
_______________

return head ;
}

Choose the correct alternative to replace the blank line.

A. q=NULL; p -> next = head; head = p
B. q -> next = NULL; head = p; p -> next = head
C. head = p; p -> next =q; q -> next = NULL
D. q -> next = NULL; p -> next = head; head = p

Q 9. Consider the C code fragment given below. 2017Set1

typedef struct node {
int data ;
node * next ;
} node ;

void join ( node * m , node * n ) {

node * p = n ;
while (p - > next != NULL ) {
p = p - > next ;
}
p - > next = m ;
}

Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will
A. append list m to the end of list n for all inputs.
B. either cause a null pointer dereference or append list m to the end of list n.
C. cause a null pointer dereference for all inputs.
D. append list n to the end of list m for all inputs.

81
 C Programming and Data Structures Linked Lists Page 82 of 107

Q 10. Consider the function f defined below. 2003

struct item {
int data ;
struct item * next ;
};
int f ( struct item *p) {
return (( p == NULL ) || (p - > next == NULL )||
(( p - > data <= p -> next -> data ) && f (p - > next )));
}

For a given linked list p, the function f returns 1 if and only if

A. the list is empty or has exactly one element
B. the elements in the list are sorted in non-decreasing order of data value
C. the elements in the list are sorted in non-increasing order of data value
D. not all elements in the list have the same data value

Q 11. Consider the following piece of C code fragment that removes duplicates from an ordered list of integers. 1997
Node * remove - duplicates ( Node * head , int * j )
{
Node * t1 , * t2 ; * j =0;
t1 = head ;
if ( t1 ! = NULL )
t2 = t1 -> next ;
else return head ;
* j = 1;
if ( t2 == NULL ) return head ;
while ( t2 != NULL )
{
if ( t1 . val != t2 . val ) - - - - - - - - - - - - - - - - > ( S1 )
{
(* j )++;
t1 -> next = t2 ;
t1 = t2 ; - - - - - - - - - - - - - - - - - > ( S2 )
}
t2 = t2 -> next ;
}
t1 -> next = NULL ;
return head ;
}

Assume the list contains n elements n ≥ 2) in the following questions.

(i) How many times is the comparison in statement S1 made?
(ii) What is the minimum and the maximum number of times statements marked S2 get executed?
(iii) What is the significance of the value in the integer pointed to by j when the function completes?

Q 12. Consider the following ANSI C program. 2021Set2

# include < stdio .h >
# include < stdlib .h >
struct Node {
int value ;
struct Node * next ;};
int main () {
struct Node * boxE , * head , * boxN ; int index =0;

82
 C Programming and Data Structures Linked Lists Page 83 of 107

boxE = head = ( struct Node *) malloc ( sizeof ( struct Node ));

head → value = index ;
for ( index =1; index <=3; index ++){
boxN = ( struct Node *) malloc ( sizeof ( struct Node ));
boxE → next = boxN ;
boxN → value = index ;
boxE = boxN ; }
for ( index =0; index <=3; index ++) {
printf ( " Value at index % d is % d \ n " , index , head → value );
head = head → next ;
printf ( " Value at index % d is % d \ n " , index +1 , head → value );
}
}
Which one of the following statements below is correct about the program?
A. Upon execution, the program creates a linked-list of five nodes.
B. Upon execution, the program goes into an infinite loop.
C. It has a missing return which will be reported as an error by the compiler.
D. It dereferences an uninitialized pointer that may result in a run-time error.
Q 13. In a circular linked list organization, insertion of a record involves modification of 1987
A. One pointer B. Two pointer C. Three pointers D. No pointer
Q 14. A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a 2018
tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let enqueue be
implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node
from the tail.

Which one of the following is the time complexity of the most time-efficient implementation of enqueue
and dequeue, respectively, for this data structure?
A. Θ(1), Θ(1) B. Θ(1), Θ(n) C. Θ(n), Θ(1) D. Θ(n), Θ(n)
Q 15. A circularly linked list is used to represent a queue. A single variable p is used to access the queue. To 2004
which node should p point such that both the operations enQueue and deQueue can be performed in
constant time?

A. rear node B. front node C. not possible with a single pointer D. node next to front
Q 16. A circular queue has been implemented using a singly linked list where each node consists of a value 2017Set2
and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and
REAR pointing to the front node and the rear node of the queue, respectively. Which of the following
statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be
performed in O(1) time?

83
 C Programming and Data Structures Linked Lists Page 84 of 107

I. Next pointer of front node points to the rear node.

II. Next pointer of rear node points to the front node.
A. I only B. II only C. Both I and II D. Neither I nor II
Q 17. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given 2002
element is
n
A. log2 n B. 2 C. log2 n − 1 D. n

Q 18. The concatenation of two lists is to be performed on O(1) time. Which of the following implementations 1997
of a list should be used?

A. singly linked list C. circular doubly linked list

B. doubly linked list D. array implementation of list

Q 19. What is the worst case time complexity of inserting n elements into an empty linked list, if the linked 2020
list needs to be maintained in sorted order?
A. Θ(n) B. Θ(n log n) C. Θ(n2 ) D. Θ(1)

Q 20. Consider the problem of reversing a singly linked list. To take an example, given the linked list below, 2022

the reversed linked list should look like

Which one of the following statements is TRUE about the time complexity of algorithms that solve the
above problem in O(1) space?
A. The best algorithm for the problem takes Θ(n) time in the worst case.
B. The best algorithm for the problem takes Θ(n log n) time in the worst case.
C. The best algorithm for the problem takes Θ(n2 ) time in the worst case.
D. It is not possible to reverse a singly linked list in O(1) space.

Q 21. N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the 2016Set2
record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the
operation is to be performed.
An algorithm performs the following operations on the list in this order: Θ (N ) delete, O(log N ) insert,
O(log N ) find, and Θ(N ) decrease-key. What is the time complexity of all these operations put
together?
A. O(log2 N )


B. O(N ) C. O(N 2 ) D. Θ N 2 log N

Q 22. Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations 2004
among union, intersection, membership, and cardinality will be the slowest?
A. union only B. intersection, membership C. membership, cardinality D. union, intersection

8.1 More Questions

Q 23. Consider a linked list containing n nodes, where each node contains two pointers ptr1 and ptr2. For ISI’15
each node, ptr1 points to the next node of the list. Describe how pointer ptr2 should be set up for each
node so that you will be able to locate the i-th node from the start node in the list traversing no more
than [log i] + [i/2]

84
 C Programming and Data Structures Linked Lists Page 85 of 107

Q 24. Let L be a singly-linked list X and Y be additional pointer variables such that X points to the first TIFR’21
element of L and Y points to the last element of L. Which of the following operations cannot be done
in time that is bound above by a constant?
A. Delete the first element of L.
B. Delete the last element of L.
C. Add an element after the last element of L.
D. Add an element before the first element of L.
E. Interchange the first two elements of L.

85
 C Programming and Data Structures Trees Page 86 of 107

Chapter 9 Trees

9.1 Basics
Q 1. Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and 2000
right subtrees, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of
the following represents a valid binary tree?
A. (1 2 (4 5 6 7)) B. (1 (2 3 4) 5 6) 7) C. (1 (2 3 4) (5 6 7)) D. (1 (2 3 NULL) (4 5))

Q 2. A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. 2006
The root is stored at X[1]. For a node stored at X[i], the left child, if any is stored in X[2i] and the
right child, if any, in X[2i + 1]. To be able to store any binary tree on n vertices the minimum size of
X should be
A. log2 n B. n C. 2n + 1 D. 2n − 1

Q 3. Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 2014Set2
1. Over all possible choices of the values at the leaves, the maximum possible value of the expression
represented by the tree is .

Q 4. The maximum number of binary trees that can be formed with three unlabelled nodes 2007
A. 1 B. 5 C. 4 D. 3
Q 5. The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum 2015Set1
number of nodes in a binary tree of height 5 are

A. 63 and 6, respectively C. 32 and 6, respectively

B. 64 and 5, respectively D. 31 and 5, respectively

Q 6. Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly 2015Set3
two children are .
Q 7. The number of rooted binary trees with n nodes is: 1990
A. Equal to the number of ways of multiplying (n + 1) matrices.
B. Equal to the number of ways of arranging n out of 2n distinct elements.
1 2n


C. Equal to (n+1) n
D. Equal to n!
Q 8. The maximum number of nodes in a binary tree of level k, k ≥ 1 is 1990
k k k−1 k−1
A. 2 + 1 B. 2 − 1 C. 2 D. 2 −1
Q 9. Consider a binary tree T in which every node has either zero or two children. Let n > 0 be the number 2025Set2
of nodes in T . Which ONE of the following is the number of nodes in T that have exactly two children?
n−2 n−1 n n+1
A. 2 B. 2 C. 2 D. 2

86
 C Programming and Data Structures Trees Page 87 of 107

Q 10. A 2-3 tree is a tree such that 1992

• all internal nodes have either 2 or 3 children
• all paths from root to the leaves have the same length.
The number of internal nodes of a 2-3 tree having 9 leaves could be
A. 4 B. 5 C. 6 D. 7
Q 11. A 3-ary tree is a tree in which every internal node has exactly three children. Use the induction to prove 1994
that the number of leaves in a 3-ary tree with n internal nodes is 2(n − 1) + 3.

Q 12. A complete n-ary tree is one in which every node has 0 or n sons. If x is the number of internal nodes 1998
of a complete n-ary tree, the number of leaves in it is given by
A. x(n − 1) + 1 B. xn − 1 C. xn + 1 D. x(n + 1)

Q 13. The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is: 2002
A. n/2 B. (n − 1)/3 C. (n − 1)/2 D. (2n + 1)/3

Q 14. In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a 2005
tree with n internal nodes is:
A. nk B. (n − 1)k + 1 C. n(k − 1) + 1 D. n(k − 1)

Q 15. Which of the following statements is false? 1998

A. A tree with n nodes has (n − 1) edges.
B. A labelled rooted binary tree can be uniquely constructed given its post-order and pre-order traversal
results.
C. A complete binary tree with n internal nodes has (n + 1) leaves.
D. The maximum number of nodes in a binary tree of height h is (2h+1 − 1).

Q 16. In a binary tree, a full node is defined to be a node with 2 children. Use the induction on the height of 1999
the binary tree to prove that the number of full nodes plus one is equal to the numbers of leaves.
Q 17. Let T (n) be the number of different binary search trees on n distinct elements. 2003
Pn
Then T (n) = k=1 T (k − 1)T (x), where x is
A. n − k + 1 B. n − k C. n − k − 1 D. n − k − 2
Q 18. In a binary tree, for every node the difference between the number of nodes in the left and right subtrees 2005IT
is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is
A. 2h−1 B. 2h−1 + 1 C. 2h − 1 D. 2h
Q 19. In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of 2006IT
degree 2 is 10. The number of leaf nodes in the binary tree is
A. 10 B. 11 C. 12 D. 15
Q 20. A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number 2007
of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41 and I = 10, what
is the value of n?
A. 3 B. 4 C. 5 D. 6
Q 21. The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum 2007
number of nodes in a binary tree of height h is:
A. 2h − 1 B. 2h−1 − 1 C. 2h+1 − 1 D. 2h+1
Q 22. In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered 2010
to be its own descendant. What is the number of nodes in the tree that have exactly one child?
(n−1)
A. 0 B. 1 C. 2 D. n − 1

87
 C Programming and Data Structures Trees Page 88 of 107

Q 23. A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is 1995
n
A. log2 n B. n − 1 C. n D. 2

Q 24. A binary tree T has 20 leaves. The number of nodes in T having two children is . 2015Set2

Q 25. Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is . 2017Set1

Q 26. Let H, I, L, and N represent height, number of internal nodes, number of leaf nodes, and the total 2024DA
number of nodes respectively in a rooted binary tree.
Which of the following statements is/are always TRUE?

A. L ≤ I + 1 C. H ≤ I ≤ 2H − 1
B. H + 1 ≤ N ≤ 2H+1 − 1 D. H ≤ L ≤ 2H−1

Q 27. Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves 2019
a and b of T are chosen uniformly and independently at random. The expected value of the distance
between a and b in T (ie., the number of edges in the unique path between a and b) is (rounded off to 2
decimal places) .

9.2 Tree Traversal

Q 28. Construct a binary tree whose preorder traversal is K L N M P R Q S T and inorder traversal is 1987
N L K P R M S Q T.
Q 29. Construct a binary tree whose preorder and inorder sequences are A B M H E O C P G J D K L I N 1990
F and H M C O E B A G P K L D I N J F respectively, where A, B, C, D, E, . . . are the labels of the
tree nodes. Is it unique?
Q 30. What is the number of binary trees with 3 nodes which when traversed in post-order give the sequence 1995
A, B, C? Draw all these binary trees.

Q 31. Draw the binary tree with the node labels a, b, c, d, e, f and g for which the inorder and postorder 1998
traversals result in the following sequences
Inorder: a f b c d g e
Postorder: a f c g e d b
Q 32. Let LASTPOST, LASTIN and LASTPRE denotes the last vertex visited in a postorder, inorder and 2000
preorder traversal respectively, of a completely binary tree. Which of the following is always true?

A. LASTIN = LASTPOST C. LASTPRE = LASTPOST

B. LASTIN = LASTPRE D. None of the above

Q 33. Draw all binary trees having exactly three nodes labelled A, B, and C on which preorder traversal gives 2002
the sequence C, B, A.
Q 34. Consider the label sequences obtained by the following pairs of traversals on a labelled binary tree. 2004
Which of these pairs identify a tree uniquely?

1. Preorder and postorder 3. Preorder and inorder

2. Inorder and postorder 4. Level order and postorder

A. 1 only B. 1 and 3 C. 3 only D. 4 only

88
 C Programming and Data Structures Trees Page 89 of 107

Q 35. Which of the following binary trees has its inorder and preorder traversals as BCAD and ABCD, 2004IT
respectively?

A. B. C. D.
Q 36. The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g respectively. The 2007
postorder traversal of the binary tree is:
A. d e b f g c a B. e d b g f c a C. e d b f g c a D. d e f g b c a

Q 37. The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But 2008IT
it is not known which is which.
I. MBCAFHPYK
II. KAMCBYPFH
III. MABCKYFPH

Pick the true statement from the following.

A. I and II are preorder and inorder sequences, respectively
B. I and III are preorder and postorder sequences, respectively
C. II is the inorder sequence, but nothing more can be said about the other two sequences
D. II and III are the preorder and inorder sequences, respectively

Q 38. Consider the following rooted tree with the vertex labeled P as the root 2014Set3

The order in which the nodes are visited during an in-order traversal of the tree is
A. SQPTRWUV B. SQPTUWRV C. SQPTWUVR D. SQPTRUWV

Q 39. Consider the following New-order strategy for traversing a binary tree: 2016Set2
• Visit the root;
• Visit the right subtree using New-order;
• Visit the left subtree using New-order;
The New-order traversal of the expression tree corresponding to the reverse polish expression
3 4 * 5 - 2 ^ 6 7 * 1 + -
is given by:

89
 C Programming and Data Structures Trees Page 90 of 107

A. + - 1 6 7 * 2 ^ 5 - 3 4 * C. - + 1 * 7 6 ^ 2 - 5 * 4 3
B. - + 1 * 6 7 ^ 2 - 5 * 3 4 D. 1 7 6 * + 2 5 4 3 * - ^ -

Q 40. The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree 2018
is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf.
The height of the binary tree above is .

Q 41. (MSQ) Consider the following tree traversals on a full binary tree: 2024DA
(i) Preorder
(ii) Inorder
(iii) Postorder
Which of the following traversal options is/are sufficient to uniquely reconstruct the full binary tree?
A. (i) and (ii) B. (ii) and (iii) C. (i) and (iii) D. (ii) only

9.3 Binary Search Tree

Q 42. A binary search tree is generated by inserting in order the following integers: 1996
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
The number of nodes in the left sub-tree and right sub-tree of the root is respectively is
A. (4, 7) B. (7, 4) C. (8, 3) D. (3, 8)

Q 43. A binary search tree is used to locate the number 43. Which of the following probe sequences are 1996
possible and which are not? Explain.
A. 61 52 14 17 40 43 B. 2 3 50 40 60 43
C. 10 65 31 48 37 43 D. 81 61 52 14 41 43
E. 17 77 27 66 18 43
Q 44. A binary search tree contains the values 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the 1997
values are printed out. Which of the following sequences is a valid output?
A. 5 3 1 2 4 7 8 6 B. 5 3 1 2 6 4 8 7 C. 5 3 2 4 1 6 7 8 D. 5 3 1 2 4 7 6 8
Q 45. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary 2003
search tree. The binary search tree uses the usual ordering on natural numbers. What is the inorder
traversal sequence of the resultant tree?
A. 7 5 1 0 3 2 4 6 8 9 B. 0 2 4 3 1 6 5 9 8 7 C. 0 1 2 3 4 5 6 7 8 9 D. 9 8 6 4 2 3 0 1 5 7
Q 46. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 15, 2004
12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node
from the root)?
A. 2 B. 3 C. 4 D. 6
Q 47. Postorder traversal of a given binary search tree T produces the following sequence of keys 2005
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
Which one of the following sequences of keys can be the result of an in-order traversal of the tree T ?

A. 9,10,15,22,23,25,27,29,40,50,60,95 C. 29,15,9,10,25,22,23,27,40,60,50,95
B. 9,10,15,22,40,50,60,95,23,25,27,29 D. 95,50,60,40,27,23,22,25,10,9,15,29

Q 48. How many distinct binary search trees can be created out of 4 distinct keys? 2005
A. 5 B. 14 C. 24 D. 42

90
 C Programming and Data Structures Trees Page 91 of 107

Q 49. The numbers 1, 2, . . . , n are inserted in a binary search tree in some order. In the resulting tree, the 2005IT
right subtree of the root contains p nodes. The first number to be inserted in the tree must be
A. p B. p + 1 C. n − p D. n − p + 1
Q 50. A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in preorder 2005IT
and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the
tree is traversed in postorder, the sequence obtained would be
A. 8,7,6,5,4,3,2,1 B. 1,2,3,4,8,7,6,5 C. 2,1,4,3,6,7,8,5 D. 2,1,4,3,7,8,6,5
Q 51. Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the 2006IT
number 55. Which of the following sequences CANNOT be the sequence of nodes examined?

A. {10, 75, 64, 43, 60, 57, 55} C. {9, 85, 47, 68, 43, 57, 55}
B. {90, 12, 68, 34, 62, 45, 55} D. {79, 14, 72, 56, 16, 53, 55}

Q 52. An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element 2006IT
of the array is 0.
(i) The index of the parent of element X[i], i ̸= 0, is?
       
i i−1 i i
A. B. C. D. −1
2 2 2 2
(ii) If only the root node does not satisfy the heap property, the algorithm to convert the complete
binary tree into a heap has the best asymptotic time complexity of
A. O(n) B. O(log n) C. O(n log n) D. P (n log log n)
(iii) If the root node is at level 0, the level of element X[i], i ̸= 0, is?
A. ⌊log2 i⌋ B. ⌈log2 (i + 1)⌉ C. ⌊log2 (i + 1)⌋ D. ⌈log2 i⌉
Q 53. You are given the postorder traversal, P , of a binary search tree on the n elements 1, 2, . . . , n. You 2008
have to determine the unique binary search tree that has P as its postorder traversal. What is the time
complexity of the most efficient algorithm for doing this?
A. Θ(log n) B. Θ(n) C. Θ(n log n)
D. None of the above, as the tree cannot be uniquely determined
Q 54. A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of 2008IT
keys.

I. 81, 537, 102, 439, 285, 376, 305 III. 142, 248, 520, 386, 345, 270, 307
II. 52, 97, 121, 195, 242, 381, 472 IV. 142, 248, 520, 386, 345, 270, 307

(i) Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences
list nodes in the order in which we could have encountered them in the search?
A. II and III only B. I and III only C. III and IV only D. III only
(ii) Which of the following statements is TRUE?
A. I, II and IV are inorder sequences of three different BSTs
B. I is a preorder sequence of some BST with 439 as the root
C. II is an inorder sequence of some BST where 121 is the root and 52 is a leaf
D. IV is a postorder sequence of some BST with 149 as the root
(iii) How may distinct BSTs can be constructed with 3 distinct keys?
A. 4 B. 5 C. 6 D. 9
Q 55. Which one of the following is the tightest upper bound that represents the time complexity of inserting 2013
an object into a binary search tree of n nodes?
A. O(1) B. O(log n) C. O(n) D. O(n log n)
Q 56. The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one 2013
of the following is the postorder traversal sequence of the same tree?

91
 C Programming and Data Structures Trees Page 92 of 107

A. 10, 20, 15, 23, 25, 35, 42, 39, 30 C. 15, 20, 10, 23, 25, 42, 35, 39, 30
B. 15, 10, 25, 23, 20, 42, 35, 39, 30 D. 15, 10, 23, 25, 20, 35, 42, 39, 30

Q 57. Which of the following is/are correct in order traversal sequence(s) of binary search tree(s)? 2015Set1

I. 3, 5, 7, 8, 15, 19, 25 III. 2, 7, 10, 8, 14, 16, 20

II. 5, 8, 9, 12, 10, 15, 25 IV. 4, 6, 7, 9, 18, 20, 25

A. I and IV only B. II and III only C. II and IV only D. II only

Q 58. What are the worst-case complexities of insertion and deletion of a key in a binary search tree? 2015Set1
A. Θ(log n) for both insertion and deletion
B. Θ(n) for both insertion and deletion
C. Θ(n) for insertion and Θ(log n) for deletion
D. Θ(log n) for insertion and Θ(n) for deletion

Q 59. While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence 2015Set3
shown, the element in the lowest level is
A. 65 B. 67 C. 69 D. 83

Q 60. The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search 2016Set2
tree, such that the resulting tree has height 6, is .
Note: The height of a tree with a single node is 0.

Q 61. Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are: 2017Set1
Note: The height of a tree with a single node is 0

A. 4 and 15 respectively. C. 4 and 14 respectively.

B. 3 and 14 respectively. D. 3 and 15 respectively.

Q 62. The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then 2017Set2
the post-order traversal of this tree is

A. 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20 C. 7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12
B. 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12 D. 7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12

Q 63. The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following 2020
is the postorder traversal of the tree?

A. 10, 11, 12, 15, 16, 18, 19, 20 C. 20, 19, 18, 16, 15, 12, 11, 10
B. 11, 12, 10, 16, 19, 18, 20, 15 D. 19, 16, 18, 20, 11, 12, 10, 15

Q 64. A binary search tree T contains n distinct elements. What is the time complexity of picking an element 2021Set1
in T that is smaller than the maximum element in T ?
A. Θ(n log n) B. Θ(n) C. Θ(log n) D. Θ(1)

Q 65. Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is 2022
stored using the array representation of binary heap trees. Assuming that the array indices start with
0, the 3rd largest element of the tree is stored at index .

92
 C Programming and Data Structures Trees Page 93 of 107

Q 66. You are given a set V of distinct integers. A binary search tree T is created by inserting all elements 2024Set2
of V one by one, starting with an empty tree. The tree T follows the convention that, at each node, all
values stored in the left subtree of the node are smaller than the value stored at the node. You are not
aware of the sequence in which these values were inserted into T , and you do not have access to T .
Which one of the following statements is TRUE?
A. Inorder traversal of T can be determined from V
B. Root node of T can be determined from V
C. Preorder traversal of T can be determined from V
D. Postorder traversal of T can be determined from V
Q 67. (MSQ) Which of the following statement(s) is/are TRUE for any binary search tree (BST) having n 2025Set1
distinct integers?
A. The maximum length of a path from the root node to any other node is (n − 1).
B. An inorder traversal will always produce a sorted sequence of elements.
C. Finding an element takes O(log2 n) time in the worst case.
D. Every BST is also a Min-Heap.
Q 68. Suppose the values 10, −4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary 2025Set2
search tree. Let T be the resulting binary search tree. The number of edges in the path from the node
containing 19 to the root node of T is . (Answer in integer)
Q 69. We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways 2011
can we populate the tree with the given set so that it becomes a binary search tree?
1 2n
A. 0 B. 1 C. n! D. n+1 . Cn

Q 70. When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 2007IT
50, 70, 80, 90 are traversed, not necessarily in the order given. How many different orders are possible
in which these key values can occur on the search path from the root to the node containing the value
60?
A. 35 B. 64 C. 128 D. 5040
Q 71. (i) Insert the following keys one by one into a binary search tree in the order specified. 2001
15, 32, 20, 9, 3, 25, 12, 1
Show the final binary search tree after the insertions.
(ii) Draw the binary search tree after deleting 15 from it.
(iii) Complete the statements S1, S2 and S3 in the following function so that the function computes
the depth of a binary tree rooted at t.
typedef struct tnode {
int key ;
struct tnode * left , * right ;
} * Tree ;

int depth ( Tree t )

{
int x , y ;
if ( t == NULL ) return 0;
x = depth ( t -> left );
S1 : ___________ ;

S2 : if ( x > y ) return __________ ;

S3 : else return _______ ;

93
 C Programming and Data Structures Trees Page 94 of 107

9.4 Code Fragments

Q 72. Consider the following C program segment: 2004

struct CellNode {
struct CellNode * leftChild ;
int element ;
struct CellNode * rightChild ;
};
int DoSomething ( struct CellNode * ptr )
{
int value = 0;
if ( ptr != NULL )
{
if ( ptr -> leftChild != NULL )
value = 1 + DoSomething ( ptr -> leftChild );
if ( ptr -> rightChild != NULL )
value = max ( value , 1 + DoSomething ( ptr -> rightChild );
}
return ( value );
}

The value returned by the function DoSomething when a pointer to the root of a nonempty tree is passed
as argument is:

A. The number of leaf nodes in the tree C. The number of internal nodes in the tree
B. The number of nodes in the tree D. The height of the tree

Q 73. Consider the following C program segment where CellNode represents a node in a binary tree: 2007
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 )
+ GetValue ( ptr - > rightChild );
}
return ( value );
}

The value returned by GetValue when a pointer to the root of a binary tree is passed as its argument is:

A. the number of nodes in the tree C. the number of leaf nodes in the tree
B. the number of internal nodes in the tree D. the height of the tree

Q 74. The height of a tree is defined as the number of edges on the longest path in the tree. The function 2012
shown in the pseudo-code below is invoked as height (root) to compute the height of a binary tree rooted
at the tree pointer root.

94
 C Programming and Data Structures Trees Page 95 of 107

int height ( treeptr n )

{
if ( n == NULL ) return -1;
if ( n -> left == NULL )
if ( n -> right == NULL ) return 0;
else return B1 ; // Box 1

else {
h1 = height ( n -> left );
if ( n -> right == NULL ) return (1+ h1 );
else {
h2 = height ( n -> right );
return B2 ; // Box 2
}
}
}

The appropriate expressions for the two boxes B1 and B2 are:

A. B1: (1 + height(n → right)); B2: (1 + max(h1, h2))
B. B1: (height(n → right)); B2: (1 + max(h1, h2))
C. B1: height(n → right); B2: max(h1, h2)
D. B1: (1 + height(n → right)); B2: max(h1, h2)

Q 75. Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the 2014Set3
root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the
tree is of type treeNode.
typedef struct treeNode * treeptr ;

struct treeNode
{
treeptr leftMostChild , rightSibling ;
};

int DoSomething ( treeptr tree )

{
int value =0;
if ( tree != NULL ) {
if ( tree - > leftMostChild == NULL )
value = 1;
else
value = DoSomething ( tree - > leftMostChild );
value = value + DoSomething ( tree - > rightSibling );
}
return ( value );
}

When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by
the function corresponds to the
A. number of internal nodes in the tree.
B. height of the tree.
C. number of nodes without a right sibling in the tree.
D. number of leaf nodes in the tree
Q 76. Consider the C function foo and the binary tree shown 2023

95
 C Programming and Data Structures Trees Page 96 of 107

typedef struct node {

int val ;
struct node * left , * right ;
} node ;

int foo ( node * p ) {

int retval ;
if ( p == NULL )
return 0;
else
{
retval = p - > val + foo (p - > left ) + foo (p - > right );
printf ( " % d " , retval );
return retval ;
}
}

When foo is called with a pointer to the root node of the given binary tree, what will it print?
A. 3 8 5 13 11 10 B. 3 5 8 10 11 13 C. 3 8 16 13 24 50 D. 3 16 8 50 24 13
Q 77. Consider a rooted n node binary tree represented using pointers. The best upper bound on the time 2014Set1
required to determine the number of subtrees having exactly 4 nodes is O(na logb n). Then the value of
a + 10b is .

9.5 Balanced Trees

Q 78. (i) In the balanced binary tree in the figure given below, how many nodes will become unbalanced 1996
when a node is inserted as a child of the node “g”?

A. 1 B. 3 C. 7 D. 8
(ii) Which of the following sequences denotes the post-order traversal sequence of the tree of above
question?
A. f e g c d b a B. g c b d a f e C. g c d b f e a D. f e d g c b a

96
 C Programming and Data Structures Trees Page 97 of 107

Q 79. A weight balanced tree is a binary tree in which for each node, the number of nodes in the left sub-tree 2002
is at least half and at most twice the number of nodes in the right sub-tree. The maximum possible
height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best
described by which of the following:
A. log2 n B. log4/3 n C. log3 n D. log3/2 n

Q 80. A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a 2004
function g(x) for each node x. If the cost of computing g(x) is:
 
min number of leaf-nodes , number of leaf-nodes
in left-subtree of x in right-subtree of x
Then the worst-case time complexity of the program is
A. Θ(n) B. Θ(n log n) C. Θ(n2 ) D. Θ(n2 log n)

Q 81. Which of the following is TRUE? 2008IT

A. The cost of searching an AVL tree is Θ(log n) but that of a binary search tree is O(n)
B. The cost of searching an AVL tree is Θ(log n) but that of a complete binary tree is Θ(n log n)
C. The cost of searching a binary search tree is O(log n) but that of an AVL tree is Θ(n)
D. The cost of searching an AVL tree is Θ(n log n) but that of a binary search tree is O(n)

Q 82. What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a 2009
single node is 0.
A. 2 B. 3 C. 4 D. 5

Q 83. The worst case running time to search for an element in a balanced binary search tree with n2n elements 2012
is
A. Θ(n log n) B. Θ(n2n ) C. Θ(n) D. Θ(log n)

Q 84. Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L 2014Set3
and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such
numbers in T . If the tightest upper bound on the time to compute the sum is O(na logb n + mc logd n),
the value of a + 10b + 100c + 1000d is .
Q 85. What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements 2020
initially?
A. Θ(n4 ) B. Θ(n2 ) C. Θ(n2 log n) D. Θ(n3 )

Q 86. In a balanced binary search tree with n elements, what is the worst case time complexity of reporting 2020
all elements in range [a, b]? Assume that the number of reported elements is k.
A. Θ(log n) B. Θ(log n + k) C. Θ(k log n) D. Θ(n log k)

9.6 B Trees and B+ Trees

Q 87. Consider the following 2 – 3 – 4 tree (i.e. B-tree with a minimum degree of two) in which each data 2003
item is a letter. The usual alphabetical ordering of letters is used in constructing the tree.

97
 C Programming and Data Structures Trees Page 98 of 107

What is the result of inserting G in the above tree?

A. B.

C. D. None of the above

Q 88. A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of 2008
node splitting operations that may take place?
A. 3 B. 4 C. 5 D. 6

Q 89. Consider a B-tree with degree m, that is, the number of children, c, of any internal node (except the 1999
root) is such that m ≤ c ≤ 2m − 1. Derive the maximum and minimum number of records in the leaf
nodes for such a B-tree with height h, h ≥ 1.(Assume that the root of a tree is at height 0).

Q 90. The below figure shows a B + tree where only key values are indicated in the records. Each block can 1989
hold upto three records. A record with a key value 34 is inserted into the B + tree. Obtain the modified
B + tree after insertion.

Q 91. For a B + - tree of order d with n leaf nodes, the number of nodes accessed during a search is O( ). 1994

Q 92. Consider B + - tree of order d shown in figure. (A B + - tree of order d contains between d and 2d keys 1994
in each node)
Draw the resulting B + - tree after 100 is inserted in the figure below.

Q 93. A B + - tree of order d is a tree in which each internal node has between d and 2d key values. An internal 1997
node with M key values has M + 1 children. The root (if it is an internal node) has between 1 and 2d
key values. The distance of a node from the root is the length of the path from the root to the node.
All leaves are at the same distance from the root. The height of the tree is the distance of a leaf from
the root.
(i) What is the total number of key values in the internal nodes of a B + -tree with l leaves (l ≥ 2)
(ii) What is the maximum number of internal nodes in a B + - tree of order 4 with 52 leaves?
(iii) What is the minimum number of leaves in a B + -tree of order d and height h(h ≥ 1)?

98
 C Programming and Data Structures Trees Page 99 of 107

Q 94. We wish to construct a B + tree with fan-out (the number of pointers per node) equal to 3 for the 2001
following set of key values:
80, 50, 10, 70, 30, 100, 90
Assume that the tree is initially empty and the values are added in the order given.
(i) Show the tree after insertion of 10, after insertion of 30, and after insertion of 90. Intermediate
trees need not be shown.
(ii) The key values 30 and 10 are now deleted from the tree in that order show the tree after each
deletion.
Q 95. Consider the B + tree in the adjoining figure, where each node has at most two keys and three links. 2007IT

Keys K15 and then K25 are inserted into this tree in that order. Exactly how many of the following
nodes (disregarding the links) will be present in the tree after the two insertions?

A. 1 B. 2 C. 3 D. 4
Q 96. The following key values are inserted into a B + - tree in which order of the internal nodes is 3, and that 2009
of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the maximum number
of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that
can be stored in it. The B + - tree is initially empty

10, 3, 6, 8, 4, 2, 1

The maximum number of times leaf nodes would get split up as a result of these insertions is
A. 2 B. 3 C. 4 D. 5
Q 97. Consider a B + -tree in which the maximum number of keys in a node is 5. What is the minimum number 2010
of keys in any non-root node?
A. 1 B. 2 C. 3 D. 4
Q 98. With reference to the B + tree index of order 1 shown below, the minimum number of nodes (including 2015
the Root node) that must be fetched in order to satisfy the following query. “Get all records with a
search key greater than or equal to 7 and less than 15” is .

99
 C Programming and Data Structures Trees Page 100 of 107

Q 99. In a B + tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the 2024Set1
following cases?

A. Only the root node C. All internal nodes

B. All leaf nodes D. Only the leftmost leaf node

Q 100. In a B + - tree where each node can hold at most four key values, a root to leaf path consists of the 2025Set2
following nodes:

A = (49, 77, 83, −), B = (7, 19, 33, 44), C = (20∗ , 22∗ , 25∗ , 26∗ )

The *-marked keys signify that these are data entries in a leaf.
Assume that a pointer between keys k1 and k2 points to a subtree containing keys in [k1 , k2 ), and that
when a leaf is created, the smallest key in it is copied up into its parent.
A record with key value 23 is inserted into the B + -tree.
The smallest key value in the parent of the leaf that contains 25∗ is . (Answer in integer)

Q 101. B + Trees are considered BALANCED because 2016

A. The lengths of the paths from the root to all leaf nodes are all equal.
B. The lengths of the paths from the root to all leaf nodes differ from each other by at most 1.
C. The number of children of any two non-leaf sibling nodes differ by at most 1.
D. The number of records in any two leaf nodes differ by at most 1.
Q 102. Which one of the following statements is NOT correct about the B + tree data structure used for 2019
creating an index of a relational database table?
A. B + Tree is a height-balanced tree
B. Non-leaf nodes have pointers to data records
C. Key values in each node are kept in sorted order
D. Each leaf node has a pointer to the next leaf node

9.7 More Questions

Q 103. Consider the following three version of the binary search program. Assume that the elements of type TIFR’12
T can be compared with each other; also assume that the array is sorted.
i , j , k : integer ;
a : array [1.... N ] of T ;
x : T;

Program 1 : i := 1; j := N ;
repeat
k := ( i + j ) div 2;
if a [ k ] < x then i := k else j := k
until ( a [ k ] = x ) or ( i > j )
Program 2 : i := 1; j := N ;
repeat
k := ( i + j ) div 2;
if x < a [ k ] then j := k - 1;
if a [ k ] < x then i := k + 1;
until i > j
Program 3 := i := 1; j := N
repeat

100
 C Programming and Data Structures Trees Page 101 of 107

k := ( i + j ) div 2;
if x < a [ k ] then j := k else i := k + 1
until i > j

A binary search program is called correct provided it terminates with a[k] = x whenever such an element
exists, or it terminates with a [k] ̸= x if there exists no array element with value x. Which of the following
statements is correct?
A. Only Program 1 is correct
B. Only Program 2 is correct
C. Only Program 1 and 2 are correct.
D. Both Program 2 and 3 are correct
E. All the three programs are wrong

Q 104. Given a binary tree of the following form and having n nodes, the height of the tree is TIFR’13

√
A. Θ (log n) B. Θ (n) C. Θ ( n) D. Θ (n/ log n) E. None of the above.

Q 105. Let T be a rooted binary tree whose vertices are labelled with symbols a, b, c, d, e, f, g, h, i, j, k. Suppose TIFR’14
the in-order (visit left subtree, visit root, visit right subtree) and post-order (visit left subtree, visit right
subtree, visit root) traversals of T produce the following sequences.
in-order: a, b, c, d, e, f, g, h, i, j, k
post-order: a, c, b, e, f, h, j, k, i, g, d
How many leaves does the tree have?
A. THREE. B. FOUR. C. FIVE. D. SIX.
E. Cannot be determined uniquely from the given information.

Q 106. Let B be a rooted binary tree of n nodes. Two nodes of B are said to be a sibling pair if they ISI’14
are the children of the same parent. For example, given the binary tree in Figure 1, the sibling
pairs are (2, 3) and (6, 7). Design an O(n) time algorithm that prints all the sibling pairs of B.

Q 107. Consider the following tree with 13 nodes. TIFR’14

101
 C Programming and Data Structures Trees Page 102 of 107

Suppose the nodes of the tree are randomly assigned distinct labels from {1, 2, . . . , 13}, each permutation
being equally likely. What is the probability that the labels form a min-heap (i.e., every node receives
the minimum label in its subtree)?
1

1
2 1 2 1 3 1

1
1
3 2
E. 2113



A. 6! 3! B. 3! 2! C. 13 6 3 D. 13

Q 108. First, consider the tree on the left. TIFR’15

On the right, the nine nodes of the tree have been assigned numbers from the set {1, 2, . . . , 9} so that for
every node, the numbers in its left subtree and right subtree lie in disjoint intervals (that is, all numbers
in one subtree are less than all numbers in the other subtree). How many such assignments are possible?
Hint: Fix a value for the root and ask what values can then appear in its left and right subtrees.
A. 29 = 512 B. 24 .32 .5.9 = 6480 C. 23 .3.5.9 = 1080 D. 24 = 16 E. 23 .33 = 216
Q 109. Let B be a binary search tree (BST) on eight nodes filled with the following set of eight integer keys ISI’22
A = {10, 2, 5, 3, 20, 15, 9, 22}. The order in which these keys were inserted to create B is not known.
However, it is known that for the given BST, (8 × 9)/2 = 36 comparisons are needed to check the
presence of all the eight keys in A. Using this information as a clue or otherwise, construct and depict
pictorially four possible BSTs each of which requires 36 comparisons to check the presence of all the
eight keys in A. Justify your answer.

Q 110. We have an array A of n numbers, where n is a power of 2. CMI’25

We build a full binary tree on top of the array A. The elements of the array are leaves of the tree,
numbered 1, 2, . . . , n, from left to right. At each internal node of the tree, we store the sum of the values
of the array elements in the subtree rooted under it.
We wish to use this data structure to support operations psum(i), 1 ≤ i ≤ n,and add(y, i), 1 ≤ i ≤ n,
defined below.
j=i
P
psum(i) : return the value of A[j]
j=1
add(y, i) : update A[i] to A[i] + y
(i) Draw the data structure built on top of the array A = [−2, 1, 4, −3, 6, 7, 9, −5].
(ii) How will you update the data structure when you perform add(y, i)? Assuming arithmetic opera-
tions are free, what is the time complexity of this update, as a function of n?

102
C Programming and Data Structures Trees Page 103 of 107

(iii) Give an algorithm to implement psum(i), 1 ≤ i ≤ n − 1 using this data structure? Assuming arith-
metic operations take unit time, what is the time complexity of psum(i)? What is the complexity
of psum(n)?

103
 C Programming and Data Structures Hash Tables Page 104 of 107

Chapter 10 Hash Tables

Q 1. Match the items in Column 1 with the items in Column 2 in the following table: 2024DA

Column 1 Column 2

(p) First In First Out (i) Stacks

(q) Lookup Operation (ii) Queues
(r) Last In First Out (iii) Hash Tables

A. (p) − (ii), (q) − (iii), (r) − (i) C. (p) − (i), (q) − (ii), (r) − (iii)
B. (p) − (ii), (q) − (i), (r) − (iii) D. (p) − (i), (q) − (iii), (r) − (ii)

Q 2. Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is . 2015Set3

Q 3. Insert the characters of the string K R P C S N Y T J M into a hash table of size 10. Use the hash 1996
function
h(x) = (ord(x) − ord(“A”) + 1) mod 10
and linear probing to resolve collisions.
(i) Which insertions cause collisions?
(ii) Display the final hash table.

Q 4. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 2004
10, which of the following statements are true?

1. 9679, 1989, 4199 hash to the same value

2. 1471, 6171 hash to the same value
3. All elements hash to the same value
4. Each elements hash to different value

A. 1 only B. 2 only C. 1 and 2 only D. 3 or 4

Q 5. A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers 2005IT
and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in
what location would the key value 142 be inserted?
A. 2 B. 3 C. 4 D. 6
Q 6. Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. 2007
Assuming the hash table is initially empty, which of the following is the contents of the table when the
sequence 1,3,8,10 is inserted into the table using closed hashing? Note that - denotes an empty location
in the table.
A. 8, -, -, -, -, -, 10 B. 1,8,10, -, -, -, 3 C. 1, -, -, -, -, -, 3 D. 1,10,8, -, -, -,3

Q 7. Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be 2008IT
the hash function used. A sequence of records with keys
43 36 92 87 11 4 71 13 14
is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is
the index of the bin into which the last record is inserted?
A. 3 B. 4 C. 6 D. 7

104
 C Programming and Data Structures Hash Tables Page 105 of 107

Q 8. The keys 12,18,13,2,3,23,5 and 15 are inserted into an initially empty hash table of length 10 using open 2009
addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
0 0 0 0
1 1 1 1
2 2 2 12 2 12 2 2, 12
3 23 3 13 3 13 3 13, 3, 23
4 4 4 2 4
A. B. C. D.
5 15 5 5 5 3 5 5, 15
6 6 6 23 6
7 7 7 5 7
8 18 8 18 8 18 8 18
9 9 9 15 9

Q 9. A hash table of length 10 uses open addressing with hash function h(k) = k mod 10, and linear probing. 2010
After inserting 6 values into an empty hash table, the table is shown as below

0
1
2 42
3 23
4 34
5 52
6 46
7 33
8
9
(i) Which one of the following choices gives a possible order in which the key values could have been
inserted in the table?

A. 46, 42, 34, 52, 23, 33 C. 46, 34, 42, 23, 52, 33
B. 34, 42, 23, 52, 33, 46 D. 42, 46, 33, 23, 34, 52

(ii) How many different insertion sequences of the key values using the same hash function and linear
probing will result in the hash table shown above?
A. 10 B. 20 C. 30 D. 40
Q 10. Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by 2014Set1
chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum,
minimum, and average chain lengths in the hash table, respectively, are
A. 3, 0 and 1 B. 3, 3 and 3 C. 4, 0 and 1 D. 3, 0 and 2

Q 11. Consider a hash table of size 10 with indices {0, 1, . . . , 9} 2025DA

h(x) = 3x( mod 10)

with the hash function where linear probing is used to handle collisions. The hash table is initially empty
and then the following sequence of keys is inserted into the hash table: 1, 4, 5, 6, 14, 15. The indices
where the keys 14 and 15 are stored are, respectively
A. 2 and 5 B. 2 and 6 C. 4 and 5 D. 4 and 6
Q 12. In a double hashing scheme, h1 (k) = k mod 11 and h2 (k) = 1 + (k mod 7) are the auxiliary hash 2025Set1
functions. The size m of the hash table is 11. The hash function for the i-th probe in the open address
table is [h1 (k) + i h2 (k)] mod m. The following keys are inserted in the given order: 63, 50, 25, 79, 67,
24.
The slot at which key 24 gets stored is . (Answer in integer)

105
 C Programming and Data Structures Hash Tables Page 106 of 107

Q 13. Consider a double hashing scheme in which the primary hash function is h1 (k) = k mod 23, and the 2020
secondary hash function is h2 (k) = 1 + (k mod 19). Assume that the table size is 23. Then the address
returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key
value k = 90 is .
Q 14. (MSQ) Consider a dynamic hashing approach for 4-bit integer keys: 2021Set1
1. There is a main hash table of size 4.
2. The 2 least significant bits of a key is used to index into the main hash table.
3. Initially, the main hash table entries are empty.
4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding
to a main hash table entry is organized as a binary tree that grows on demand.
5. First, the 3rd least significant bit is used to divide the keys into left and right subtrees.
6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right
subtrees based on the 4th least significant bit.
7. A split is done only if it is needed, i.e., only when there is a collision.
Consider the following state of the hash table.

Which of the following sequences of key insertions can cause the above state of the hash table (assume
the keys are in decimal notation)?
A. 5, 9, 4, 13, 10, 7 B. 9, 5, 10, 6, 7, 1 C. 10, 9, 6, 7, 5, 13 D. 9, 5, 13, 6, 10, 14
Q 15. Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h1 and h2 . 2022
Further suppose our hashing scheme uses h1 for the odd keys and h2 for the even keys. What is the
expected number of keys in a slot?
m n 2n n
A. n B. m C. m D. 2m

Q 16. An algorithm has to store several keys generated by an adversary in a hash table. The adversary is 2023
malicious who tries to maximize the number of collisions. Let k be the number of keys, m be the number
of slots in the hash table, and k > m.
Which one of the following is the best hashing strategy to counteract the adversary?
A. Division method, i.e., use the hash function h(k) = k mod m.
B. Multiplication method, i.e., use the hash function h(k) = ⌊m(kA − ⌊kA⌋)⌋ ,where A is a carefully
chosen constant.
C. Universal hashing method.
D. If k is a prime number, use Division method. Otherwise, use Multiplication method.

Q 17. Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform 2014Set3
hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

A. (97 × 97 × 97)/1003 C. (97 × 96 × 95)/1003

B. (99 × 98 × 97)/1003 D. (97 × 96 × 95/(3! × 1003 )

Q 18. Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets 2015Set2
numbered 0 to 9 for i ranging from 0 to 2020?
A. h(i) = i2 mod 10 B. h(i) = i3 mod 10 C. h(i) = (11 ∗ i2 )mod 10 D. h(i) = (12 ∗ i2 )mod 10

106
 C Programming and Data Structures Hash Tables Page 107 of 107

Q 19. Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of 2007IT
how many keys will the probability that any new key hashed collides with an existing one exceed 0.5.
A. 5 B. 6 C. 7 D. 10

10.1 More Questions

Q 20. Suppose 3 elements are hashed independently and uniformly at random one by one to slots in a hash TIFR’25
table of size 6 (assume that in case of a collision, the element is hashed to the first free slot). What is
the expected number of elements that DO NOT collide with an existing element in the table?
A. 25/18 B. 3/2 C. 59/36 D. 2 E. 5/2

107