ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
31 practice sets · Page 1 of 2
Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.
True
False
The worst case time complexity of Rabin Karp algorithm is O(m*n) but it has a linear average case time complexity. So Rabin Karp and naive pattern searching algorithm have the same worst case time complexity.
Which of the following is a sub string of "SANFOUNDRY"?
SANO
FOUND
SAND
FOND
A sub string is a subset of another string. So "FOUND" is the only possible sub string out of the given options.
The naive pattern searching algorithm is an in place algorithm.
True
False
The auxiliary space complexity required by naive pattern searching algorithm is O(1). So it qualifies as an in place algorithm.
What is the auxiliary space complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
O(n + m)
O(m)
O(n)
O(m * n)
Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It an auxiliary space of O(m) for maintaining Z array.
What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
O(n + m)
O(m)
O(n)
O(m * n)
Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It has a time complexity of O(m + n) where m is the length of text and n is the length of the pattern.
What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?
O(n)
O(n*m)
O(m)
O(log n)
KMP algorithm is an efficient pattern searching algorithm. It has a time complexity of O(m) where m is the length of text.
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.
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.
