250+ TOP MCQs on Square Root Decomposition and Answers

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Square Root Decomposition”.

1. What is the purpose of using square root decomposition?
a) to reduce the time complexity of a code
b) to increase the space complexity of a code
c) to reduce the space complexity of a code
d) to reduce the space and time complexity of a code

Answer: a
Clarification: Square decomposition is mainly used in competitive programming to optimize code. It reduces the time complexity by a factor of √n.

2. By what factor time complexity is reduced when we apply square root decomposition to a code?
a) n
b) √n
c) n2
d) n-1/2

Answer: b
Clarification: In square root decomposition a given array is decomposed into small parts each of size √n. This reduces the time complexity of the code by a factor of √n.

3. What will be the worst case time complexity of finding the sum of elements in a given range of (l,r) in an array of size n?
a) O(n)
b) O(l+r)
c) O(l-r)
d) O(r-l)
View Answer

Answer: a
Clarification: For a given array of size n we have to traverse all n elements in the worst case. In such a case l=0, r=n-1 so the time complexity will be O(n).

4. What will be the worst case time complexity of finding the sum of elements in a given range of (l,r) in an array of size n when we use square root optimization?
a) O(n)
b) O(l+r)
c) O(√n)
d) O(r-l)

Answer: c
Clarification: When we use square root optimization we decompose the given array into √n chunks each of size √n. So after calculating the sum of each chunk individually, we require to iterate only 3*√n times to calculate the sum in the worst case.

5. Total how many iterations are required to find the sum of elements in a given range of (l,r) in an array of size n when we use square root optimization?
a) √n
b) 2*√n
c) 3*√n
d) n*√n
Answer: c
Clarification: After calculating the sum of each chunk individually we require to iterate only 3*√n times to calculate the sum in the worst case. It is because two of the √n factors consider the worst case time complexity of summing elements in the first and last block. Whereas the third √n considers the factor of summing the √n chunks.

6. What will be the time complexity of update query operation in an array of size n when we use square root optimization?
a) O(√n)
b) O(n)
c) O(1)
d) O(n2)
Answer:c
Clarification: The time complexity of query operation remains the same in both square root optimized code and non optimized code. We simply find the chunk in which the update requires to be performed and then add the new updated value at the desired index.

7. Square root decomposition technique is only applicable when the number of indices in an array is a perfect square.
a) true
b) false

Answer: b
Clarification: Square root decomposition technique can be applied to an array with any number of indices. It does not require this number to be a perfect square.

8. What will be the worst case time complexity of code to find sum in given query range (l,r) in an array of size n with q number of such queries?
a) O(n)
b) O(q)
c) O(n*q)
d) O(n+q)

Answer: c
Clarification: For finding the result of one query the worst case time complexity will be n. So for q queries the time complexity will be O(q*n). This can be reduced by using square root optimization.

9. What will be the worst case time complexity of code to find sum in given query range (l,r) in an array of size n with q number of such queries when we apply MO’s algorithm?
a) O(n*q)
b) O(n)
c) O((q+n)√n)
d) O(q*√n)
Answer: c
Clarification: Mo’s algorithm requires O(q*√n) + O(n*√n) time for processing all the queries. It is better than the naive solution where O(n*q) time is required.

10. Mo’s algorithm can only be used for problems where the query can be calculated from the result of the previous query.
a) true
b) false
Answer: a
Clarification: Mo’s algorithm uses the result of the previous query in order to compute the result of the given query. It cannot be implemented where such a scenario is not possible.

11. What will be the time complexity of the code to find a minimum element from an array of size n and uses square root decomposition(exclude pre processing time)?
a) O(√n)
b) O(n)
c) O(1)
d) O(n2)

Answer: a
Clarification: For finding the minimum element in a given array of size n using square root decomposition we first divide the array into √n chunks and calculate the result for them individually. So for a given query, the result of middle blocks has to be calculated along with the extreme elements. This takes O(√n) time in the worst case.

250+ TOP MCQs on Insertion Sort MCQs and Answers

