Category: Data Structures & Algorithms Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Introsort”.

1. Which of the following sorting algorithm is used by C++ internally?
a) quicksort
b) introsort
c) merge sort
d) heap sort

Answer: b
Clarification: Introsort is the in built sorting algorithm used by C++. It is an example of a hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine.

2. Which of the following sorting algorithm is not a constituent of introsort?
a) selection sort
b) quicksort
c) insertion sort
d) heap sort
Answer: a
Clarification: Introsort is a hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine. It may use quick sort or heap sort or insertion sort depending on the given situation.

3. Introsort begins sorting the given array by using which of the following sorting algorithm?
a) selection sort
b) quick sort
c) insertion sort
d) heap sort

Answer: b
Clarification: Introsort begins sorting any given array by using quick sort. Then it may switch to heap sort or insertion sort or may stick to quick sort depending upon the size of the partition.

4. Which of the following sorting algorithm is NOT stable?
a) Introsort
b) Brick sort
c) Bubble sort
d) Merge sort

Answer: a
Clarification: Out of the given options introsort is the only algorithm which is not stable. As it may use quick sort in some case to perform sorting which is itself not stable. Thus stability of introsort is not guaranteed.

5. Which of the following sorting algorithm is in-place?
a) intro sort
b) merge sort
c) counting sort
d) radix sort

Answer: a
Clarification: Introsort may use quick sort or heap sort or insertion sort internally in order to sort the given input. All of the three algorithms are in place, thus making introsort to be an in-place sorting algorithm.

6. Introsort sort is a comparison based sort.
a) true
b) false

Answer: a
Clarification: Quicksort, heap sort and insertion sort are comparison based sorts. Thus overall introsort also becomes a comparison based sort.

7. What is the best case time complexity of introsort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: b
Clarification: Introsort is mainly governed by heap sort and quick sort. As the best case of both heap sort and quick sort is O(n log n) so the best case of introsort also becomes O(n log n).

8. What is the worst case time complexity of introsort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: b
Clarification: Worst case time complexity of quicksort is avoided when we implement introsort. Introsort switches to heap sort when there is a possibility of crossing the maximum depth limit.

9. What is the average time complexity of introsort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: b
Clarification: Average time complexity of introsort remains to be O(n log n) as for most of the cases quick sort and heap sort are used which have O(n log n) time complexity for an average case.

10. What is the auxiliary space requirement of introsort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: d
Clarification: Introsort is a hybrid of quick sort, heap sort and insertion sort. So like quick sort it may use O(log n) auxiliary space in the stack to store call statements.

11. Why is heap sort preferred over merge sort for introsort implementation?
a) Because heap sort is faster
b) Because heap sort requires less space
c) Because heap sort is easy to implement
d) Because heap sort is easy to understand
Answer: b
Clarification: Both heap sort and merge sort have the same time complexity. But heap sort is an in-place sorting algorithm whereas merge sort requires O(n) auxiliary space which makes heap sort a more preferable option.

12. Why is insertion sort preferred over other sorting algorithms (like selection sort, bubble sort etc.) for introsort implementation?
a) Because insertion sort is faster and adaptive
b) Because insertion sort requires less space
c) Because insertion sort is easy to implement
d) Because insertion sort is easy to understand
Answer: a
Clarification: When small arrays need to be sorted then insertion sort proves to be the best choice. Also it is adaptive so it performs better than others when the given array is fully/partially sorted.

13. What is the cut-off for switching from quick sort to insertion sort in the implementation of introsort?
a) 4
b) 8
c) 16
d) 32

Answer: c
Clarification: When small arrays needs to be sorted then insertion sort proves to be the best choice. So when the size of the partition is less than 16 introsort switches to insertion sort. This particular value has been deduced experimentally.

14. What is the cut-off for switching from quick sort to heap sort in the implementation of introsort?
a) 16
b) n²
c) n log(n)
d) 2 log (n)

