Count Inversion Multiple Choice Questions and Answers (MCQs)

Uncategorized

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

1. How many inversions are there in the array arr = {1,5,4,2,3}?
A) 0
B) 3
C) 4
D) 5

Explanation: An inversion requires the conditions arr[i]>arr[j] and ij. As a result, the array has five inversions.

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

Explanation: An inversion requires the conditions arr[i]>arr[j] and ij. As a result, the array has three inversions. There are (5,4), (5,2), and (5,3). (4,2).

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


Explanation: We use a nested loop to calculate the number of inversions by comparing the value of each element to all the elements that come after it. The number of inversions is then counted, and the count is returned to the main function.

4. 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(n2)
D) O(log n)

Explanation: The provided code has an O time complexity (n2). The existence of a nested loop is the reason for this.

5. 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

Explanation: The time complexity of the code that uses merge sort to calculate the number of inversions in an array is O(n log n), which is less than that of the code that uses loops.

6. What is the time complexity of the code that uses merge sort for determining the number of inversions in an array?
A) O(n2)
B) O(n)
C) O(log n)
D) O(n log n)

Explanation: To measure the number of inversions in an array, the merge sort code is slightly changed. As a result, merge sort’s time complexity is unchanged, and the time complexity is O. (n log n).

7. What is the time complexity of the code that uses self balancing BST for determining the number of inversions in an array?
A) O(n2)
B) O(n)
C) O(log n)
D) O(n log n)

Explanation: When using a self-balancing BST like an AVL tree to measure the number of inversions in an array, the time complexity is O(n log n), since AVL insert takes O(log n) time.

8. 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

Explanation: The time complexity of the code that uses self-balancing BST to calculate the number of inversions in an array is O(n log n), which is less than the processing time of the code that uses loops.

9. 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)

Explanation: The code’s necessary space complexity will be O. (n). It’s the same as the regular merge sort code’s space complexity.

10. 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

Explanation: The number of inversions in an array shows how close or far it is to being fully sorted. If the amount of variations is zero, the list is sorted.

11. How many inversions does a sorted array have?
A) 0
B) 1
C) 2
D) cannot be determined

Explanation: When an array is sorted, it is impossible for the array to be inverted. Since arr[i]>arr[j] is a required condition for an inversion, and gan.

12. 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

Explanation: The condition arr[i] > arr[j] and I j is needed for two elements to form an inversion. The number of inversions in an array shows how close or far it is to being fully sorted.

13. 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

Explanation: When an array is reverse sorted, the number of inversions in it is at its limit. Since arr[i]>arr[j] is a required condition for an inversion, and ij.

14. 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

Explanation: When an array is sorted, the number of inversions in it is minimised. Since arr[i]>arr[j] is a required condition for an inversion, and ij.

The array’s inversion count shows how far (or close) it is from being sorted. The inversion count is 0 if the array is already sorted; however, the inversion count is maximum if the array is sorted in reverse order. The number of changes needed to transform an array into its sorted form is indicated by its inversions. When an array is already sorted, it requires no inversions; however, if the array is inverted, the number of inversions needed is the limit.

Leave a Reply

Your email address will not be published. Required fields are marked *