Data Structure Multiple Choice Questions & Answers (MCQs) on “Minimum Number of Jumps”.
1. You are given an array of elements where each array element represents the MAXIMUM number of jumps that can be made in the forward direction from that element. You have to find the minimum number of jumps that are required to reach the end of the array. Which of these methods can be used to solve the problem? Answer: d 2. Consider the following array: Answer: c 3. Consider the following recursive implementation: Which of these arguments should be passed by the min_jumps function represented by the blanks? Answer: a 4. For a given array, there can be multiple ways to reach the end of the array using minimum number of jumps. 5. What is the output of the following program? a) 4 Answer: a 6. For any array, given that at most one element is non-zero, it is ALWAYS possible to reach the end of the array using minimum jumps. Answer: b 7. Consider the following dynamic programming implementation of the minimum jumps problem: Which of the following “for” loops can be used instead of the inner for loop so that the output doesn’t change? Answer: d 8. What is the time complexity of the following dynamic programming implementation used to find the minimum number of jumps? a) O(1) Answer: c 9. What is the space complexity of the following dynamic programming implementation used to find the minimum number of jumps? a) O(1) Answer: b 10. What is the output of the following program? a) 7 Answer: b 11. What is the output of the following program? a) 1 Answer: a
a) Dynamic Programming
b) Greedy Algorithm
c) Recursion
d) Recursion and Dynamic Programming
Clarification: Both recursion and dynamic programming can be used to solve minimum number of jumps problem.
{1, 3, 5, 8, 9, 2, 6, 7, 6}
What is the minimum number of jumps required to reach the end of the array?
a) 1
b) 2
c) 3
d) 4
Clarification: The jumps made will be:{1 -> 2 -> 4 -> 9}. So, the number of jumps is three.#include
a) arr, strt + idx, end
b) arr + idx, strt, end
c) arr, strt, end
d) arr, strt, end + idx
Clarification: arr, strt + idx, end should be passed as arguments.
a) True
b) False
Answer: a
Clarification: Consider the array {1,2,3,4,5}. It is possible to reach the end in the following ways: {1 -> 2 -> 3 -> 5} or {1 -> 2 -> 4 -> 5}.
In both the cases the number of jumps is 3, which is minimum. Hence, it is possible to reach the end of the array in multiple ways using minimum number of jumps.#include
b) 5
c) 6
d) 7
Clarification: The program prints the minimum number of jumps required to reach the end of the array. One way reach the end using minimum number of jumps is
{1 -> 2 -> 4 -> 8 -> 9}. So, the number of jumps is 4.
a) True
b) False
Clarification: Consider the array {1,0,2,3,4}.
In this case, only one element is 0 but it is not possible to reach the end of the array.#include
a) for(j = 1; j < arr[idx] + len; j++)
b) for(j = 0; j < arr[idx] – len; j++)
c) for(j = idx + 1; j < len && j <= arr[idx] + idx; j++)
d) No change is required
Clarification: None of the above mentioned “for” loops can be used instead of the inner for loop. Note, for(j = idx + 1; j < len && j <= arr[idx] + idx; j++) covers the same range as the inner for loop but it produces the wrong output because the indexing inside the loops changes as “j” takes different values in the two “for” loops.#include
b) O(n)
c) O(n2)
d) None of the mentioned
Clarification: The time complexity of the above dynamic programming implementation is O(n2).#include
b) O(n)
c) O(n2)
d) O(5)
Clarification: The space complexity of the above dynamic programming implementation is O(n).#include
b) 8
c) 9
d) 10
Clarification: The program prints the minimum jumps required to reach the end of the array, which is 8 and so the output is 8.#include
b) 6
c) 2
d) 7
Clarification: The program prints the minimum jumps required to reach the end of the array, which is 1 and so the output is 1.