Interpolation in Data Structure And Algorithm: Practice MCQ Questions and Answers

15 practice sets · Page 1 of 1

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

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

Answer and explanation

Correct Answer: B — high = pos - 1, low remains unchanged

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.

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

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

Answer and explanation

Correct Answer: A — low = pos + 1, high remains unchanged

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.

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

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])

Answer and explanation

Correct Answer: C — low + ((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.

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

Interpolation search has a better time complexity than exponential search for any given array.

True

False

Answer and explanation

Correct Answer: B — 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.

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

Interpolation search is an in place algorithm.

True

False

Answer and explanation

Correct Answer: A — True

Interpolation search has an auxiliary space complexity of O(1). So it qualifies as an in place algorithm.

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

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

Answer and explanation

Correct Answer: B — linear 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.

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

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

Answer and explanation

Correct Answer: C — binary 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.

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

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

Answer and explanation

Correct Answer: D — 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.

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

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)

Answer and explanation

Correct Answer: C — O(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.

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

10.

What is the auxiliary space requirement of interpolation search?

O(n)

O(2^{n})

O(1)

O(log n)

Answer and explanation

Correct Answer: C — O(1)

Interpolation search does not require any auxiliary space for finding the element being searched. So it has a constant auxiliary space O(1).

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

11.

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)

Answer and explanation

Correct Answer: B — O(log 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).

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

12.

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

Answer and explanation

Correct Answer: C — when array is sorted but the values increases exponentially

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.

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

13.

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

Answer and explanation

Correct Answer: B — array is sorted and has uniform distribution of values

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.

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

14.

Interpolation search is a variation of?

Linear search

Binary search

Jump search

Exponential search

Answer and explanation

Correct Answer: B — Binary 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.

Data Structure And AlgorithmMediumSearching AlgorithmsInterpolation

15.

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

Answer and explanation

Correct Answer: D — 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.

Printing this content is disabled

Interpolation in Data Structure And Algorithm: Practice MCQ Questions and Answers