This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Searching”.
1. Which of the following searching algorithm is fastest?
a) binary search
b) linear search
c) jump search
d) all are equally fast
View Answer
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.
2. Where is linear searching used?
a) Used all the time
b) When the list has only a few elements
c) When performing a single search in an unordered list
d) When the list has only a few elements and When performing a single search in an unordered list
View Answer
Explanation: It is practical to implement linear search in the situations mentioned in When the list has only a few elements and When performing a single search in an unordered list, but for larger elements the complexity becomes larger and it makes sense to sort the list and employ binary search or hashing.
3. How can Jump Search be improved?
a) Step size should be other than sqrt(n)
b) Cannot be improved
c) Begin from the kth item, where k is the step size
d) Start searching from the end
View Answer
Explanation: This gives a very slight improvement as you are skipping the first k elements.
4. Which of the following searching algorithm is used with exponential sort after finding the appropriate range?
a) Jump search
b) Fibonacci Search
c) Linear search
d) Binary search
View Answer
Explanation: In exponential search, we first find a range where the required elements should be present in the array. Then we apply binary search in this range.
5. Which of the following searching algorithm is fastest when the input array is not sorted but has uniformly distributed values?
a) linear search
b) jump search
c) interpolation search
d) binary search
View Answer
Explanation: Out of the given options linear search is the only searching algorithm which can be applied to arrays which are not sorted. It has a time complexity of O(n) in the worst case.
6. What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
a) O(n)
b) O(m)
c) O(n + m)
d) O(m * n)
View Answer
Explanation: Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It has a time complexity of O(m + n) where m is the length of text and n is the length of the pattern.
7. In which of the cases uniform binary search fails compared to binary search?
a) Complexity of code
b) Many searches will be performed on several arrays of the same length
c) Many searches will be performed on the same array
d) A table lookup is generally faster than an addition and a shift
View Answer
Explanation: Uniform binary search code is more complex to implement than binary search as it involves mid points to be computed in hand before search.
8. Interpolation search is a variation of?
a) Exponential search
b) Linear search
c) Binary search
d) Jump search
View Answer
Explanation: Interpolation search is a variation of binary search which gives the best result when the array has uniformly distributed values. Interpolation search goes to different positions depending on the value being searched whereas binary search always goes to the middle element.
9. Which of the following is not an application of binary search?
a) To search in unordered list
b) Debugging
c) Union of intervals
d) To find the lower/upper bound in an ordered sequence
View Answer
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.
10. Which of the following step is taken after finding an element having value greater than the element being searched?
a) binary search takes place in the forward direction
b) binary search takes place in a backward direction
c) linear search takes place in the forward direction
d) linear search takes place in the backward direction
View Answer
Explanation: First an element having value greater than the element being searched is found. After this linear search is performed in a backward direction.
11. Which of the following is not an advantage of Fibonacci Search?
a) When the element being searched for has a non uniform access storage
b) It can be applied efficiently on unsorted arrays
c) Can be used for large arrays which do not fit in the CPU cache or in the RAM
d) Can be used in magnetic tapes
View Answer
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.
12. In which of the following case jump search will be preferred over exponential search?
a) when the given array is very small in size
b) when the given array is very large in size
c) jumping backwards takes significantly more time than jumping forward
d) jumping forward takes significantly more time than jumping backwards
View Answer
Explanation: Jump search only needs to jump backwards once, while an exponential search can jump backwards up to log n times. Thus jump search will be preferred if jumping backwards is expensive.
More MCQs on Searching:
- Searching MCQ (Set 2) – Linear Search
- Searching MCQ (Set 3) – Linear Search Iterative
- Searching MCQ (Set 4) – Binary Search
- Searching MCQ (Set 5) – Uniform Binary Search
- Searching MCQ (Set 6) – Jump Search
- Searching MCQ (Set 7) – Fibonacci Search
- Searching MCQ (Set 8) – Exponential Search
- Searching MCQ (Set 9) – Interpolation Searching Algorithm
- Searching MCQ (Set 10) – Substring Searching Algorithm
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
