This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Jump Search”.
1. 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
View Answer
Explanation: Jump sort requires the input array to be sorted. The algorithm would fail to give the correct result if array is not sorted.
2. 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
View Answer
Explanation: In jump search algorithm jumps are made until element having value greater than the value of element being searched is found. After this linear search is performed in backwards direction.
3. 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
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.
4. 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
View Answer
Explanation: Worst case occurs when the value to be searched is in the last section of the array. So, in this case the number of jumps will be n/k.
5. 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
View Answer
Explanation: Worst case occurs when the element being searched is present just after the element that has been compared while making the last jump. So, in this case k-1 comparisons will have to be made.
6. What is the value of jump taken for maximum efficiency while implementing jump search?
a) n/2
b) n2
c) n1/2
d) log n
View Answer
Explanation: Total number of comparisons required will be n/k + k-1 in worst case. This function will be minimum for k=n1/2. So this value of jump will be the best for implementing jump search.
7. What is the auxiliary space requirement of the jump search?
a) O(n)
b) O(log n)
c) O(n1/2)
d) O(1)
View Answer
Explanation: Jump search does not require any additional space for searching the required element. Thus its auxiliary space requirement will be O(1).
8. Which of the following searching algorithm is fastest?
a) jump search
b) binary search
c) linear 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.
9. 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
View Answer
Explanation: Jump search only needs to jump backwards once, while a binary can jump backwards up to log n times. Thus jump search will be preferred over binary search if jumping backwards is expensive.
10. 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)
View Answer
Explanation: Best case of jump search will be when the first element of the array is the element that is being searched. In this case only one comparison will be required. Thus it will have a time complexity of O(1).
11. Which of the following code correctly represent jump search?
a)
int jumpSearch(int arr[], int x, int n) { int step = n*n; int prev = 0; while (arr[min(step, n)-1] < x) { prev = step; step += sqrt(n); if (prev >= n) return -1; } while (arr[prev] < x) { prev++; if (prev == min(step, n)) return -1; } if (arr[prev] == x) return prev; return -1; }
b)
int jumpSearch(int arr[], int x, int n) { int step = sqrt(n); int prev = 0; while (arr[min(step, n)-1] < x) { prev = step; step += sqrt(n); if (prev >= n) return -1; } while (arr[prev] < x) { prev++; if (prev == min(step, n)) return -1; } if (arr[prev] == x) return prev; return -1; }
c)
int jumpSearch(int arr[], int x, int n) { int step = sqrt(n); int prev = 0; while (arr[min(step, n)-1] < x) { prev = step; step += sqrt(n); if (prev == n) return -1; } while (arr[prev] < x) { prev++; if (prev == min(step, n)) return -1; } if (arr[prev] == x) return prev; return -1; }
d)
int jumpSearch(int arr[], int x, int n) { int step = sqrt(n); int prev = 0; while (arr[min(step, n)-1] < x) { prev = step; step += sqrt(n); if (prev >= n) return -1; } while (arr[prev] > x) { prev++; if (prev == min(step, n)) return -1; } if (arr[prev] == x) return prev; return -1; }
Explanation: The correct code first makes jumps until an element greater than the required element is found. Then linear search is performed in a backwards direction. If the element is not found then we return -1.
12. Jump search is worse than linear search in terms of time complexity.
a) True
b) False
View Answer
Explanation: Linear search has a time complexity of O(n) and the time complexity of jump search is O(n1/2). So jump search is better than linear search in terms of time complexity.
13. Jump search has a worst case time complexity of O(n).
a) True
b) False
View Answer
Explanation: The time complexity of jump search is O(n1/2) in worst and average case. It is due to the fact that size of optimal jump is n1/2.
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]
- Practice Computer Science MCQs
- Check Computer Science Books
- Practice Programming MCQs
- Apply for Computer Science Internship
- Practice Data Structure MCQ