Answer: d
Clarification: Quicksort has a worst case time complexity of O(n²) which is not preferable. So in order to avoid worst case of quicksort, introsort switches to heap sort when the depth is greater than 2 log(n). This particular value has been deduced experimentally.

15. Which of the following sorting algorithm will be preferred when the size of partition is between 16 and 2 log(n) while implementing introsort?
a) quick sort
b) insertion sort
c) heap sort
d) merge sort

Answer: a
Clarification: Quicksort proves to be the best sorting algorithm for mid sized arrays as it has low space and time complexity. Thus quick sort is preferred when size of partition is between 16 and 2 log(n).

16. What will be the output of the given C++ code?

#include  
using namespace std; 
int main() 
{ 
    int arr[] = {1,3,4,2,5}; 
    int n = sizeof(arr)/sizeof(arr[0]);  
    sort(arr, arr+n, greater<int>());   
    int a; 
    for (a = 0; a < n; a++) 
        cout << arr[a] << " ";   
    return 0; 
}

a) 1 2 3 4 5
b) 1 3 4 2 5
c) 5 4 3 2 1
d) error

Answer: c
Clarification: The given program sorts the input in descending order. It is due to the third parameter i.e. greater() which is passed to the function sort().

17. What will be the output of the given C++ code?

#include  
using namespace std; 
int main() 
{ 
    int arr[] = {1, 3,4,2,5}; 
    int n = sizeof(arr)/sizeof(arr[0]);   
    sort(arr, arr+n); 
    int a;
    for ( a = 0; a< n; a++) 
        cout << arr[a] << " ";  
    return 0; 
}

a) 1 2 3 4 5
b) 1 3 4 2 5
c) 5 4 3 2 1
d) error
Answer: a
Clarification: The given program sorts the input in ascending order. Function sort() uses two parameters in the form of address of the first and last element of the array to sort the array.

18. What will be the output of the given C++ code?

#include  
using namespace std; 
int main() 
{ 
	int arr[] = {1, 3,4,2,5}; 
	int n = sizeof(arr)/sizeof(arr[0]);
	sort(arr+2, arr+n, greater<int>()); 
        int a;
	for (int a = 0; a < n; a++) 
		cout << arr[a] << " "; 
	return 0; 
}

a) 1 2 3 4 5
b) 1 5 4 3 2
c) 5 4 3 2 1
d) 1 3 5 4 2
Answer: d
Clarification: As the first parameter to function sort() is arr+2 so the sorting begins from the third element i.e. 4. Also as there is a third argument greater () to the function sort() so the sorting will be done in descending order.

& Algorithms.

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Bucket Sort (Uniform Keys)”.

1. How many comparisons will be made to sort the array arr={1, 5, 3, 8, 2} using bucket sort?
a) 5
b) 7
c) 9
d) 0

Answer: d
Clarification: As bucket sort is an example of a non-comparison sort so it is able to sort an array without making any comparison. So the answer should be 0.

2. What is the alternate name of bucket sort?
a) group sort
b) radix sort
c) bin sort
d) uniform sort
Answer: c
Clarification: Bucket sort is also known as bin sort. It is an example of a non-comparison sort.

3. Which of the following non-comparison sort can also be considered as a comparison based sort?
a) counting sort
b) MSD radix sot
c) bucket sort
d) pigeonhole sort
Answer: c
Clarification: Bucket sort can also be considered as a comparison based sort. It is because it can also be implemented with comparisons.

4. Which of the following is not true about bucket sort?
a) It is a non comparison based integer sort
b) It is a distribution sort
c) It can also be considered as comparison based sort
d) It is in place sorting algorithm

Answer: d
Clarification: Bucket sort is a non comparison based integer sort. It sorts the given data by distributing the array elements into a number of buckets. It is not an in place sorting technique.

5. Which of the following don’t affect the time complexity of bucket sort?
a) algorithm implemented for sorting individual buckets
b) number of buckets used
c) distribution of input
d) input values

Answer: d
Clarification: Time complexity of bucket sort is affected by various factors. These include algorithm implemented for sorting individual buckets, number of buckets used and distribution of input. It doesnot depend on the input value. It can be either positive or negative or zero.

