Q1. What is the worst case for linear search?.
A. O(nlogn).
B. O(logn).
C. O(n).
D. O(1).
Answer= O(n)
Q2. What is the best case and worst case complexity of ordered linear search?.
A. O(nlogn), O(logn).
B. O(logn), O(nlogn).
C. O(n), O(1).
D. O(1), O(n).
Answer= O(1), O(n)
Q3. Which of the following is a disadvantage of linear search?.
A. Requires more space.
B. Greater time complexities compared to other searching algorithms.
C. Not easy to understand.
D. Not easy to implement.
Answer= Greater time complexities compared to other searching algorithms
Q4. Is there any difference in the speed of execution between linear serach(recursive) vs linear search(lterative)?.
A. Both execute at same speed.
B. Linear search(recursive) is faster.
C. Linear search(Iterative) is faster.
D. Cant be said.
Answer= Linear search(Iterative) is faster
Q5. Is the space consumed by the linear search(recursive) and linear search(iterative) same?.
A. No, recursive algorithm consumes more space.
B. No, recursive algorithm consumes less space.
C. Yes.
D. Nothing can be said.
Answer= No, recursive algorithm consumes more space
Q6. What is the worst case runtime of linear search(recursive) algorithm?.
A. O(n).
B. O(logn).
C. O(n^2).
D. O(nx).
Answer= O(n)
Q7. Linear search(recursive) algorithm used in _____________.
A. When the size of the dataset is low.
B. When the size of the dataset is large.
C. When the dataset is unordered.
D. Never used.
Answer= When the size of the dataset is low
Q8. 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).
A. 4th call.
B. 3rd call.
C. 6th call.
D. 5th call.
Answer= 4th call
Q9. 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).
A. 7th call.
B. 9th call.
C. 17th call.
D. The function calls itself infinite number of times.
Answer= 7th call
Q10. What is the best case runtime of linear search(recursive) algorithm on an ordered set of elements?.
A. O(1).
B. O(n).
C. O(logn).
D. O(nx).
Answer= O(1)
Q11. Can linear search recursive algorithm and binary search recursive algorithm be performed on an unordered list?.
A. Binary search can’t be used.
B. Linear search can’t be used.
C. Both cannot be used.
D. Both can be used.
Answer= Binary search can’t be used
Q12. What is the recurrence relation for the linear search recursive algorithm?.
A. T(n-2)+c.
B. 2T(n-1)+c.
C. T(n-1)+c.
D. T(n+1)+c.
Answer= T(n-1)+c
Q13. What is the advantage of recursive approach than an iterative approach?.
A. Consumes less memory.
B. Less code and easy to implement.
C. Consumes more memory.
D. More code has to be written.
Answer= Less code and easy to implement
Q14. Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?.
A. 5.
B. 2.
C. 3.
D. 4.
Answer= 3
Q15. 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?.
A. 90 and 99.
B. 90 and 94.
C. 89 and 99.
D. 89 and 94.
Answer= 90 and 99
Q16. What is the worst case complexity of binary search using recursion?.
A. O(nlogn).
B. O(logn).
C. O(n).
D. O(n^2).
Answer= O(logn)
Q17. What is the average case time complexity of binary search using recursion?.
A. O(nlogn).
B. O(logn).
C. O(n).
D. O(n^2).
Answer= O(logn)
Q18. Which of the following is not an application of binary search?.
A. To find the lower/upper bound in an ordered sequence.
B. Union of intervals.
C. Debugging.
D. To search in unordered list.
Answer= To search in unordered list
Q19. Binary Search can be categorized into which of the following?.
A. Brute Force technique.
B. Divide and conquer.
C. Greedy algorithm.
D. Dynamic programming.
Answer= Divide and conquer
Q20. Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element is found?.
A. 1.
B. 3.
C. 4.
D. 2.
Answer= 2
Q21. 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?.
A. 90 and 99.
B. 90 and 100.
C. 89 and 94.
D. 94 and 99.
Answer= 90 and 99
Q22. What is the time complexity of binary search with iteration?.
A. O(nlogn).
B. O(logn).
C. O(n).
D. O(n^2).
Answer= O(logn)
Q23. In which of the cases uniform binary search fails compared to binary search?.
A. A table lookup is generally faster than an addition and a shift.
B. Many searches will be performed on the same array.
C. Many searches will be performed on several arrays of the same length.
D. Complexity of code.
Answer= Complexity of code
Q24. What is the time complexity of uniform binary search?.
A. O(nlogn).
B. O(logn).
C. O(n).
D. O(n^2).
Answer= O(logn)
Q25. Given, arr = {1,3,5,6,7,9,14,15,17,19} key = 17 and delta = {5,3,1,0}How many key comparisons are made?(exclude the comparison used to decide the left or right sub array).
A. 4.
B. 3.
C. 5.
D. 6.
Answer= 3
Q26. How can Jump Search be improved?.
A. Start searching from the end.
B. Begin from the kth item, where k is the step size.
C. Cannot be improved.
D. Step size should be other than sqrt(n).
Answer= Begin from the kth item, where k is the step size
Q27. Which of the following false about Jump Search?.
A. Jump Search is better than Linear Search.
B. Useful when jumping back is more costly than jumping forward.
C. Jump Search is worse than Binary Search.
D. Jump search starts from the index 0 even though specified index is k.
Answer= Jump search starts from the index 0 even though specified index is k
Q28. Jump search algorithm requires which of the following condition to be true?.
A. array should be sorted.
B. array should have not be sorted.
C. array should have a less than 64 elements.
D. array should be partially sorted.
Answer= array should be sorted
Q29. Jumps are made in the jump search algorithm until ___________.
A. element having value less than that of the required element is found.
B. element having value equal to the median of values of the array is found.
C. element having value greater than that of the required element is found.
D. middle element is found equal to the element being searched.
Answer= element having value greater than that of the required element is found
Q30. Which of the following step is taken after finding an element having value greater than the element being searched?.
A. linear search takes place in the forward direction.
B. linear search takes place in the backward direction.
C. binary search takes place in the forward direction.
D. binary search takes place in a backward direction.
Answer= linear search takes place in the backward direction
Q31. How many jumps will be made in the worst case of jump search(let block jumped =k)?.
A. n*k.
B. n/k.
C. k/n.
D. n+k.
Answer= n/k
Q32. What will be the maximum number of comparisons that can be made in jump search algorithm (assuming k to be blocks jumped)?.
A. k.
B. n/k.
C. k-1.
D. k-1.
Answer= k-1
Q33. What is the value of jump taken for maximum efficiency while implementing jump search?.
A. n/2.
B. n^2.
C. n1/2.
D. log n.
Answer= n1/2
Q34. What is the auxiliary space requirement of the jump search?.
A. O(n).
B. O(log n).
C. O(n1/2).
D. O(1).
Answer= O(1)
Q35. Which of the following searching algorithm is fastest?.
A. jump search.
B. binary search.
C. linear search.
D. all are equally fast.
Answer= binary search
Q36. In which of the following case jump search will be preferred over binary search?.
A. jumping backwards takes significantly more time than jumping forward.
B. jumping forward takes significantly more time than jumping backwards.
C. when the given array is very large in size.
D. when the given array is very small in size.
Answer= jumping backwards takes significantly more time than jumping forward
Q37. Best case of jump search will have time complexity of _________.
A. O(1).
B. O(n).
C. O(log n).
D. O(n log n).
Answer= O(1)
Q38. Which algorithmic technique does Fibonacci search use?.
A. Brute force.
B. Divide and Conquer.
C. Greedy Technique.
D. Backtracking.
Answer= Divide and Conquer
Q39. Choose the recursive formula for the Fibonacci series.(n>=1).
A. F(n) = F(n+1) + F(n+2).
B. F(n) = F(n) + F(n+1).
C. F(n) = F(n-1) + F(n-2).
D. F(n) = F(n-1) – F(n-2).
Answer= F(n) = F(n-1) + F(n-2)
Q40. What is the time complexity of Fibonacci Search?.
A. O(logn).
B. O(n).
C. O(n^2).
D. O(nlogn).
Answer= O(logn)
Q41. What are the advantages of Fibonacci Search?.
A. When the element being searched for has a non uniform access storage.
B. Can be used in magnetic tapes.
C. Can be used for large arrays which do not fit in the CPUcache or in the RAM.
D. All of the mentioned.
Answer= All of the mentioned
Q42. What is the length of the step in jump search?.
A. n.
B. n/2.
C. sqrt(n).
D. 1.
Answer= sqrt(n)
Q43. What is the time complexity of Jump Search?.
A. O(logn).
B. O(n).
C. O(sqrt(n)).
D. O(nlogn).
Answer= O(sqrt(n))
Q44. Exponential search algorithm requires which of the following condition to be true?.
A. array should be sorted.
B. array should have not be sorted.
C. array should have a less than 128 elements.
D. array should be partially sorted.
Answer= array should be sorted
Q45. Which of the following searching algorithm is used with exponential sort after finding the appropriate range?.
A. Linear search.
B. Binary search.
C. Jump search.
D. Fibonacci Search.
Answer= Binary search
Q46. Exponential search has ____________.
A. neither an exponential space complexity nor exponential time complexity.
B. exponential time complexity but a linear space complexity.
C. exponential space complexity but a linear time complexity.
D. both exponential time and space complexity.
Answer= neither an exponential space complexity nor exponential time complexity
Q47. What is the time complexity of exponential sort?.
A. O(n).
B. O(2n).
C. O(n log n).
D. O(log n).
Answer= O(log n)
Q48. What is the auxiliary space requirement of an exponential sort when used with iterative binary search?.
A. O(n).
B. O(2n).
C. O(1).
D. O(log n).
Answer= O(1)
Q49. What is the auxiliary space requirement of the exponential sort when used with recursive binary search?.
A. O(n).
B. O(2n).
C. O(1).
D. O(log n).
Answer= O(log n)
Q50. Which of the following searching algorithm is fastest?.
A. jump search.
B. exponential search.
C. linear search.
D. all are equally fast.
Answer= exponential search
Q51. In which of the following case jump search will be preferred over exponential search?.
A. jumping backwards takes significantly more time than jumping forward.
B. jumping forward takes significantly more time than jumping backwards.
C. when the given array is very large in size.
D. when the given array is very small in size.
Answer= jumping backwards takes significantly more time than jumping forward
Q52. Best case of the exponential search will have time complexity of?.
A. O(1).
B. O(n).
C. O(log n).
D. O(n log n).
Answer= O(1)
Q53. Choose the incorrect statement about exponential search from the following..
A. Exponential search is an in place algorithm.
B. Exponential search has a greater time complexity than binary search.
C. Exponential search performs better than binary search when the element being searched is present near the starting point of the array..
D. Jump search has a greater time complexity than an exponential search.
Answer= Exponential search has a greater time complexity than binary search
Q54. Which of the following is not an alternate name of exponential search?.
A. Logarithmic search.
B. Doubling search.
C. Galloping search.
D. Struzik search.
Answer= Logarithmic search
Q55. Which of the following is the most desirable condition for interpolation search?.
A. array should be sorted.
B. array should not be sorted but the values should be uniformly distributed.
C. array should have a less than 64 elements.
D. array should be sorted and the values should be uniformly distributed.
Answer= array should be sorted and the values should be uniformly distributed
Q56. Interpolation search is a variation of?.
A. Linear search.
B. Binary search.
C. Jump search.
D. Exponential search.
Answer= Binary search
Q57. Interpolation search performs better than binary search when?.
A. array has uniformly distributed values but is not sorted.
B. array is sorted and has uniform distribution of values.
C. array is sorted but the values are not uniformly distributed.
D. array is not sorted.
Answer= array is sorted and has uniform distribution of values
Q58. In which of the following case jump search performs better than interpolation search?.
A. When array has uniformly distributed values but is not sorted.
B. when array is sorted and has uniform distribution of values.
C. when array is sorted but the values increases exponentially.
D. when array is not sorted.
Answer= when array is sorted but the values increases exponentially
Q59. What is the time complexity of interpolation search when the input array has uniformly distributed values and is sorted?.
A. O(n).
B. O(log log n).
C. O(n log n).
D. O(log n).
Answer= O(log log n)
Q60. What is the auxiliary space requirement of interpolation search?.
A. O(n).
B. O(2n).
C. O(1).
D. O(log n).
Answer= O(1)
Q61. What is the time complexity of exponential search when the input array is sorted but the values are not uniformly distributed?.
A. O(n1/2).
B. O(log log n).
C. O(n).
D. O(log n).
Answer= O(n)
Q62. Which of the following searching algorithm is fastest when the input array is sorted and has uniformly distributed values?.
A. jump search.
B. exponential search.
C. binary search.
D. interpolation search.
Answer= interpolation search
Q63. Which of the following searching algorithm is fastest when the input array is sorted but has non uniformly distributed values?.
A. jump search.
B. linear search.
C. binary search.
D. interpolation search.
Answer= binary search
Q64. Which of the following searching algorithm is fastest when the input array is not sorted but has uniformly distributed values?.
A. jump search.
B. linear search.
C. binary search.
D. interpolation search.
Answer= linear search
Q65. 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).
A. ((x – A[low]) * (high – low)) / (A[high] – A[low]).
B. high + ((x – A[low]) * (high – low)) / (A[high] – A[low]).
C. low + ((x – A[low]) * (high – low)) / (A[high] – A[low]).
D. x + ((x – A[low]) * (high – low)) / (A[high] – A[low]).
Answer= low + ((x – A[low]) * (high – low)) / (A[high] – A[low])
Q66. 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).
A. low = pos + 1, high remains unchanged.
B. high = pos – 1, low remains unchanged.
C. low = low +1, high = high – 1.
D. low = pos +1, high = pos – 1.
Answer= low = pos + 1, high remains unchanged
Q67. 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).
A. low = pos + 1, high remains unchanged.
B. high = pos – 1, low remains unchanged.
C. low = low +1, high = high – 1.
D. low = pos +1, high = pos – 1.
Answer= high = pos – 1, low remains unchanged
Q68. Which of the following is a sub string of “SANFOUNDRY”?.
A. SANO.
B. FOUND.
C. SAND.
D. FOND.
Answer= FOUND
Q69. What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?.
A. O(n).
B. O(n*m).
C. O(m).
D. O(log n).
Answer= O(m)
Q70. What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?.
A. O(n + m).
B. O(m).
C. O(n).
D. O(m * n).
Answer= O(n + m)
Q71. What is the auxiliary space complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?.
A. O(n + m).
B. O(m).
C. O(n).
D. O(m * n).
Answer= O(m)
Q72. How many passes does an insertion sort algorithm consist of?.
A. N.
B. N-1.
C. N+1.
D. N^2.
Answer= N-1
Q73. Which of the following algorithm implementations is similar to that of an insertion sort?.
A. Binary heap.
B. Quick sort.
C. Merge sort.
D. Radix sort.
Answer= Binary heap