Greedy Algorithm MCQs

Greedy Algorithm is an approach that makes the best choice at each step to find an optimal solution. Practice these multiple-choice questions to understand greedy strategies and problem-solving techniques with answers.

Greedy Algorithm MCQs with Answers

1. Question: Greedy Algorithms are:

1. All the problems can be solved optimally by using Greedy Algorithm.
2. Greedy Algorithms have some local optimal choices with the aim of finding a global optimum.
3. The greedy Algorithms cannot be used in optimization problems.
4. The time complexity of Greedy Algorithms is very exponential.

2. Question: What Greedy Algorithm can be widely used to solve the above-mentioned problems?

1. Travelling Salesman Problem (TSP)
2. Minimum Spanning Tree (MST)
3. Shortest Path in a Graph
4. All of the above

3. Question: The main design principle employed by the Greedy Algorithm in the Huffman coding is:

1. Setting length scores to be equal for all the codewords
2. The use of codewords with variable lengths by the frequencies
3. Assigning random lengths to codewords
4. The use of longer codewords for the symbols with higher frequencies

4. Question: What is the main benefit of Greedy Algorithms?

1. Always guaranteeing the optimal solution
2. Simplicity and ease of implementation
3. Efficiently handling large datasets
4. Parallel processing capabilities

5. Question: What is the main weakness of the Greedy Algorithms?

1. Inability to handle large datasets
2. Complexity and difficulty of implementation
3. Lack of parallel processing capabilities
4. Lack of backtracking and revaluation

6. Question: Which of the following problems does not use any optimization?

1. Huffman Coding
2. Job Scheduling
3. Fractional Knapsack
4. Linear Search

7. Question: In Dijkstra's algorithm for finding the Shortest Path, what is the Greedy Choice at each step?

1. Choosing the shortest edge
2. Choosing the longest edge
3. Choosing edges randomly
4. Selecting the edge with the highest weight

8. Question: What is the Greedy Algorithm used for finding the Minimum Spanning Tree?

1. Dijkstra's Algorithm
2. Kruskal's Algorithm
3. Bellman-Ford Algorithm
4. Prim's Algorithm

9. Question: What is the main goal of the Greedy Choice in the Fractional Knapsack Problem?

1. Maximizing total weight
2. Minimizing total value
3. Maximizing total value
4. Reducing the number of the selected items

10. Question: Which of the following describes what a Greedy Algorithm is?

1. Random selection of choices
2. Global optimization at each step is important.
3. Analyzing future decisions in detail
4. Minimizing backtracking

11. Question: What is the order of complexity for Huffman Coding using a Greedy Algorithm?

1. O(n log n)
2. O(n^2)
3. O(n)
4. O(log n)

12. Question: What is the problem that is not usually solved through a Greedy Algorithm?

1. Huffman Coding
2. Job Scheduling
3. Longest Common Subsequence
4. Activity Selection

13. Question: What is the Greedy Choice at each step in the Activity Selection Problem?

1. Selecting the first activity to start.
2. Selecting the activity with the last end time
3. Choosing activities randomly
4. Choosing the shortest activity

14. Question: What defines the Greedy Algorithms?

1. They choose locally and optimally at every stage.
2. They consider all possible solutions.
3. They reverse to locate the global best.
4. They rely on random choices.

15. Question: How many of the given problems are solved using the Greedy Algorithms?

1. Sorting
2. Searching
3. Minimum Spanning Tree
4. Dynamic Programming

16. Question: How is Huffman Coding applied?

1. Data encryption
2. Sorting
3. Data compression
4. Pathfinding

17. Question: What type of data structure is typically used in Dijkstra's algorithm to determine the shortest possible path?

1. Stack
2. Queue
3. Priority Queue
4. Linked List

18. Question: What does the Fractional Knapsack problem cover?

1. Sorting items by weight
2. Maximizing total weight
3. Maximization of the total value within a weight constraint
4. Minimizing total value

19. Question: What is the unique characteristic of Greedy Algorithms that solve the Activity Selection Problem?

1. To increase the number of activities, there are many options available to consider.
2. Reducing the number of activities can help improve your focus and productivity
3. Minimizing the total duration
4. Maximizing the total duration

20. Question: For the Job Sequencing Problem's Greedy Algorithm, what is a job-selection criterion if two jobs have equal deadlines?

1. Choose the job that has to be done first
2. Choose the job that brings in the most revenue
3. Choose a job with an upcoming deadline.
4. Choose the job with the minimum processing time

21. Question: What is the major weakness of the Greedy Algorithms?