6. Bucket sort is most efficient in the case when __________
a) the input is non uniformly distributed
b) the input is uniformly distributed
c) the input is randomly distributed
d) the input range is large

Answer: b
Clarification: Bucket sort works by distributing the array elements into a number of buckets. So bucket sort is most efficient in the case when the input is uniformly distributed.

7. Bucket sort is a generalization of which of the following sort?
a) LSD radix sort
b) Pigeonhole sort
c) Counting sort
d) MSD radix sort

Answer: b
Clarification: Pigeonhole sort is a particular case of bucket sort. Bucket sort is also closely related to MSD radix sort.

8. What is the worst case time complexity of bucket sort (k = number of buckets)?
a) O(n + k)
b) O(n.k)
c) O(n²)
d) O(n log n)

Answer: c
Clarification: Time complexity of bucket sort is O(n²) in the worst case. So if bucket sort does not get the inputs in the desired manner then it becomes very inefficient.

9. What is the best time complexity of bucket sort (k= number of buckets)?
a) O(n + k)
b) O(n.k)
c) O(n²)
d) O(n log n)

Answer: a
Clarification: Time complexity of bucket sort is O(n+k). It performs better than any comparison based sort if there is a uniform input distribution.

10. Which of the following is not necessarily a stable sorting algorithm?
a) bucket sort
b) counting sort
c) merge sort
d) pigeonhole sort

Answer: a
Clarification: Bucket sort is not necessarily a stable sorting algorithm. This is because its stability depends on the stability of the algorithm that we have used to sort the individual buckets.

11. Bucket sort is an in place sorting algorithm.
a) True
b) False

Answer: b
Clarification: Bucket sort is not an in place sorting algorithm. It requires an auxiliary space of O(n k) in the worst case.

12. What is the worst space complexity of bucket sort (k = number of buckets)?
a) O(n + k)
b) O(n.k)
c) O(n²)
d) O(n log n)

Answer: b
Clarification: Worst case space complexity of bucket sort is O(n.k). So it is not an in place sorting algorithm.

Data Structures & Algorithms Multiple Choice Questions on “Generating Combinations”.

1. What is meant by the term lexicographical order?
a) dictionary ordering of elements
b) reverse dictionary ordering of elements
c) to sort according to value of first element
d) to sort according to value of last element

Answer: a
Clarification: Lexicographical order is also known as dictionary order. It is a generalized method of the way words are alphabetically ordered in a dictionary.

2. How many combinations of 2 elements will be formed from the array arr={1,2,3}?
a) 1
b) 2
c) 3
d) 4

Answer: c
Clarification: No.of combinations of r elements for an array of size n will be given by the formula nCr. So for the given problem, we have 3C2=3.

3. What will be the lexicographical order of combinations of 2 elements each formed from the array arr={1,2,3}?
a) {{2,1},{3,2},{3,1}}
b) {{1,2},{2,3},{1,3}}
c) {{1,2},{1,3},{2,3}}
d) {{2,1},{3,1},{3,2}}

Answer: c
Clarification: The number of combinations for the problem will be 3 according to the formula 3C2. When ordered in lexicographical manner these will be {{1,2},{1,3},{2,3}}.

4. What will be the auxiliary space requirement (excluding call stack) of the program to print combinations of r elements each from array of size n?
a) O(n*r)
b) O(n/r)
c) O(n)
d) O(r)

Answer: d
Clarification: Code to print combinations will require an auxiliary space of O(r) other than call stack memory. This memory is required by an array that is used for storing combinations formed.

5. The code for printing combinations is in-place.
a) true
b) false

Answer: b
Clarification: Code to print combinations will require an auxiliary space of O(r) other than call stack memory. So it is not an in-place algorithm.

6. What will be the time complexity of the code to print combinations?
a) O(n)
b) O(n²)
c) O(n log n)
d) O(2ⁿ)

