Browse topic-based Data Structure And Algorithm practice sets.
302 practice sets · Page 2 of 16
Can linear search recursive algorithm and binary search recursive algorithm be performed on an unordered list?
Binary search can't be used
Linear search can't be used
Both cannot be used
Both can be used
Correct Answer: A — Binary search can't be used
Explanation:
As binary search requires comparison, it is required that the list be ordered. Whereas this doesn't matter for linear search.
What is the best case runtime of linear search(recursive) algorithm on an ordered set of elements?
O(1)
O(n)
O(logn)
O(nx)
Correct Answer: A — O(1)
Explanation:
The best case occurs when the given element to be found is at the first position. Therefore O(1) is the correct answer.
The array is as follows: 1,2,3,6,8,10. Given that the number 17 is to be searched. At which call it tells that there's no such element (By using linear search(recursive) algorithm)
7th call
9th call
17th call
The function calls itself infinite number of times
Correct Answer: A — 7th call
Explanation:
The function calls itself till the element is found. But at the 7th call it terminates as goes outside the array.
The array is as follows: 1,2,3,6,8,10. At what time the element 6 is found (By using linear search(recursive) algorithm)
4th call
3rd call
6th call
5th call
Correct Answer: A — 4th call
Explanation:
Provided that the search starts from the first element, the function calls itself till the element is found. In this case, the element is found in 4th call.
Linear search(recursive) algorithm used in _____________
When the size of the dataset is low
When the size of the dataset is large
When the dataset is unordered
Never used
Correct Answer: A — When the size of the dataset is low
Explanation:
It is used when the size of the dataset is low as its runtime is O(n) which is more when compared to the binary search O(logn).
What is the worst case runtime of linear search(recursive) algorithm?
O(n)
O(logn)
O(n^{2})
O(nx)
Correct Answer: A — O(n)
Explanation:
In the worst case scenario, there might be a need of calling the stack n times. Therfore O(n).
Is the space consumed by the linear search(recursive) and linear search(iterative) same?
No, recursive algorithm consumes more space
No, recursive algorithm consumes less space
Yes
Nothing can be said
Correct Answer: A — No, recursive algorithm consumes more space
Explanation:
The recursive algorithm consumes more space as it involves the usage the stack space(calls the function numerous times).
Is there any difference in the speed of execution between linear serach(recursive) vs linear search(lterative)?
Both execute at same speed
Linear search(recursive) is faster
Linear search(Iterative) is faster
Cant be said
Correct Answer: C — Linear search(Iterative) is faster
Explanation:
The Iterative algorithm is faster than the latter as recursive algorithm has overheads like calling function and registering stacks repeatedly.
Jump search has a worst case time complexity of O(n).
True
False
Correct Answer: B — False
Explanation:
The time complexity of jump search is O(n^{1/2}) in worst and average case. It is due to the fact that size of optimal jump is n^{1/2}.
Jump search is worse than linear search in terms of time complexity.
True
False
Correct Answer: B — False
Explanation:
Linear search has a time complexity of O(n) and the time complexity of jump search is O(n^{1/2}). So jump search is better than linear search in terms of time complexity.
Best case of jump search will have time complexity of _________
O(1)
O(n)
O(log n)
O(n log n)
Correct Answer: A — O(1)
Explanation:
Best case of jump 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 binary 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
Correct Answer: A — jumping backwards takes significantly more time than jumping forward
Explanation:
Jump search only needs to jump backwards once, while a binary can jump backwards up to log n times. Thus jump search will be preferred over binary search if jumping backwards is expensive.
Which of the following searching algorithm is fastest?
jump search
binary search
linear search
all are equally fast
Correct Answer: B — binary search
Explanation:
Binary search has the least time complexity (equal to log n) out of the given searching algorithms. This makes binary search preferable in most cases.
What is the auxiliary space requirement of the jump search?
O(n)
O(log n)
O(n^{1/2})
O(1)
Correct Answer: D — O(1)
Explanation:
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
Correct Answer: C — n^{1/2}
Explanation:
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
Correct Answer: C — k-1
Explanation:
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
Correct Answer: B — n/k
Explanation:
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
Correct Answer: B — linear search takes place in the backward direction
Explanation:
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
Correct Answer: C — element having value greater than that of the required element is found
Explanation:
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
Correct Answer: A — array should be sorted
Explanation:
Jump sort requires the input array to be sorted. The algorithm would fail to give the correct result if array is not sorted.
