ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
Interpolation search is a variation of?
Linear search
Binary search
Jump search
Exponential search
Interpolation search is a variation of binary search which gives the best result when the array has uniformly distributed values. Interpolation search goes to different positions depending on the value being searched whereas binary search always goes to the middle element.
Which of the following is the most desirable condition for interpolation search?
array should be sorted
array should not be sorted but the values should be uniformly distributed
array should have a less than 64 elements
array should be sorted and the values should be uniformly distributed
Desirable condition for interpolation search is that the array should be sorted and the values should be uniformly distributed. The algorithm would fail to give the correct result if array is not sorted.
Which of the following is not an alternate name of exponential search?
Logarithmic search
Doubling search
Galloping search
Struzik search
Logarithmic search is not an alternate name of the exponential search. Some alternate names of exponential search are Doubling search, Galloping search and Struzik search.
Choose the incorrect statement about exponential search from the following.
Exponential search is an in place algorithm
Exponential search has a greater time complexity than binary search
Exponential search performs better than binary search when the element being searched is present near the starting point of the array
Jump search has a greater time complexity than an exponential search
Time complexity of exponential search and binary search are the same. But exponential search performs better than binary search when the element being searched is present near the starting point of the array.
Exponential search performs better than binary search when the element being searched is present near the starting point of the array.
True
False
Exponential search first finds the range where binary search needs to be applied. So when the element is present near the starting point of the array then exponential search performs better than standard binary search.
Jump search has a better time complexity than the exponential search.
True
False
The worst case time complexity of jump search and exponential searches are O(n1/2) and O(log n) respectively. So exponential search is better in terms of time complexity.
Best case of the exponential search will have time complexity of?
O(1)
O(n)
O(log n)
O(n log n)
Best case of the exponential search will be when the first element of the array is the element that is being searched. In this case, only one comparison will be required. Thus it will have a time complexity of O(1).
In which of the following case jump search will be preferred over exponential search?
jumping backwards takes significantly more time than jumping forward
jumping forward takes significantly more time than jumping backwards
when the given array is very large in size
when the given array is very small in size
Jump search only needs to jump backwards once, while an exponential search can jump backwards up to log n times. Thus jump search will be preferred if jumping backwards is expensive.
Which of the following searching algorithm is fastest?
jump search
exponential search
linear search
all are equally fast
Exponential search has the least time complexity (equal to log n) out of the given searching algorithms. This makes exponential search preferable in most cases.
What is the auxiliary space requirement of the exponential sort when used with recursive binary search?
O(n)
O(2^{n})
O(1)
O(log n)
Exponential search requires an auxiliary space of log n when used with recursive binary search. This space is required for the recursion call stack space.
What is the auxiliary space requirement of an exponential sort when used with iterative binary search?
O(n)
O(2^{n})
O(1)
O(log n)
Exponential search does not require any auxiliary space for finding the element being searched. So it has a constant auxiliary space O(1).
What is the time complexity of exponential sort?
O(n)
O(2n)
O(n log n)
O(log n)
In exponential search, we first find a range where the required elements should be present in the array. Then we apply binary search in this range. This takes O(log n) time in the worst case.
Exponential search has ____________
neither an exponential space complexity nor exponential time complexity
exponential time complexity but a linear space complexity
exponential space complexity but a linear time complexity
both exponential time and space complexity
Exponential search has neither an exponential space complexity nor exponential time complexity. It is named exponential search because it searches for an element in an exponential manner.
Which of the following searching algorithm is used with exponential sort after finding the appropriate range?
Linear search
Binary search
Jump search
Fibonacci Search
In exponential search, we first find a range where the required elements should be present in the array. Then we apply binary search in this range.
Exponential search algorithm requires which of the following condition to be true?
array should be sorted
array should have not be sorted
array should have a less than 128 elements
array should be partially sorted
Exponential sort requires the input array to be sorted. The algorithm would fail to give the correct result if array is not sorted.
Which of the following false about Jump Search?
Jump Search is better than Linear Search
Useful when jumping back is more costly than jumping forward
Jump Search is worse than Binary Search
Jump search starts from the index 0 even though specified index is k
Linear search has O(n) complexity and Binary search has O(logn) complexity, in Jump search you have to jump backwards only once, hence it is preferable if jumping backwards is costly. Jump search starts from index k (specified index) and searches for the element. It won't start searching from index 0.
How can Jump Search be improved?
Start searching from the end
Begin from the kth item, where k is the step size
Cannot be improved
Step size should be other than sqrt(n)
This gives a very slight improvement as you are skipping the first k elements.
Given, arr = {1,3,5,6,7,9,14,15,17,19} (key = 17 and delta = {5),3,1,0} How many key comparisons are made?(exclude the comparison used to decide the left or right sub array)
4
3
5
6
Tracing with the above code, comparison #1: i=4, comparison #2: i=7, comparison #3: i=8
What is the time complexity of uniform binary search?
O(nlogn)
O(logn)
O(n)
O(n^{2})
With every iteration we are dividing the array into two parts(though not equal halves), the complexity remains same as the normal binary search.
Given delta[4] is a global array and number of elements in the sorted array is 10, what are the values in the delta array?
4, 3, 1, 0
5, 3, 1, 0
4, 2, 1, 1
5, 2, 1, 1
Trace with respect to the make_delta function, always note that the last element is always 0.