Answer: d
Clarification: The recurrence relation of the code to print combinations will be T(n)=2T(n-1)+k. It is found to be equal to O(2ⁿ).

7. What will be the output for the following code?

#include 
void combination(int arr[],int n,int r,int index,int aux[],int i); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, n, r, 0, aux, 0); 
} 
void combination(int arr[], int n, int r, int index, int aux[], int i) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ",aux[j]); 
		printf(", "); 
		return; 
	} 
	if (i >= n) 
		return; 
	aux[index] = arr[i]; 
	combination(arr, n, r, index+1, aux, i+1); 
	combination(arr, n, r, index, aux, i+1); 
} 
int main() 
{ 
	int arr[] = {1, 2,2}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
	return 0; 
}

a) 1 2, 1 2, 2 2
b) 1 2, 1 2, 2 2 ,
c) 1 2, 2 1, 2 2 ,
d) 1 2, 2 1, 2 2
Answer: b
Clarification: The given code prints the combinations of the given array in lexicographical order.The given code considers the duplicate 2s as different entities.Note that the comma is printed even for the last combination.

8. Which of the following code prints the combinations of a given array?
a)

#include  
void combination(int arr[], int aux[], int start, int end, int index, int r); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, aux, 0, n-1, 0, r); 
}
void combination(int arr[], int aux[], int start, int end, 
					int index, int r) 
{ 	
	if (index <= r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ", aux[j]); 
		printf(", "); 
		return; 
	} 	
	for (int i=start; i<=end && end-i+1 >= r-index; i++) 
	{ 
		aux[index] = arr[i]; 
		combination(arr, aux, i+1, end, index+1, r); 
	} 
}  
int main() 
{ 
	int arr[] = {1, 2, 3}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
}

b)

#include  
void combination(int arr[], int aux[], int start, int end, 
					int index, int r); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, aux, 0, n-1, 0, r); 
}
void combination(int arr[], int aux[], int start, int end, 
					int index, int r) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ", aux[j]); 
		printf(", "); 
		return; 
	} 	
	for (int i=start; i<=end && end-i+1 >= r-index; i++) 
	{ 
		aux[index] = arr[i]; 
		combination(arr, aux, i+1, end, index+1, r); 
	} 
} 
 
int main() 
{ 
	int arr[] = {1, 2, 3}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
}

c)

#include  
void combination(int arr[], int aux[], int start, int end, 
					int index, int r); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, aux, 0, n-1, 0, r); 
}
void combination(int arr[], int aux[], int start, int end, 
					int index, int r) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ", aux[j]); 
		printf(", "); 
		return; 
	} 	
	for (int i=start; i<=end ; i++) 
	{ 
		aux[index] = arr[i]; 
		combination(arr, aux, i+1, end, index+1, r); 
	} 
} 
 
int main() 
{ 
	int arr[] = {1, 2, 3}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
}

d)

#include  
void combination(int arr[], int aux[], int start, int end, 
					int index, int r); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, aux, 0, n-1, 0, r); 
}
void combination(int arr[], int aux[], int start, int end, 
					int index, int r) 
{ 	
	if (index <= r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ", aux[j]); 
		printf(", "); 
		return; 
	} 
	for (int i=start; i<=end; i++) 
	{ 
		aux[index] = arr[i]; 
		combination(arr, aux, i+1, end, index+1, r); 
	} 
} 
 
int main() 
{ 
	int arr[] = {1, 2, 3}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
}

Answer: b
Clarification: In the code we start from first index (index = 0) in array aux and one by one fix elements at this index and recur for remaining indexes. Finally, when index becomes equal to r we print the combination.

9. Which of the following code prints the combinations of a given array?
a)

#include 
void combination(int arr[],int n,int r,int index,int aux[],int i); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, n, r, 0, aux, 0); 
} 
void combination(int arr[], int n, int r, int index, int aux[], int i) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ",aux[j]); 
		printf(", "); 
		return; 
	} 
	if (i >= n) 
		return; 
	aux[index] = arr[i]; 
	combination(arr, n, r, index+1, aux, i+1); 
	combination(arr, n, r, index, aux, i+1); 
} 
 
