Count Inversion Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Count Inversion”.

1. What does the number of inversions in an array indicate?
a) mean value of the elements of array
b) measure of how close or far the array is from being sorted
c) the distribution of values in the array
d) median value of the elements of array
View Answer

2. How many inversions does a sorted array have?
a) 0
b) 1
c) 2
d) cannot be determined
View Answer

3. What is the condition for two elements arr[i] and arr[j] to form an inversion?
a) arr[i]<arr[j]
b) i < j
c) arr[i] < arr[j] and i < j
d) arr[i] > arr[j] and i < j
View Answer

4. Under what condition the number of inversions in an array are maximum?
a) when the array is sorted
b) when the array is reverse sorted
c) when the array is half sorted
d) depends on the given array
View Answer

5. Under what condition the number of inversions in an array are minimum?
a) when the array is sorted
b) when the array is reverse sorted
c) when the array is half sorted
d) depends on the given array
View Answer

6. How many inversions are there in the array arr = {1,5,4,2,3}?
a) 0
b) 3
c) 4
d) 5
View Answer

7. Which of the following form inversion in the array arr = {1,5,4,2}?
a) (5,4), (5,2)
b) (5,4), (5,2), (4,2)
c) (1,5), (1,4), (1,2)
d) (1,5)
View Answer

8. Choose the correct function from the following which determines the number of inversions in an array?
a)

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i ; j < n; j++) 
			if (arr[i] >= arr[j]) 
				count++; 
 
	return count; 
}

b)

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i + 1; j < n; j++) 
			if (arr[i] > arr[j]) 
				count++; 
 
	return count; 
}

c)

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i + 1; j < n; j++) 
			if (arr[i] > arr[j]) 
				count++; 
 
	return count + 1; 
}

d)

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i + 1; j < n; j++) 
			if (arr[i] < arr[j]) 
				count++; 
 
	return count + 1; 
}

9. What is the time complexity of the following code that determines the number of inversions in an array?

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i + 1; j < n; j++) 
			if (arr[i] > arr[j]) 
				count++; 
 
	return count; 
}

a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)
View Answer

10. The time complexity of the code that determines the number of inversions in an array using merge sort is lesser than that of the code that uses loops for the same purpose.
a) true
b) false
View Answer

11. What is the time complexity of the code that uses merge sort for determining the number of inversions in an array?
a) O(n²)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer

12. What is the time complexity of the code that uses self balancing BST for determining the number of inversions in an array?
a) O(n²)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer

13. The time complexity of the code that determines the number of inversions in an array using self balancing BST is lesser than that of the code that uses loops for the same purpose.
a) true
b) false
View Answer

14. What is the space complexity of the code that uses merge sort for determining the number of inversions in an array?
a) O(n)
b) O(log n)
c) O(1)
d) O(n log n)
View Answer

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]