ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
What is the auxiliary space requirement of the jump search?
O(n)
O(log n)
O(n^{1/2})
O(1)
Jump search does not require any additional space for searching the required element. Thus its auxiliary space requirement will be O(1).
What is the value of jump taken for maximum efficiency while implementing jump search?
n/2
n^{2}
n^{1/2}
log n
Total number of comparisons required will be n/k + k-1 in worst case. This function will be minimum for k=n^{1/2}. So this value of jump will be the best for implementing jump search.
What will be the maximum number of comparisons that can be made in jump search algorithm (assuming k to be blocks jumped)?
k
n/k
k-1
k-1
Worst case occurs when the element being searched is present just after the element that has been compared while making the last jump. So, in this case k-1 comparisons will have to be made.
How many jumps will be made in the worst case of jump search(let block jumped =k)?
n*k
n/k
k/n
n+k
Worst case occurs when the value to be searched is in the last section of the array. So, in this case the number of jumps will be n/k.
Which of the following step is taken after finding an element having value greater than the element being searched in jump search?
linear search takes place in the forward direction
linear search takes place in the backward direction
binary search takes place in the forward direction
binary search takes place in a backward direction
First an element having value greater than the element being searched is found. After this linear search is performed in a backward direction.
Jumps are made in the jump search algorithm until ___________
element having value less than that of the required element is found
element having value equal to the median of values of the array is found
element having value greater than that of the required element is found
middle element is found equal to the element being searched
In jump search algorithm jumps are made until element having value greater than the value of element being searched is found. After this linear search is performed in backwards direction.
Jump 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 64 elements
array should be partially sorted
Jump sort requires the input array to be sorted. The algorithm would fail to give the correct result if array is not sorted.
What are the updated values of high and low in the array if the element being searched is lower than the value at calculated index in interpolation search (pos = current position)
low = pos + 1, high remains unchanged
high = pos - 1, low remains unchanged
low = low +1, high = high - 1
low = pos +1, high = pos - 1
When the element being searched is lower than the value at the calculated position then in that case we update high and low remains unaltered. Updated value of high is high = pos - 1.
What are the updated values of high and low in the array if the element being searched is greater than the value at calculated index in interpolation search (pos = current position)
low = pos + 1, high remains unchanged
high = pos - 1, low remains unchanged
low = low +1, high = high - 1
low = pos +1, high = pos - 1
When the element being searched is greater than the value at the calculated position then in that case we update low and high remains unaltered. Updated value of low is low = pos + 1.
What is the formula used for calculating the position in interpolation search (x = element being searched, A[] = input array, low and high are the leftmost and rightmost index of A[] respectively)
((x - A[low]) * (high - low)) / (A[high] - A[low])
high + ((x - A[low]) * (high - low)) / (A[high] - A[low])
low + ((x - A[low]) * (high - low)) / (A[high] - A[low])
x + ((x - A[low]) * (high - low)) / (A[high] - A[low])
For calculating the position after each iteration in interpolation search we use the formula low + ((x - A[low]) * (high - low)) / (A[high] - A[low]). Then the value at the calculated position is compared with the element being searched.
Interpolation search has a better time complexity than exponential search for any given array.
True
False
The worst case time complexity of interpolation search and exponential search are O(n) and O(log n) respectively. So exponential search is better when the worst case scenario is considered.
Interpolation search is an in place algorithm.
True
False
Interpolation search has an auxiliary space complexity of O(1). So it qualifies as an in place algorithm.
Which of the following searching algorithm is fastest when the input array is not sorted but has uniformly distributed values?
jump search
linear search
binary search
interpolation search
Out of the given options linear search is the only searching algorithm which can be applied to arrays which are not sorted. It has a time complexity of O(n) in the worst case.
Which of the following searching algorithm is fastest when the input array is sorted but has non uniformly distributed values?
jump search
linear search
binary search
interpolation search
Interpolation search has a time complexity of O(n) when the array does not have uniformly distributed values. So in such a case binary search has the least time complexity out of the given options.
Which of the following searching algorithm is fastest when the input array is sorted and has uniformly distributed values?
jump search
exponential search
binary search
interpolation search
Interpolation search has a time complexity of O( log log n) when the array is sorted and has uniformly distributed values. It has the least time complexity out of the given options for such a case.
What is the time complexity of exponential search when the input array is sorted but the values are not uniformly distributed?
O(n^{1/2})
O(log log n)
O(n)
O(log n)
When an array has non uniformly distributed values then in that case the algorithm of interpolation search fails to work efficiently. As a result, it has a time complexity of O(n) in such a case.
What is the auxiliary space requirement of interpolation search?
O(n)
O(2^{n})
O(1)
O(log n)
Interpolation 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 interpolation search when the input array has uniformly distributed values and is sorted?
O(n)
O(log log n)
O(n log n)
O(log n)
Interpolation search goes to different positions in the array depending on the value being searched. It is an improvement over binary search and has a time complexity of O(log log n).
In which of the following case jump search performs better than interpolation search?
When array has uniformly distributed values but is not sorted
when array is sorted and has uniform distribution of values
when array is sorted but the values increases exponentially
when array is not sorted
In case of non uniform distribution of values the time complexity of interpolation search is O(n) whereas the average time complexity of jump search is O(n^{1/2}). So in such a case jump search has a better performance.
Interpolation search performs better than binary search when?
array has uniformly distributed values but is not sorted
array is sorted and has uniform distribution of values
array is sorted but the values are not uniformly distributed
array is not sorted
Interpolation search is an improvement over a binary search for the case when array is sorted and has uniformly distributed values. Binary search performs better when the values are not distributed uniformly.