int main() 
{ 
	int arr[] = {1, 2,2}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
	return 0; 
}

b)

#include 
void combination(int arr[],int n,int r,int index,int aux[],int i); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, n, r, 0, aux, 0); 
} 
void combination(int arr[], int n, int r, int index, int aux[], int i) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ",aux[j]); 
		printf(", "); 
		return; 
	} 
	if (i >= n) 
		return; 
	aux[index] = arr[i]; 
	combination(arr, n, r, index+1, aux, i+1); 
	combination(arr, n, r, index+1, aux, i+1); 
} 
int main() 
{ 
	int arr[] = {1, 2,2}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
	return 0; 
}

c)

#include 
void combination(int arr[],int n,int r,int index,int aux[],int i); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, n, r, 0, aux, 0); 
} 
void combination(int arr[], int n, int r, int index, int aux[], int i) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ",aux[j]); 
		printf(", "); 
		return; 
	} 
	if (i >= n) 
		return; 
	aux[index] = arr[i]; 
	combination(arr, n, r, index-1, aux, i+1); 
	combination(arr, n, r, index, aux, i+1); 
} 
int main() 
{ 
	int arr[] = {1, 2,2}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
	return 0; 
}

d)

#include 
void combination(int arr[],int n,int r,int index,int aux[],int i); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, n, r, 0, aux, 0); 
} 
void combination(int arr[], int n, int r, int index, int aux[], int i) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ",aux[j]); 
		printf(", "); 
		return; 
	} 
	if (i >= n) 
		return; 
	aux[index] = arr[i]; 
	combination(arr, n, r, index, aux, i+1); 
	combination(arr, n, r, index+1, aux, i+1); 
} 
int main() 
{ 
	int arr[] = {1, 2,2}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
	return 0; 
}

Answer: a
Clarification: In this method we consider each method one by one and recur for two cases.In first case we include that element in our array and in second case we don’t .When the number of elements in the array aux[] becomes equal to r then we print that combination.

10. What will be the output for the following code?

#include  
void combination(int arr[], int aux[], int start, int end, int index, int r); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
        combination(arr, aux, 0, n-1, 0, r); 
}
void combination(int arr[], int aux[], int start, int end, int index, int r) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ", aux[j]); 
		printf(", "); 
		return; 
	} 	
	for (int i=start; i<=end && end-i+1 >= r-index; i++) 
	{   aux[index] = arr[i]; 
		combination(arr, aux, i+1, end, index+1, r); 
	} 
}  
int main() 
{ 
	int arr[] = {1, 2, 3}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
}

a) 1 2, 1 3, 2 3
b) 1 3,1 2,2 3,
c) 1 2, 1 3, 2 3,
d) 1 2,1 3,2 3,

Answer: c
Clarification: The given code prints the combinations of the given array in lexicographical order.Note that the comma is printed even for the last combination.

11. What will be the output for the following code?

#include 
#include 
void combination(int arr[], int aux[], int start, int end, int index, int r);
int compare (const void * a, const void * b)
{  return ( *(int*)a - *(int*)b );  }
void print(int arr[], int n, int r)
{
    int aux[r];
    qsort (arr, n, sizeof(int), compare);    
    combination(arr, aux, 0, n-1, 0, r);
}
void combination(int arr[], int aux[], int start, int end, int index, int r)
{
    if (index == r)
    {
        for (int i=0; i<r; i++)
            printf("%d " ,aux[i]);
        printf(", ");
        return;
    }    
    for (int i=start; i<=end && end-i+1 >= r-index; i++)
    {
        aux[index] = arr[i];
        combination(arr, aux, i+1, end, index+1, r);
        while (arr[i] == arr[i+1])
             i++;
    }
}
int main()
{
    int arr[] = {1, 2, 2};
    int r = 2;
    int n = sizeof(arr)/sizeof(arr[0]);
    print(arr, n, r);
}