Data Structures & Algorithms Multiple Choice Questions on “Insertion Sort”.

1. How many passes does an insertion sort algorithm consist of?
a) N
b) N-1
c) N+1
d) N2

Answer: b
Clarification: An insertion algorithm consists of N-1 passes when an array of N elements is given.

2. Which of the following algorithm implementations is similar to that of an insertion sort?
a) Binary heap
b) Quick sort
c) Merge sort
d) Radix sort

Answer: a
Clarification: Insertion sort is similar to that of a binary heap algorithm because of the use of temporary variable to swap.

3. What is the average case running time of an insertion sort algorithm?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)

Answer: d
Clarification: The average case analysis of a tight bound algorithm is mathematically achieved to be O(N2).

4. Any algorithm that sorts by exchanging adjacent elements require O(N2) on average.
a) True
b) False
View Answer

Answer: a
Clarification: Each swap removes only one inversion, so O(N2) swaps are required.

5. What is the average number of inversions in an array of N distinct numbers?
a) N(N-1)/4
b) N(N+1)/2
c) N(N-1)/2
d) N(N-1)/3

Answer: a
Clarification: The total number of pairs in a list L is N(N-1)/2. Thus, an average list has half this amount, or N(N-1)/4 inversions.

6. What is the running time of an insertion sort algorithm if the input is pre-sorted?
a) O(N2)
b) O(N log N)
c) O(N)
d) O(M log N)

Answer: c
Clarification: If the input is pre-sorted, the running time is O(N), because the test in the inner for loop always fails immediately and the algorithm will run quickly.

7. What will be the number of passes to sort the elements using insertion sort?
14, 12,16, 6, 3, 10
a) 6
b) 5
c) 7
d) 1

Answer: b
Clarification: The number of passes is given by N-1. Here, N=6. Therefore,
6-1=5 passes.

8. For the following question, how will the array elements look like after second pass?
34, 8, 64, 51, 32, 21
a) 8, 21, 32, 34, 51, 64
b) 8, 32, 34, 51, 64, 21
c) 8, 34, 51, 64, 32, 21
d) 8, 34, 64, 51, 32, 21

Answer: d
Clarification: After swapping elements in the second pass, the array will look like, 8, 34, 64, 51, 32, 21.

9. Which of the following real time examples is based on insertion sort?
a) arranging a pack of playing cards
b) database scenarios and distributes scenarios
c) arranging books on a library shelf
d) real-time systems
View Answer

Answer: a
Clarification: Arranging a pack of cards mimics an insertion sort. Database scenario is an example for merge sort, arranging books is a stack and real-time systems uses quick sort.

10. In C, what are the basic loops required to perform an insertion sort?
a) do- while
b) if else
c) for and while
d) for and if

Answer: c
Clarification: To perform an insertion sort, we use two basic loops- an outer for loop and an inner while loop.

11. Binary search can be used in an insertion sort algorithm to reduce the number of comparisons.
a) True
b) False

Answer: a
Clarification: Binary search can be used in an insertion sort algorithm to reduce the number of comparisons. This is called a Binary insertion sort.

12. Which of the following options contain the correct feature of an insertion sort algorithm?
a) anti-adaptive
b) dependable
c) stable, not in-place
d) stable, adaptive

Answer: d
Clarification: An insertion sort is stable, adaptive, in-place and incremental in nature.

13. Which of the following sorting algorithms is the fastest for sorting small arrays?
a) Quick sort
b) Insertion sort
c) Shell sort
d) Heap sort

Answer: b
Clarification: For sorting small arrays, insertion sort runs even faster than quick sort. But, it is impractical to sort large arrays.

14. For the best case input, the running time of an insertion sort algorithm is?
a) Linear
b) Binary
c) Quadratic
d) Depends on the input

Answer: a
Clarification: The best case input for an insertion sort algorithm runs in linear time and is given by O(N).

15. Which of the following examples represent the worst case input for an insertion sort?
a) array in sorted order
b) array sorted in reverse order
c) normal unsorted array
d) large array

