# Searching in Data Structure and Algorithms MCQs

Q1. What is the worst case for linear search?.

A.  O(nlogn).

B.  O(logn).

C.  O(n).

D.  O(1).

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).

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.

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).

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.

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.

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).

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.

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.

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.

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).

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).

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.

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.

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.

Q22. What is the time complexity of binary search with iteration?.

A.  O(nlogn).

B.  O(logn).

C.  O(n).

D.  O(n^2).

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.

Q24. What is the time complexity of uniform binary search?.

A.  O(nlogn).

B.  O(logn).

C.  O(n).

D.  O(n^2).

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.

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.

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.

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.

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.

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).

Q35. Which of the following searching algorithm is fastest?.

A.  jump search.

B.  binary search.

C.  linear search.

D.  all are equally fast.

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).

Q38. Which algorithmic technique does Fibonacci search use?.

A.  Brute force.

B.  Divide and Conquer.

C.  Greedy Technique.

D.  Backtracking.

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).

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.

Q42. What is the length of the step in jump search?.

A.  n.

B.  n/2.

C.  sqrt(n).

D. 1.

Q43. What is the time complexity of Jump Search?.

A.  O(logn).

B.  O(n).

C.  O(sqrt(n)).

D.  O(nlogn).

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.

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.

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).

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).

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).

Q50. Which of the following searching algorithm is fastest?.

A.  jump search.

B.  exponential search.

C.  linear search.

D.  all are equally fast.

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).

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.

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.

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).

Q60. What is the auxiliary space requirement of interpolation search?.

A.  O(n).

B.  O(2n).

C.  O(1).

D.  O(log n).

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).

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.

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.

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.

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.

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).

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).

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).

Q72. How many passes does an insertion sort algorithm consist of?.

A.  N.

B.  N-1.

C.  N+1.

D.  N^2.