Data Structure Quiz on “Search an Element in an Array using Recursion – 2”.
1. What is the output of the following code?
#includeint recursive_search_num(int *arr, int num, int idx, int len) { if(idx == len) return -1; if(arr[idx] == num) return idx; return recursive_search_num(arr, num, idx+1, len); } int main() { int arr[8] ={-11,2,-3,0,3,5,-6,7},num = -2,len = 8; int indx = recursive_search_num(arr,num,0,len); printf("Index of %d is %d",num,indx); return 0; }
a) Index of -2 is 1
b) Index of -2 is 0
c) Index of -2 is -1
d) None of the mentioned
View Answer
Answer: c
Clarification: The program prints the index of the first occurrence of -2. Since, -2 doesn’t exist in the array, the program prints -1.
2. What does the following code do?
#includeint cnt = 0; int recursive_search_num(int *arr, int num, int idx, int len) { int cnt = 0; if(idx == len) return cnt; if(arr[idx] == num) cnt++; return cnt + recursive_search_num(arr, num, idx+1, len); } int main() { int arr[8] ={0,0,0,0,3,5,-6,7},num = 0,len = 8; int ans = recursive_search_num(arr,num,0,len); printf("%d",ans); return 0; }
a) Adds all the indexes of the number 0
b) Finds the first last occurrence of the number 0
c) Counts the number of occurrences of the number 0
d) None of the mentioned
View Answer
Answer: c
Clarification: The above code counts the number of occurrences of the number 0.
3. Consider the following recursive implementation of the binary search:
#includeint recursive_binary_search(int *arr, int num, int lo, int hi) { if(lo > hi) return -1; int mid = (lo + hi)/2; if(arr[mid] == num) return mid; else if(arr[mid] < num) __________; else hi = mid - 1; return recursive_binary_search(arr, num, lo, hi); } int main() { int arr[8] ={0,0,0,0,3,5,6,7},num = 7,len = 8; int indx = recursive_binary_search(arr,num,0,len-1); printf("Index of %d is %d",num,indx); return 0; }
Which of the following lines should be added to complete the above code? Answer: d 4. What is the output of the following code? a) Index of 7 is 4 Answer: c 5. What is the output of the following code? a) Index of 0 is 0 Answer: d 6. What is the time complexity of the above recursive implementation of binary search? Answer: c 7. In which of the below cases will the following code produce a wrong output? a) Array: {0,0,0,0,0,0} Search: -10 Answer: c 8. How many times is the function recursive_binary_search() called when the following code is executed? a) 0 9. What is the output of the following code? a) Index of 1 is 4
a) hi = mid – 1
b) mid = (lo + hi)/2
c) mid = lo – 1
d) lo = mid + 1
Clarification: The line “lo = mid + 1” should be added to complete the above code.#include
b) Index of 7 is 5
c) Index of 7 is 6
d) Index of 7 is 7
View Answer
Clarification: The program prints the index of number 7, which is 6.#include
b) Index of 0 is 1
c) Index of 0 is 2
d) Index of 0 is 3
View Answer
Clarification: In this case, when the function recursive_binary_search() is called for the first time we have: lo = 0 and hi = 7. So, the value of mid is:
mid = (lo + hi)/2 = (0 + 7)/2 = 3. Since, arr[mid] = arr[3] = 0, the function returns the value of mid, which is 3.
a) O(n)
b) O(2n)
c) O(logn)
d) O(n!)
Clarification: The time complexity of the above recursive implementation of binary search is O(logn).int recursive_binary_search(int *arr, int num, int lo, int hi)
{
if(lo > hi)
return -1;
int mid = (lo + hi)/2;
if(arr[mid] == num)
return mid;
else if(arr[mid] < num)
lo = mid + 1;
else
hi = mid - 1;
return recursive_binary_search(arr, num, lo, hi);
}
b) Array: {1,2,3,4,5} Search: 0
c) Array: {5,4,3,2,1} Search: 1
d) Array: {-5,-4,-3,-2,-1} Search: -1
Clarification: Since the array {5,4,3,2,1} is sorted in descending order, it will produce a wrong output.#include
b) 1
c) 2
d) 3
Answer: c
Clarification: The function recursive_binary_search() is called 2 times, when the above code is executed.#include
b) Index of 1 is 5
c) Index of 1 is -1
d) Index of 1 is 0
Answer: c
Clarification: Since the array is sorted in descending order, the above implementation of binary search will not work for the given array. Even though 1 is present in the array, binary search won’t be able to search it and it will produce -1 as an answer.