WorksheetsSearching Algorithms
Total questions: 26
Worksheet time: 16mins
Where is linear searching used?
When the list has only a few elements
When performing a single search in an unordered list
Used all the time
When the list has only a few elements and when performing a single search in an unordered list
What is the best case complexity for linear search?
O(nlogn)
O(logn)
O(n)
O(1)
What is the worst case complexity for linear search?
O(nlogn)
O(logn)
O(n)
O(1)
Which of the following is a disadvantage of linear search?
Requires more space
Greater time complexities compared to other searching algorithms
Not easy to understand
Not easy to implement
Which of the following is not an application of binary search?
To find the lower/upper bound in an ordered sequence
Searching for a word in a dictionary
Debugging
To search in unordered list
Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are doneuntil the element is found using binary search?
1
2
3
4
Given an array arr = {45,77,89,90,94,99,100} and key = 100; What are the mid values(corresponding array elements) generated in the first and second iterations using binary search?
90 and 99
90 and 100
89 and 94
94 and 99
What is the time complexity of binary search with iteration?
O(nlogn)
O(logn)
O(n)
O(n2)
Jump search is worse than linear search in terms of time complexity.
True
False
Jump search has a worst case time complexity of O(n).
True
False
Jump search algorithm requires which of the following condition to be true?
array should be sorted
array should not be sorted
array should have a less than 64 elements
array should be partially sorted
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, which of the following steps is taken after finding an element having value greater than the element being searched?
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
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
What is the value of jump taken for maximum efficiency while implementing jump search?
n/2
n^2
n^(1/2)
log n
Which of the following searching algorithm is fastest?
jump search
binary search
linear search
all are equally fast
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 less than 64 elements
array should be sorted and the values should be uniformly distributed
Interpolation search is a variation of?
Linear search
Binary search
Jump search
Exponential search
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
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
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)
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
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
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
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])
Select the code snippet which performs unordered linear search iteratively?
