This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Greedy Algorithms”.
1. The first step in the naïve greedy algorithm is?
a) adding flows with higher values
b) reversing flow if required
c) analysing the zero flow
d) calculating the maximum flow using trial and error
View Answer
Explanation: The first step in the naïve greedy algorithm is to start with the zero flow followed by adding edges with higher values.
2. Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?
a) 100
b) 10
c) 6
d) 14
View Answer
Explanation: Using the greedy algorithm, three coins {4,1,1} will be selected to make a sum of 6. But, the optimal answer is two coins {3,3}. Similarly, four coins {4,4,1,1} will be selected to make a sum of 10. But, the optimal answer is three coins {4,3,3}. Also, five coins {4,4,4,1,1} will be selected to make a sum of 14. But, the optimal answer is four coins {4,4,3,3}. For a sum of 100, twenty-five coins {all 4’s} will be selected and the optimal answer is also twenty-five coins {all 4’s}.
3. Choose the correct statement from the following.
a) branch and bound is not suitable where a greedy algorithm is not applicable
b) branch and bound divides a problem into at least 2 new restricted sub problems
c) backtracking divides a problem into at least 2 new restricted sub problems
d) branch and bound is more efficient than backtracking
View Answer
Explanation: Both backtracking as well as branch and bound are problem solving algorithms. Branch and bound is less efficient than backtracking. Branch and bound divides a problem into at least 2 new restricted sub problems.
4. Dijkstra’s Algorithm is the prime example for ___________
a) Dynamic programming
b) Back tracking
c) Branch and bound
d) Greedy algorithm
View Answer
Explanation: Dijkstra’s Algorithm is the prime example for greedy algorithms because greedy algorithms generally solve a problem in stages by doing what appears to be the best thing at each stage.
5. Bellmann Ford Algorithm is an example for ____________
a) Linear Programming
b) Greedy Algorithms
c) Dynamic Programming
d) Branch and Bound
View Answer
Explanation: In Bellmann Ford Algorithm the shortest paths are calculated in bottom up manner which is similar to other dynamic programming problems.
6. Which of the following algorithms is the best approach for solving Huffman codes?
a) greedy algorithm
b) exhaustive search
c) divide and conquer algorithm
d) brute force algorithm
View Answer
Explanation: Greedy algorithm is the best approach for solving the Huffman codes problem since it greedily searches for an optimal solution.
7. Fractional knapsack problem is solved most efficiently by which of the following algorithm?
a) Backtracking
b) Greedy algorithm
c) Dynamic programming
d) Divide and conquer
View Answer
Explanation: Greedy algorithm is used to solve this problem. We first sort items according to their value/weight ratio and then add item with highest ratio until we cannot add the next item as a whole. At the end, we add the next item as much as we can.
8. Which of the following is false about the Kruskal’s algorithm?
a) It constructs MST by selecting edges in increasing order of their weights
b) It is a greedy algorithm
c) It uses union-find data structure
d) It can accept cycles in the MST
View Answer
Explanation: Kruskal’s algorithm is a greedy algorithm to construct the MST of the given graph. It constructs the MST by selecting edges in increasing order of their weights and rejects an edge if it may form the cycle. So, using Kruskal’s algorithm is never formed.
More MCQs on Greedy Algorithms:
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.
