Module 6 Quiz and answers verified to
pass 2025
Which of the following algorithms constructs a minimum spanning tree on a
graph by "jumping" around the graph, placing edges between nodes in
ascending order of edge cost? - correct answer Kruskal's algorithm
Which of the following algorithms constructs a minimum spanning tree on a
graph by starting at a root node and "growing" the tree outwards from the root,
adding edges in ascending order of edge cost? - correct answer Prim's
algorithm
Which of the following algorithms constructs a minimum spanning tree on a
graph by starting with a full graph, and deleting edges in descending order of
edge cost? - correct answer Reverse-Delete algorithm
Which of the following best explains why the running time of Kruskal's
algorithm can never be better than O(m log n) in the worst case? - correct
answer The edges of the graph must be sorted in ascending order initially.
With respect to the implementation of Kruskal's algorithm, which of the
following can be done to ensure the running time of the Find operation of the
Union-Find data structure never exceeds O(log n)? - correct answer When
two subsets are joined, the name of the larger subset is used to name the set
that results from the union.
Which of the following statements are true regarding the clustering problem?
(Select all that apply.) - correct answer The clustering problem can be solved
by running Kruskal's algorithm until it has added all but the k - 1 most
expensive edges.
pass 2025
Which of the following algorithms constructs a minimum spanning tree on a
graph by "jumping" around the graph, placing edges between nodes in
ascending order of edge cost? - correct answer Kruskal's algorithm
Which of the following algorithms constructs a minimum spanning tree on a
graph by starting at a root node and "growing" the tree outwards from the root,
adding edges in ascending order of edge cost? - correct answer Prim's
algorithm
Which of the following algorithms constructs a minimum spanning tree on a
graph by starting with a full graph, and deleting edges in descending order of
edge cost? - correct answer Reverse-Delete algorithm
Which of the following best explains why the running time of Kruskal's
algorithm can never be better than O(m log n) in the worst case? - correct
answer The edges of the graph must be sorted in ascending order initially.
With respect to the implementation of Kruskal's algorithm, which of the
following can be done to ensure the running time of the Find operation of the
Union-Find data structure never exceeds O(log n)? - correct answer When
two subsets are joined, the name of the larger subset is used to name the set
that results from the union.
Which of the following statements are true regarding the clustering problem?
(Select all that apply.) - correct answer The clustering problem can be solved
by running Kruskal's algorithm until it has added all but the k - 1 most
expensive edges.