Answer: b
Clarification: The worst case input for an insertion sort algorithm will be an array sorted in reverse order and its running time is quadratic.

250+ TOP MCQs on Introsort and Answers

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(n2)
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(n2)
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(n2)
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(n2)
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) n2
c) n log(n)
d) 2 log (n)

Answer: d
Clarification: Quicksort has a worst case time complexity of O(n2) 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.

250+ TOP MCQs on Bucket Sort (Uniform Keys) and Answers

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(n2)
d) O(n log n)

Answer: c
Clarification: Time complexity of bucket sort is O(n2) 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(n2)
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(n2)
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.

250+ TOP MCQs on Generating Combinations and Answers

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(n2)
c) O(n log n)
d) O(2n)

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(2n).

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.

250+ TOP MCQs on Prim’s Algorithm and Answers Quiz Exam

Data Structures & Algorithms Multiple Choice Questions on “Prim’s Algorithm”.

1. Which of the following is true?
a) Prim’s algorithm initialises with a vertex
b) Prim’s algorithm initialises with a edge
c) Prim’s algorithm initialises with a vertex which has smallest edge
d) Prim’s algorithm initialises with a forest

Answer: a
Clarification: Steps in Prim’s algorithm: (I) Select any vertex of given graph and add it to MST (II) Add the edge of minimum weight from a vertex not in MST to the vertex in MST; (III) It MST is complete the stop, otherwise go to step (II).

2. Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?
a) O(log V)
b) O(V2)
c) O(E2)
d) O(V log E)

Answer: b
Clarification: Use of adjacency matrix provides the simple implementation of the Prim’s algorithm. In Prim’s algorithm, we need to search for the edge with a minimum for that vertex. So, worst case time complexity will be O(V2), where V is the number of vertices.

3. Prim’s algorithm is a ______
a) Divide and conquer algorithm
b) Greedy algorithm
c) Dynamic Programming
d) Approximation algorithm

Answer: b
Clarification: Prim’s algorithm uses a greedy algorithm approach to find the MST of the connected weighted graph. In greedy method, we attempt to find an optimal solution in stages.

4. Prim’s algorithm resembles Dijkstra’s algorithm.
a) True
b) False

Answer: a
Clarification: In Prim’s algorithm, the MST is constructed starting from a single vertex and adding in new edges to the MST that link the partial tree to a new vertex outside of the MST. And Dijkstra’s algorithm also rely on the similar approach of finding the next closest vertex. So, Prim’s algorithm resembles Dijkstra’s algorithm.

5. Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.
a) True
b) False
View Answer

Answer: a
Clarification: Prim’s algorithm and Kruskal’s algorithm perform equally in case of the sparse graphs. But Kruskal’s algorithm is simpler and easy to work with. So, it is best suited for sparse graphs.

6. Prim’s algorithm is also known as __________
a) Dijkstra–Scholten algorithm
b) Borůvka’s algorithm
c) Floyd–Warshall algorithm
d) DJP Algorithm

Answer: d
Clarification: The Prim’s algorithm was developed by Vojtěch Jarník and it was latter discovered by the duo Prim and Dijkstra. Therefore, Prim’s algorithm is also known as DJP Algorithm.

7. Prim’s algorithm can be efficiently implemented using _____ for graphs with greater density.
a) d-ary heap
b) linear search
c) fibonacci heap
d) binary search

Answer: a
Clarification: In Prim’s algorithm, we add the minimum weight edge for the chosen vertex which requires searching on the array of weights. This searching can be efficiently implemented using binary heap for dense graphs. And for graphs with greater density, Prim’s algorithm can be made to run in linear time using d-ary heap(generalization of binary heap).

8. Which of the following is false about Prim’s algorithm?
a) It is a greedy algorithm
b) It constructs MST by selecting edges in increasing order of their weights
c) It never accepts cycles in the MST
d) It can be implemented using the Fibonacci heap

Answer: b
Clarification: Prim’s algorithm can be implemented using Fibonacci heap and it never accepts cycles. And Prim’s algorithm follows greedy approach. Prim’s algorithms span from one vertex to another.