This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Recursive Insertion Sort”.
1. Which of the following is an advantage of recursive insertion sort over its iterative version?
a) it has better time complexity
b) it has better space complexity
c) it is easy to implement
d) it has no significant advantage
View Answer
Explanation: Recursive insertion sort has no significant advantage over iterative insertion sort. It is just a different way to implement the same.
2. Insertion sort is an online sorting algorithm.
a) true
b) false
View Answer
Explanation: Insertion sort does not require the entire input data in the beginning itself in order to sort the array. It rather creates a partial solution in every step, so future elements are not required to be considered. Hence it is an online sorting algorithm.
3. What will be the recurrence relation of the code of recursive insertion sort?
a) T(n) = 2T(n/2) + n
b) T(n) = 2T(n/2) + c
c) T(n) = T(n-1) + n
d) T(n) = T(n-1) + c
View Answer
Explanation: The recurrence relation of the code of recursive insertion sort is T(n) = T(n-1) + n. It can be solved by the method of substitution and is found to be equal to n2.
4. Which of the following sorting algorithm is stable?
a) Selection sort
b) Quick sort
c) Insertion sort
d) Heap sort
View Answer
Explanation: Out of the given options insertion sort is the only algorithm which is stable. It is because the elements with identical values appear in the same order in the output array as they were in the input array.
5. Which of the following is a variant of insertion sort?
a) selection sort
b) shell sort
c) odd-even sort
d) stupid sort
View Answer
Explanation: Shell sort is a variation of insertion sort. It has a better running time in practical applications.
6. Recursive insertion sort is a comparison based sort.
a) True
b) False
View Answer
Explanation: In insertion sort, we need to compare elements in order to find the minimum element in each iteration. So we can say that it uses comparisons in order to sort the array. Thus it qualifies as a comparison based sort.
7. What is the average case time complexity of recursive insertion sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Explanation: The overall recurrence relation of recursive insertion sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n2).
8. What is the best case time complexity of recursive insertion sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Explanation: The best case time complexity of recursive insertion sort is O(n). It occurs in the case when the input is already/almost sorted.
9. What is the worst case time complexity of recursive insertion sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Explanation: The overall recurrence relation of recursive insertion sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n2).
10. How many swaps will be required in the worst case to sort an array having n elements using binary insertion sort?
a) n
b) 1
c) n * log n
d) log n
View Answer
Explanation: In a normal insertion sort at most n comparisons are required to sort the array. But if we also implement the concept of a binary sort in insertion sort then we can sort by having log n comparisons only.
11. What will be the base case for the code of recursive insertion sort ?
a)
if(n < 1) return;
b)
if(n == 0) return;
c)
if(n <= 1) return;
d)
If(n == 2) return;View Answer
Explanation: The most appropriate condition for the base case of recursive insertion sort is when n is less than or equal 1 then return. It is because we know that an array with only 1 element is always sorted.
12. What is the auxiliary space complexity of recursive insertion sort?
a) O(n)
b) O(1)
c) O(n log n)
d) O(n2)
View Answer
Explanation: The auxiliary space required by recursive insertion sort is O(1). So it qualifies as an in place sorting algorithm.
13. Which of the following is an adaptive sorting algorithm?
a) recursive insertion sort
b) merge sort
c) heap sort
d) selection sort
View Answer
Explanation: Insertion sort is an adaptive algorithm. It is because the time complexity of the algorithm improves when the input array is almost sorted.
14. Which of the following sorting algorithm is in place?
a) recursive insertion sort
b) merge sort
c) radix sort
d) counting sort
View Answer
Explanation: Out of the given options recursive insertion sort is the only algorithm which is in place. It is because the auxiliary space required by recursive bubble sort is O(1).
15.Choose the correct function for recursive insertion sort?
a)
void RecInsertionSort(int arr[], int n) { if (n <= 1) return; RecInsertionSort( arr, n-1 ); int key = arr[n-1]; int j = n-2; while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j--; } arr[j+1] = key; }
b)
void RecInsertionSort(int arr[], int n) { if (n < 1) return; RecInsertionSort( arr, n-1 ); int key = arr[n-1]; int j = n-2; while (j >= 0 || arr[j] > key) { arr[j+1] = arr[j]; j--; } arr[j] = key; }
c)
void RecInsertionSort(int arr[], int n) { if (n <1) return; RecInsertionSort( arr, n-1 ); int key = arr[n-1]; int j = n-2; while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j--; } arr[j] = key; }
d)
void RecInsertionSort(int arr[], int n) { if (n <= 1) return; RecInsertionSort( arr, n-1 ); int key = arr[n-1]; int j = n-1; while (j >= 0 || arr[j] > key) { arr[j+1] = arr[j]; j--; } arr[j+1] = key; }
Explanation: The base case of recursive bubble sort should be when n equal or less than 1 then return. Also we need to insert the element being chosen as key at its correct position in the sorted array to its left. All this needs to be done in a recursive code.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, 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]
- Check Computer Science Books
- Check Design and Analysis of Algorithms Books
- Practice Programming MCQs
- Apply for Computer Science Internship
- Practice Computer Science MCQs