a) 1 2, 1 2,2 2,
b) 1 2, 2 1, 2 2,
c) 1 2, 2 2,
d) 1 2, 2 2, 2 1,

Answer: c
Clarification:The given code prints combination of the elements of a given array.But the difference here is that this code also handles duplicate elements due to which we get only 2 combinations instead of 3.

& Algorithms.

and Answers.

Data Structure Multiple Choice Questions & Answers (MCQs) on “Fibonacci using Recursion”.

1. Suppose the first fibonnaci number is 0 and the second is 1. What is the sixth fibonnaci number?
a) 5
b) 6
c) 7
d) 8

Answer: a
Clarification: The sixth fibonnaci number is 5.

2. Which of the following is not a fibonnaci number?
a) 8
b) 21
c) 55
d) 14

Answer: d
Clarification: 14 is not a fibonnaci number.

3. Which of the following option is wrong?
a) Fibonacci number can be calculated by using Dynamic programming
b) Fibonacci number can be calculated by using Recursion method
c) Fibonacci number can be calculated by using Iteration method
d) No method is defined to calculate Fibonacci number

Answer: d
Clarification: Fibonacci number can be calculated by using Dynamic Programming, Recursion method, Iteration Method.

4. Consider the following iterative implementation to find the nth fibonacci number?

int main()
{
    int  n = 10,i;
    if(n == 1)
        printf("0");
    else if(n == 2)
        printf("1");
    else
    {
        int a = 0, b = 1, c;
        for(i = 3; i <= n; i++)
        {
            c = a + b;
            ________;
			________;
        }
        printf("%d",c);
    }
   return 0;
}

Which of the following lines should be added to complete the above code?
a)

   c = b
   b = a

b)

   a = b
   b = c

c)

   b = c
   a = b

d)

   a = b
   b = a

Answer: b
Clarification: The lines “a = b” and “b = c” should be added to complete the above code.

5. Which of the following recurrence relations can be used to find the nth fibonacci number?
a) F(n) = F(n) + F(n – 1)
b) F(n) = F(n) + F(n + 1)
c) F(n) = F(n – 1)
d) F(n) = F(n – 1) + F(n – 2)

Answer: d
Clarification: The relation F(n) = F(n – 1) + F(n – 2) can be used to find the nth fibonacci number.

6. Consider the following recursive implementation to find the nth fibonacci number:

int fibo(int n)
{
     if(n == 1)
        return 0;
     else if(n == 2)
        return 1;
     return ________;
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

Which of the following lines should be inserted to complete the above code?
a) fibo(n – 1)
b) fibo(n – 1) + fibo(n – 2)
c) fibo(n) + fibo(n – 1)
d) fibo(n – 2) + fibo(n – 1)
Answer: b
Clarification: The line fibo(n – 1) + fibo(n – 2) should be inserted to complete the above code.

7. Consider the following recursive implementation to find the nth fibonnaci number:

int fibo(int n)
{
     if(n == 1)
        return 0;
     else if(n == 2)
        return 1;
     return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

Which of the following is the base case?
a) if(n == 1)
b) else if(n == 2)
c) return fibo(n – 1) + fibo(n – 2)
d) both if(n == 1) and else if(n == 2)

Answer: d
Clarification: Both if(n == 1) and else if(n == 2) are the base cases.

8. What is the time complexity of the following recursive implementation to find the nth fibonacci number?

int fibo(int n)
{
     if(n == 1)
        return 0;
     else if(n == 2)
        return 1;
     return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) O(1)
b) O(2*n)
c) O(n²)
d) O(2ⁿ)
Answer: d
Clarification: The time complexity of the above recursive implementation to find the nth fibonacci number is O(2ⁿ).

9. What is the space complexity of the following recursive implementation to find the nth fibonacci number?

int fibo(int n)
{
     if(n == 1)
        return 0;
     else if(n == 2)
        return 1;
     return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) O(1)
b) O(2*n)
c) O(n²)
d) O(2ⁿ)

