Browse topic-based Data Structure And Algorithm practice sets.
302 practice sets · Page 5 of 16
What is the length of the step in jump search?
n
n/2
sqrt(n)
1
Correct Answer: C — sqrt(n)
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).
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
Correct Answer: D — 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.
What is the time complexity of Fibonacci Search?
O(logn)
O(n)
O(n^{2})
O(nlogn)
Correct Answer: A — O(logn)
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.
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))
Correct Answer: C — (F(n) = F(n-1) + F(n-2))
Explanation:
None.
Which algorithmic technique does Fibonacci search use?
Brute force
Divide and Conquer
Greedy Technique
Backtracking
Correct Answer: B — Divide and Conquer
Explanation:
With every iteration, we divide the given array into two sub arrays(not necessarily equal).
What is the time complexity of binary search with iteration?
O(nlogn)
O(logn)
O(n)
O(n^{2})
Correct Answer: B — O(logn)
Explanation:
(T(n) = T(n/2) + theta(1))
Using the divide and conquer master theorem, we get the time complexity as O(logn).
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?
90 and 99
90 and 100
89 and 94
94 and 99
Correct Answer: A — 90 and 99
Explanation:
Trace the input with the binary search iterative code.
Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element is found?
1
3
4
2
Correct Answer: D — 2
Explanation:
Iteration1 : mid = 77; Iteration2 : mid = 88;
Binary Search can be categorized into which of the following?
Brute Force technique
Divide and conquer
Greedy algorithm
Dynamic programming
Correct Answer: B — Divide and conquer
Explanation:
Since 'mid' is calculated for every iteration or recursion, we are diving the array into half and then try to solve the problem.
Which of the following is not an application of binary search?
To find the lower/upper bound in an ordered sequence
Union of intervals
Debugging
To search in unordered list
Correct Answer: D — To search in unordered list
Explanation:
In Binary search, the elements in the list should be sorted. It is applicable only for ordered list. Hence Binary search in unordered list is not an application.
What is the average case time complexity of binary search using recursion?
O(nlogn)
O(logn)
O(n)
O(n^{2})
Correct Answer: B — O(logn)
Explanation:
T(n) = T(n/2) + 1, Using the divide and conquer master theorem.
What is the worst case complexity of binary search using recursion?
O(nlogn)
O(logn)
O(n)
O(n^{2})
Correct Answer: B — O(logn)
Explanation:
Using the divide and conquer master theorem.
Given an array arr = {45,77,89,90,94,99,100} and key = 99; what are the mid values(corresponding array elements) in the first and second levels of recursion?
90 and 99
90 and 94
89 and 99
89 and 94
Correct Answer: A — 90 and 99
Explanation:
At first level key = 90
At second level key= 99
Here 90 and 99 are mid values.
Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?
5
2
3
4
Correct Answer: C — 3
Explanation:
level 1: mid = 7
level 2: mid = 99
level 3: mid = 899(this is the key).
What is the advantage of recursive approach than an iterative approach?
Consumes less memory
Less code and easy to implement
Consumes more memory
More code has to be written
Correct Answer: B — Less code and easy to implement
Explanation:
A recursive approach is easier to understand and contains fewer lines of code.
What is the space complexity of the above implementation of Wagner-Fischer algorithm where "m" and "n" are the lengths of the two strings?
O(1)
O(n+m)
O(mn)
O(nlogm)
Correct Answer: C — O(mn)
Explanation:
The space complexity of the above Wagner-Fischer algorithm is O(mn).
What is the time complexity of the Wagner-Fischer algorithm where "m" and "n" are the lengths of the two strings?
O(1)
O(n+m)
O(mn)
O(nlogm)
Correct Answer: C — O(mn)
Explanation:
The time complexity of the Wagner-Fischer algorithm is O(mn).
Which of the following lines should be inserted to complete the above code?
arr[i][j] = min
(min = arr[i-1][j-1] - 1);
min = arr[i-1][j-1].
(min = arr[i-1][j-1] + 1);
Correct Answer: C — min = arr[i-1][j-1].
Explanation:
The line min = arr[i-1][j-1] completes the above code.
For which of the following pairs of strings is the edit distance maximum?
sunday & monday
monday & tuesday
tuesday & wednesday
wednesday & thursday
Correct Answer: D — wednesday & thursday
Explanation:
The edit distances are 2, 4, 4 and 5 respectively. Hence, the maximum edit distance is between the strings wednesday and thursday.
What is the edit distance between the strings "abcd" and "acbd" when the allowed operations are insertion, deletion and substitution?
1
2
3
4
Correct Answer: B — 2
Explanation:
The string "abcd" can be changed to "acbd" by substituting "b" with "c" and "c" with "b". Thus, the edit distance is 2.
