WGU C950 Data Structures and Algorithms II: Final Exam
(Comprehensive) - Questions with Correct Answers
100 questions
1. Chaining is often preferred over open addressing when:
A. Memory is extremely limited
B. Keys never collide
C. The load factor may exceed 1 or deletions are frequent
D. The table is tiny
Correct Answer: C. The load factor may exceed 1 or deletions are frequent
Rationale: Flexibility.
2. A bucket implemented as a Python list of [key, value] pairs supports:
A. Open addressing
B. Chaining
C. Binary search
D. Heaps
Correct Answer: B. Chaining
Rationale: Common C950 approach.
3. Binary search on 1,024 sorted items needs at most about how many comparisons?
A. 11
B. 1024
C. 512
D. 100
Correct Answer: A. 11
Rationale: log2(1024) = 10, plus 1.
4. The best general-purpose comparison sort guaranteeing O(n log n) worst case with O(1) extra
space is:
A. Quick sort
B. Heap sort
C. Merge sort
D. Bubble sort
Correct Answer: B. Heap sort
Rationale: Heap sort.
5. Memoized Fibonacci has time complexity:
A. O(2^n)
B. O(n^2)
C. O(n)
D. O(log n)
Correct Answer: C. O(n)
Rationale: Each value computed once.
6. Naive recursive Fibonacci has time complexity of about:
A. O(n)
B. O(log n)
C. O(n^2)
D. O(2^n)
Correct Answer: D. O(2^n)
Rationale: Overlapping subproblems.
,7. An AVL rotation takes:
A. O(1) time
B. O(n) time
C. O(log n) time
D. O(n^2) time
Correct Answer: A. O(1) time
Rationale: Constant pointer changes.
8. A circular linked list:
A. Has no nodes
B. Has the last node pointing back to the first
C. Is a tree
D. Is sorted
Correct Answer: B. Has the last node pointing back to the first
Rationale: Round-robin uses.
9. Which representation lets you list all neighbors of a vertex fastest in a sparse graph?
A. Adjacency matrix
B. Edge list unsorted
C. Incidence matrix
D. Adjacency list
Correct Answer: D. Adjacency list
Rationale: Neighbors stored directly.
10. A graph consists of:
A. Only nodes
B. Only edges
C. Keys and values only
D. Vertices (nodes) and edges
Correct Answer: D. Vertices (nodes) and edges
Rationale: G = (V, E).
11. Edge relaxation means:
A. Updating a vertex's distance if a shorter path through another vertex is found
B. Removing an edge
C. Sorting edges
D. Adding weights randomly
Correct Answer: A. Updating a vertex's distance if a shorter path through another vertex is
found
Rationale: Core step.
12. Dijkstra's algorithm starting at the WGUPS hub would give:
A. The optimal delivery tour
B. A minimum spanning tree
C. Package deadlines
D. The shortest distance from the hub to every address
Correct Answer: D. The shortest distance from the hub to every address
Rationale: Not a TSP solution.
, 13. Relaxation in Bellman-Ford is repeated V - 1 times because:
A. The longest simple path has at most V - 1 edges
B. There are V - 1 vertices
C. It is a guess
D. Edges are sorted
Correct Answer: A. The longest simple path has at most V - 1 edges
Rationale: Correctness.
14. Dijkstra's algorithm space complexity is:
A. O(V^3)
B. O(1)
C. O(E^2)
D. O(V) for distances plus graph storage
Correct Answer: D. O(V) for distances plus graph storage
Rationale: Distance array.
15. Dijkstra's algorithm is an example of a:
A. Divide and conquer algorithm
B. Brute-force search
C. Greedy algorithm
D. Backtracking algorithm
Correct Answer: C. Greedy algorithm
Rationale: Picks closest unvisited.
16. If a delivery address is corrected mid-day in WGUPS, the program must:
A. Update the package's address and recompute affected routing
B. Ignore the change
C. Delete the package
D. Restart the day
Correct Answer: A. Update the package's address and recompute affected routing
Rationale: Package 9 scenario.
17. Shortest path algorithms alone do NOT solve the delivery routing problem because:
A. They cannot find distances
B. They need negative weights
C. Routing requires visiting many stops in a good order (a TSP/VRP problem)
D. They are too fast
Correct Answer: C. Routing requires visiting many stops in a good order (a TSP/VRP
problem)
Rationale: Different problem.
18. In a graph with all edge weights equal, the shortest path can be found with:
A. Bellman-Ford only
B. Floyd-Warshall only
C. BFS
D. Kruskal
Correct Answer: C. BFS
Rationale: Unweighted.
(Comprehensive) - Questions with Correct Answers
100 questions
1. Chaining is often preferred over open addressing when:
A. Memory is extremely limited
B. Keys never collide
C. The load factor may exceed 1 or deletions are frequent
D. The table is tiny
Correct Answer: C. The load factor may exceed 1 or deletions are frequent
Rationale: Flexibility.
2. A bucket implemented as a Python list of [key, value] pairs supports:
A. Open addressing
B. Chaining
C. Binary search
D. Heaps
Correct Answer: B. Chaining
Rationale: Common C950 approach.
3. Binary search on 1,024 sorted items needs at most about how many comparisons?
A. 11
B. 1024
C. 512
D. 100
Correct Answer: A. 11
Rationale: log2(1024) = 10, plus 1.
4. The best general-purpose comparison sort guaranteeing O(n log n) worst case with O(1) extra
space is:
A. Quick sort
B. Heap sort
C. Merge sort
D. Bubble sort
Correct Answer: B. Heap sort
Rationale: Heap sort.
5. Memoized Fibonacci has time complexity:
A. O(2^n)
B. O(n^2)
C. O(n)
D. O(log n)
Correct Answer: C. O(n)
Rationale: Each value computed once.
6. Naive recursive Fibonacci has time complexity of about:
A. O(n)
B. O(log n)
C. O(n^2)
D. O(2^n)
Correct Answer: D. O(2^n)
Rationale: Overlapping subproblems.
,7. An AVL rotation takes:
A. O(1) time
B. O(n) time
C. O(log n) time
D. O(n^2) time
Correct Answer: A. O(1) time
Rationale: Constant pointer changes.
8. A circular linked list:
A. Has no nodes
B. Has the last node pointing back to the first
C. Is a tree
D. Is sorted
Correct Answer: B. Has the last node pointing back to the first
Rationale: Round-robin uses.
9. Which representation lets you list all neighbors of a vertex fastest in a sparse graph?
A. Adjacency matrix
B. Edge list unsorted
C. Incidence matrix
D. Adjacency list
Correct Answer: D. Adjacency list
Rationale: Neighbors stored directly.
10. A graph consists of:
A. Only nodes
B. Only edges
C. Keys and values only
D. Vertices (nodes) and edges
Correct Answer: D. Vertices (nodes) and edges
Rationale: G = (V, E).
11. Edge relaxation means:
A. Updating a vertex's distance if a shorter path through another vertex is found
B. Removing an edge
C. Sorting edges
D. Adding weights randomly
Correct Answer: A. Updating a vertex's distance if a shorter path through another vertex is
found
Rationale: Core step.
12. Dijkstra's algorithm starting at the WGUPS hub would give:
A. The optimal delivery tour
B. A minimum spanning tree
C. Package deadlines
D. The shortest distance from the hub to every address
Correct Answer: D. The shortest distance from the hub to every address
Rationale: Not a TSP solution.
, 13. Relaxation in Bellman-Ford is repeated V - 1 times because:
A. The longest simple path has at most V - 1 edges
B. There are V - 1 vertices
C. It is a guess
D. Edges are sorted
Correct Answer: A. The longest simple path has at most V - 1 edges
Rationale: Correctness.
14. Dijkstra's algorithm space complexity is:
A. O(V^3)
B. O(1)
C. O(E^2)
D. O(V) for distances plus graph storage
Correct Answer: D. O(V) for distances plus graph storage
Rationale: Distance array.
15. Dijkstra's algorithm is an example of a:
A. Divide and conquer algorithm
B. Brute-force search
C. Greedy algorithm
D. Backtracking algorithm
Correct Answer: C. Greedy algorithm
Rationale: Picks closest unvisited.
16. If a delivery address is corrected mid-day in WGUPS, the program must:
A. Update the package's address and recompute affected routing
B. Ignore the change
C. Delete the package
D. Restart the day
Correct Answer: A. Update the package's address and recompute affected routing
Rationale: Package 9 scenario.
17. Shortest path algorithms alone do NOT solve the delivery routing problem because:
A. They cannot find distances
B. They need negative weights
C. Routing requires visiting many stops in a good order (a TSP/VRP problem)
D. They are too fast
Correct Answer: C. Routing requires visiting many stops in a good order (a TSP/VRP
problem)
Rationale: Different problem.
18. In a graph with all edge weights equal, the shortest path can be found with:
A. Bellman-Ford only
B. Floyd-Warshall only
C. BFS
D. Kruskal
Correct Answer: C. BFS
Rationale: Unweighted.