Answer: a
Clarification: The space complexity of the above recursive implementation to find the nth fibonacci number is O(1).

10. What is the output of the following code?

int fibo(int n)
{
      if(n == 1)
        return 0;
      else if(n == 2)
        return 1;
      return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = -1;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) 0
b) 1
c) Compile time error
d) Runtime error

Answer: d
Clarification: Since negative numbers are not handled by the program, the function fibo() will be called infinite times and the program will produce a runtime error when the stack overflows.

11. What is the output of the following code?

int fibo(int n)
{
      if(n == 1)
        return 0;
      else if(n == 2)
        return 1;
      return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) 1
b) 2
c) 3
d) 5

Answer: c
Clarification: The program prints the 5th fibonacci number, which is 3.

12. How many times will the function fibo() be called when the following code is executed?

int fibo(int n)
{
      if(n == 1)
         return 0;
      else if(n == 2)
        return 1;
      return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) 5
b) 6
c) 8
d) 9

Answer: d
Clarification: The function fibo() will be called 9 times, when the above code is executed.

13. What is the output of the following code?

int fibo(int n)
{ 
      if(n == 1)
        return 0;
      else if(n == 2)
        return 1;
      return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 10;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) 21
b) 34
c) 55
d) 13

Answer: b
Clarification: The program prints the 10th fibonacci number, which is 34.

and Answers.

Data Structure Questions and Answers for Entrance exams on “Search an Element in a Linked List using Recursion”.

1. Which of the following methods can be used to search an element in a linked list?
a) Iterative linear search
b) Iterative binary search
c) Recursive binary search
d) Normal binary search

Answer: a
Clarification: Iterative linear search can be used to search an element in a linked list. Binary search can be used only when the list is sorted.

2. Consider the following code snippet to search an element in a linked list:

struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(int value)
{
      struct Node *temp = head->next;
      while(temp != 0)
      {
           if(temp->val == value)
              return 1;
           _________;
      }
      return 0;
}

Which of the following lines should be inserted to complete the above code?
a) temp = next
b) temp->next = temp
c) temp = temp->next
d) return 0

Answer: c
Clarification: The line “temp = temp->next” should be inserted to complete the above code.

3. What does the following code do?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(int value)
{
      struct Node *temp = head->next;
      while(temp != 0)
      {
           if(temp->val == value)
              return 1;
           temp = temp->next;
      }
      return 0;
}
int main()
{
      int arr[5] = {1,2,3,4,5};
      int n = 5,i;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      struct Node *temp;
      temp = head;
      for(i=0; i<n; i++)
      {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
      }
      int ans = linear_search(60);
      if(ans == 1)
      printf("Found");
      else
      printf("Not found");
      return 0;
}

a) Finds the index of the first occurrence of a number in a linked list
b) Finds the index of the last occurrence of a number in a linked list
c) Checks if a number is present in a linked list
d) Checks whether the given list is sorted or not
View Answer

Answer: c
Clarification: The above code checks if a number is present in a linked list.

4. What is the output of the following code?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(int value)
{
      struct Node *temp = head->next;
      while(temp != 0)
      {
           if(temp->val == value)
             return 1;
           temp = temp->next;
      }
      return 0;
}
int main()
{
     int arr[5] = {1,2,3,4,5};
     int n = 5,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     for(i=0; i<n; i++)
     {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
     }
     int ans = linear_search(-1);
     if(ans == 1)
     printf("Found");
     else
     printf("Not found");
     return 0;
}

a) Found
b) Not found
c) Compile time error
d) Runtime error
View Answer

Answer: b
Clarification: Since the number -1 is not present in the linked list, the program prints not found.

5. What is the time complexity of the following implementation of linear search on a linked list?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(int value)
{
      struct Node *temp = head->next;
      while(temp != 0)
      {
           if(temp->val == value)
             return 1;
           temp = temp->next;
      }
      return 0;
}
int main()
{
     int arr[5] = {1,2,3,4,5};
     int n = 5,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     for(i=0; i<n; i++)
     {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
     }
     int ans = linear_search(-1);
     if(ans == 1)
     printf("Found");
     else
     printf("Not found");
     return 0;
}

