WGU C950 Data Structures and Algorithms II: Practice Test 2
(Units 8-13) - Questions with Correct Answers
100 questions
1. Path reconstruction in Dijkstra's algorithm uses:
A. A second graph
B. Sorting
C. Hashing only
D. A predecessor (previous) array or map
Correct Answer: D. A predecessor (previous) array or map
Rationale: Backtrack from target.
2. Shortest path problems with time windows (deliveries must arrive by deadlines) are:
A. Simpler than plain shortest path
B. Solved by BFS
C. Solved by sorting
D. Harder variants requiring scheduling constraints
Correct Answer: D. Harder variants requiring scheduling constraints
Rationale: VRPTW.
3. The output of Floyd-Warshall is:
A. A matrix of shortest distances between every pair
B. A single path
C. A tree
D. A tour
Correct Answer: A. A matrix of shortest distances between every pair
Rationale: All-pairs matrix.
4. Straight-line (Euclidean) distance is an admissible heuristic for road routing because:
A. Actual road distance is never shorter than straight-line distance
B. It is always exact
C. It is negative
D. It ignores direction
Correct Answer: A. Actual road distance is never shorter than straight-line distance
Rationale: Lower bound.
5. Dijkstra's algorithm finalizes a vertex when:
A. It is removed from the priority queue with the smallest tentative distance
B. It is first discovered
C. All edges are sorted
D. The algorithm ends
Correct Answer: A. It is removed from the priority queue with the smallest tentative distance
Rationale: Greedy finalization.
6. Johnson's algorithm computes all-pairs shortest paths efficiently for:
A. Dense graphs only
B. Unweighted graphs only
C. Trees only
D. Sparse graphs, including some negative weights
Correct Answer: D. Sparse graphs, including some negative weights
Rationale: Reweighting plus Dijkstra.
,7. Precomputing a full distance matrix for n addresses allows:
A. No lookups
B. Negative cycles
C. O(1) distance lookups during routing
D. Sorting
Correct Answer: C. O(1) distance lookups during routing
Rationale: Efficiency.
8. Dijkstra's algorithm finds:
A. Minimum spanning trees
B. All-pairs shortest paths with negative cycles
C. Shortest paths from a single source to all vertices in a graph with non-negative weights
D. Maximum flow
Correct Answer: C. Shortest paths from a single source to all vertices in a graph with
non-negative weights
Rationale: Single-source.
9. The main difference between Dijkstra's and Prim's algorithm is that Dijkstra's minimizes:
A. Edge weight connecting to the tree
B. Number of edges
C. Tree height
D. Total distance from the source
Correct Answer: D. Total distance from the source
Rationale: Similar structure, different key.
10. Floyd-Warshall time complexity is:
A. O(V^2)
B. O(V + E)
C. O(V^3)
D. O(E log V)
Correct Answer: C. O(V^3)
Rationale: Triple loop.
11. Which algorithm would you choose for single-source shortest paths with negative weights
but no negative cycles?
A. Dijkstra
B. Bellman-Ford
C. Prim
D. Kruskal
Correct Answer: B. Bellman-Ford
Rationale: Handles negatives.
12. Routing services (e.g., GPS) commonly use algorithms based on:
A. Bubble sort
B. Hash tables only
C. Linear search
D. Dijkstra's and A* with preprocessing
Correct Answer: D. Dijkstra's and A* with preprocessing
Rationale: Practical routing.
, 13. Which algorithm is best for all-pairs shortest paths in a small dense graph?
A. BFS
B. Floyd-Warshall
C. Kruskal
D. Prim
Correct Answer: B. Floyd-Warshall
Rationale: Simple O(V^3).
14. Finding an address's row index by linear search through a list of addresses costs:
A. O(1)
B. O(log n)
C. O(n) per lookup
D. O(n^2)
Correct Answer: C. O(n) per lookup
Rationale: Use a hash map to improve.
15. A shortest-path tree is:
A. A minimum spanning tree always
B. A heap
C. A trie
D. A tree formed by the shortest paths from the source to all vertices
Correct Answer: D. A tree formed by the shortest paths from the source to all vertices
Rationale: Can differ from MST.
16. For A* to guarantee an optimal path, the heuristic must be:
A. Admissible (never overestimates the true cost)
B. Always zero
C. Always larger than true cost
D. Random
Correct Answer: A. Admissible (never overestimates the true cost)
Rationale: Admissibility.
17. Floyd-Warshall uses which technique?
A. Dynamic programming
B. Greedy
C. Divide and conquer
D. Backtracking
Correct Answer: A. Dynamic programming
Rationale: Intermediate vertices.
18. Disjoint set 'find' returns:
A. The set size
B. All elements
C. A sorted list
D. The representative (root) of an element's set
Correct Answer: D. The representative (root) of an element's set
Rationale: Representative.
(Units 8-13) - Questions with Correct Answers
100 questions
1. Path reconstruction in Dijkstra's algorithm uses:
A. A second graph
B. Sorting
C. Hashing only
D. A predecessor (previous) array or map
Correct Answer: D. A predecessor (previous) array or map
Rationale: Backtrack from target.
2. Shortest path problems with time windows (deliveries must arrive by deadlines) are:
A. Simpler than plain shortest path
B. Solved by BFS
C. Solved by sorting
D. Harder variants requiring scheduling constraints
Correct Answer: D. Harder variants requiring scheduling constraints
Rationale: VRPTW.
3. The output of Floyd-Warshall is:
A. A matrix of shortest distances between every pair
B. A single path
C. A tree
D. A tour
Correct Answer: A. A matrix of shortest distances between every pair
Rationale: All-pairs matrix.
4. Straight-line (Euclidean) distance is an admissible heuristic for road routing because:
A. Actual road distance is never shorter than straight-line distance
B. It is always exact
C. It is negative
D. It ignores direction
Correct Answer: A. Actual road distance is never shorter than straight-line distance
Rationale: Lower bound.
5. Dijkstra's algorithm finalizes a vertex when:
A. It is removed from the priority queue with the smallest tentative distance
B. It is first discovered
C. All edges are sorted
D. The algorithm ends
Correct Answer: A. It is removed from the priority queue with the smallest tentative distance
Rationale: Greedy finalization.
6. Johnson's algorithm computes all-pairs shortest paths efficiently for:
A. Dense graphs only
B. Unweighted graphs only
C. Trees only
D. Sparse graphs, including some negative weights
Correct Answer: D. Sparse graphs, including some negative weights
Rationale: Reweighting plus Dijkstra.
,7. Precomputing a full distance matrix for n addresses allows:
A. No lookups
B. Negative cycles
C. O(1) distance lookups during routing
D. Sorting
Correct Answer: C. O(1) distance lookups during routing
Rationale: Efficiency.
8. Dijkstra's algorithm finds:
A. Minimum spanning trees
B. All-pairs shortest paths with negative cycles
C. Shortest paths from a single source to all vertices in a graph with non-negative weights
D. Maximum flow
Correct Answer: C. Shortest paths from a single source to all vertices in a graph with
non-negative weights
Rationale: Single-source.
9. The main difference between Dijkstra's and Prim's algorithm is that Dijkstra's minimizes:
A. Edge weight connecting to the tree
B. Number of edges
C. Tree height
D. Total distance from the source
Correct Answer: D. Total distance from the source
Rationale: Similar structure, different key.
10. Floyd-Warshall time complexity is:
A. O(V^2)
B. O(V + E)
C. O(V^3)
D. O(E log V)
Correct Answer: C. O(V^3)
Rationale: Triple loop.
11. Which algorithm would you choose for single-source shortest paths with negative weights
but no negative cycles?
A. Dijkstra
B. Bellman-Ford
C. Prim
D. Kruskal
Correct Answer: B. Bellman-Ford
Rationale: Handles negatives.
12. Routing services (e.g., GPS) commonly use algorithms based on:
A. Bubble sort
B. Hash tables only
C. Linear search
D. Dijkstra's and A* with preprocessing
Correct Answer: D. Dijkstra's and A* with preprocessing
Rationale: Practical routing.
, 13. Which algorithm is best for all-pairs shortest paths in a small dense graph?
A. BFS
B. Floyd-Warshall
C. Kruskal
D. Prim
Correct Answer: B. Floyd-Warshall
Rationale: Simple O(V^3).
14. Finding an address's row index by linear search through a list of addresses costs:
A. O(1)
B. O(log n)
C. O(n) per lookup
D. O(n^2)
Correct Answer: C. O(n) per lookup
Rationale: Use a hash map to improve.
15. A shortest-path tree is:
A. A minimum spanning tree always
B. A heap
C. A trie
D. A tree formed by the shortest paths from the source to all vertices
Correct Answer: D. A tree formed by the shortest paths from the source to all vertices
Rationale: Can differ from MST.
16. For A* to guarantee an optimal path, the heuristic must be:
A. Admissible (never overestimates the true cost)
B. Always zero
C. Always larger than true cost
D. Random
Correct Answer: A. Admissible (never overestimates the true cost)
Rationale: Admissibility.
17. Floyd-Warshall uses which technique?
A. Dynamic programming
B. Greedy
C. Divide and conquer
D. Backtracking
Correct Answer: A. Dynamic programming
Rationale: Intermediate vertices.
18. Disjoint set 'find' returns:
A. The set size
B. All elements
C. A sorted list
D. The representative (root) of an element's set
Correct Answer: D. The representative (root) of an element's set
Rationale: Representative.