1. They are computationally expensive
2. They may not always lead to the global optimum
3. They need a lot of memory
4. They are limited to particular cases i

22. Question: What Greedy Algorithm is designed for finding the shortest path in the weighted graphs with nonnegative edge weights?

1. Kruskal's Algorithm
2. Dijkstra's Algorithm
3. Prim's Algorithm
4. Bellman-Ford Algorithm

23. Question: What is the basic concept behind assigning the shorter codes to symbols in the Greedy Algorithm of the Huffman Coding problem?

1. To reduce computational complexity
2. To decrease the length of the encoded data
3. To increase the amount of encoded information,
4. To make the decoding process much easier

24. Question: Which of the following problems is an uncommon application of the Greedy Algorithms?

1. Shortest Path Problem
2. Huffman Coding
3. Traveling Salesman Problem
4. Matrix Multiplication

25. Question: What is the core idea of the Greedy Algorithms?

1. Dynamic Programming
2. Local optimization
3. Backtracking
4. Divide and Conquer

26. Question: What problems can be solved using the Greedy Algorithms?

1. Shortest Path
2. Knapsack Problem
3. Sorting
4. All of the above

27. Question: How does the Kruskal's algorithm work?

1. Shortest Path
2. Minimum Spanning Tree
3. Huffman Coding
4. Job Scheduling

28. Question: What kinds of characters do the shorter codes receive in Huffman Coding?

1. Frequent characters
2. Rare characters
3. Both get equal codes
4. None of the above

29. Question: What is a greedy approach to the Job Scheduling problem?

1. Earliest Deadline First (EDF)
2. Shortest Job First (SJF)
3. FCFS
4. Minimum Completion Time First

30. Question: What does Dijkstra's algorithm seek to achieve?

1. Determining the Minimum Spanning Tree by using different algorithms is important.
2. The shortest Path in a weighted graph.
3. Sorting
4. Job Scheduling

31. Question: What is the Greedy algorithm for the Fractional Knapsack Problem?

1. Kruskal's Algorithm
2. Prim's Algorithm
3. Huffman Coding
4. Greedy Choice Property

32. Question: What is the greedy decision made at each iteration in the Activity Selection Problem?

1. Select the activity with the lowest start time
2. Select the longest duration activity
3. Select the activity that finishes the earliest
4. Select the most urgent activity

33. Question: What is the Greedy Choice Property?

1. Making the locally optimal choice in each stage leads to a globally optimum solution.
2. Optimal substructure
3. Overlapping subproblems
4. None of the above

34. Question: Which algorithm employs a priority queue for its implementation?

1. Dijkstra's Algorithm
2. Prim's Algorithm
3. Huffman Coding
4. Both A and B

35. Question: How is The Time Complexity of the Huffman Coding?

1. O(n log n)
2. O(n^2)
3. O(n^3)
4. O(2^n)

36. Question: In the Knapsack Problem, if a part of an item can be put in the knapsack, it is called:

1. Fractional Knapsack Problem
2. 0/1 Knapsack Problem
3. Multiple Knapsack Problem
4. Subset Sum Problem

37. Question: What Greedy Algorithm is commonly used to optimize the files' merge pattern?

1. Huffman Coding
2. Kruskal's Algorithm
3. Prim's Algorithm
4. Optimal Merge Pattern

38. Question: How can we determine the Greedy choice in the Huffman Coding algorithm?

1. Select the least frequent character
2. Select the most frequent character in the given sentence
3. Choose characters randomly
4. Select characters alphabetically

39. Question: What is NOT the feature of Greedy Algorithms?

1. Greedy Choice Property
2. Optimal Substructure
3. Overlapping Subproblems
4. Backtracking

40. Question: What is the runtime performance of searching an element in a balanced BST?

1. O(log n)
2. O(n)
3. O(n log n)
4. O(1)

41. Question: What data structure has the Last In, First Out (LIFO) ordering?

1. Queue
2. Stack
3. Linked List
4. Heap

42. Question: Why do we have the breadth-first search (BFS) algorithm?

1. The shortest path in a weighted graph is always important to find.
2. Re-arrange the elements in an array
3. Go through a tree or graph vertically
4. Find any element in the array

43. Question: What sorting algorithm has the best average-case time complexity?

1. Bubble Sort
2. Merge Sort
3. Quick Sort
4. Insertion Sort

44. Question: Which of the following is a dynamic programming algorithm?

1. Quicksort
2. Breadth-First Search
3. Bellman-Ford
4. Binary Search