a) O(1)
b) O(n)
c) O(n²)
d) O(n³)
View Answer

Answer: b
Clarification: The time complexity of the above implementation of linear search on a linked list is O(n).

6. What is the output of the following code?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(int value)
{
      struct Node *temp = head->next;
      while(temp -> next != 0)
      {
            if(temp->val == value)
            return 1;
            temp = temp->next;
      }
      return 0;
}
int main()
{
     int arr[6] = {1,2,3,4,5,6};
     int n = 6,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     for(i=0; i<n; i++)
     {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
     }
     int ans = linear_search(60);
     if(ans == 1)
       printf("Found");
     else
       printf("Not found");
     return 0;
}

a) Found
b) Not found
c) Compile time error
d) Runtime error

Answer: b
Clarification: The condition in the while loop “temp->next == 0”, checks if the current element is the last element. If the current element is the last element, the value of the current element is not compared with the value to be searched. So, even though the number 6 is present in the linked list, it will print not found.

7. Can binary search be applied on a sorted linked list in O(Logn) time?
a) No
b) Yes

Answer: a
Clarification: Since linked list doesn’t allow random access, binary search cannot be applied on a sorted linked list in O(Logn) time.

8. What will be time complexity when binary search is applied on a linked list?
a) O(1)
b) O(n)
c) O(n²)
d) O(n³)

Answer: b
Clarification: The time complexity will be O(n) when binary search is applied on a linked list.

9. Consider the following recursive implementation of linear search on a linked list:

struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(struct Node *temp,int value)
{
      if(temp == 0)
         return 0;
      if(temp->val == value)
         return 1;
      return _________;
}

Which of the following lines should be inserted to complete the above code?
a) 1
b) 0
c) linear_search(temp, value)
d) linear_search(temp->next, value)
Answer: d
Clarification: The line “linear_search(temp->next, value)”, should be inserted to complete the above code.

10. What is the output of the following code?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(struct Node *temp,int value)
{
      if(temp == 0)
         return 0;
      if(temp->val == value)
         return 1;
      return linear_search(temp->next, value);
}
int main()
{
     int arr[6] = {1,2,3,4,5,6};
     int n = 6,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     for(i=0; i<n; i++)
     {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
     }
     int ans = linear_search(head->next,6);
     if(ans == 1)
       printf("Found");
     else
       printf("Not found");
     return 0;
}

a) Found
b) Not found
c) Compile time error
d) Runtime error

Answer: a
Clarification: Since the element 6 is present in the linked list, the program prints “Found”.

11. How many times is the function linear_search() called when the following code is executed?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(struct Node *temp,int value)
{
      if(temp == 0)
         return 0;
      if(temp->val == value)
         return 1;
      return linear_search(temp->next, value);
}
int main()
{
     int arr[6] = {1,2,3,4,5,6};
     int n = 6,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     for(i=0; i<n; i++)
     {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
     }
     int ans = linear_search(head->next,6);
     if(ans == 1)
       printf("Found");
     else
       printf("Not found");
    return 0;
}

a) 5
b) 6
c) 7
d) 8

Answer: b
Clarification: The function linear_search() is called 6 times when the above code is executed.

12. What is the time complexity of the following recursive implementation of linear search?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(struct Node *temp,int value)
{
      if(temp == 0)
         return 0;
      if(temp->val == value)
         return 1;
      return linear_search(temp->next, value);
}
int main()
{
     int arr[6] = {1,2,3,4,5,6};
     int n = 6,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     for(i=0; i<n; i++)
     {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
     }
     int ans = linear_search(head->next,6);
     if(ans == 1)
       printf("Found");
     else
       printf("Not found");
    return 0;
}

a) O(1)
b) O(n)
c) O(n²)
d) O(n³)

Answer: b
Clarification: The time complexity of the above recursive implementation of linear search is O(n).