Data Structure

Fibonacci Search

Question 1
Marks : +2 | -2
Pass Ratio : 100%
What is the length of the step in jump search?
n
n/2
sqrt(n)
1
Explanation:
If the step size is 1, it becomes a linear search, if it is n, we reach the end of the list in just on step, if it is n/2, it becomes similar to binary search, therefore the most efficient step size is found to be sqrt(n).
Question 2
Marks : +2 | -2
Pass Ratio : 100%
Which of the following is not an advantage of Fibonacci Search?
When the element being searched for has a non uniform access storage
Can be used in magnetic tapes
Can be used for large arrays which do not fit in the CPU cache or in the RAM
It can be applied efficiently on unsorted arrays
Explanation:
When the speed of access depends on the location previously accessed, Fibonacci search is better compared to binary search as it performs well on those locations which have lower dispersion. Fibonacci search won’t work on unsorted arrays. The input should be a sorted array or array should be sorted before Fibonacci search.
Question 3
Marks : +2 | -2
Pass Ratio : 100%
)
Explanation:
Here instead of choosing middle of the array as a point of array division, we use Fibonacci numbers, the division index are strictly between two Fibonacci numbers.
Question 4
Marks : +2 | -2
Pass Ratio : 100%
)
Explanation:
Question 5
Marks : +2 | -2
Pass Ratio : 100%
Choose the recursive formula for the Fibonacci series.(n>=1)
F(n) = F(n+1) + F(n+2)
F(n) = F(n) + F(n+1)
F(n) = F(n-1) + F(n-2)
F(n) = F(n-1) – F(n-2)
Explanation:
None.
Question 6
Marks : +2 | -2
Pass Ratio : 100%
Which algorithmic technique does Fibonacci search use?
Brute force
Divide and Conquer
Greedy Technique
Backtracking
Explanation:
With every iteration, we divide the given array into two sub arrays(not necessarily equal).
Question 7
Marks : +2 | -2
Pass Ratio : 100%
)
Explanation:
Question 8
Marks : +2 | -2
Pass Ratio : 100%
Write a function for the Fibonacci search method.
Explanation:
Question 9
Marks : +2 | -2
Pass Ratio : 100%
What is the time complexity of Fibonacci Search?
O(logn)
O(n)
O(n2)
O(nlogn)
Explanation:
Since it divides the array into two parts, although not equal, its time complexity is O(logn), it is better than binary search in case of large arrays.
Question 10
Marks : +2 | -2
Pass Ratio : 100%
Select the code snippet for Jump Search.
Explanation: