CS Algorithms & Data Structures 3 — Questions and Answers
Question 1: Dijkstra's shortest path algorithm fails to produce correct results when the graph contains what?
- Negative edge weights (Correct answer)
- Cycles
- Self-loops
- Parallel edges
Correct answer: Negative edge weights
Dijkstra assumes settled vertices are final, an invariant that negative edges can violate.
Question 2: Which sorting algorithm is stable and runs in O(n log n) time in the worst case?
- Merge sort (Correct answer)
- Quicksort
- Heapsort
- Selection sort
Correct answer: Merge sort
Merge sort preserves the relative order of equal keys and guarantees O(n log n) in all cases.
Question 3: A programmer needs constant-time insertion and deletion at both ends of a sequence. Which structure fits best?
- Doubly linked list (deque) (Correct answer)
- Dynamic array
- Binary search tree
- Singly linked list
Correct answer: Doubly linked list (deque)
A doubly linked list or deque supports O(1) insertion and removal at both head and tail.
Question 4: What is the primary advantage of an AVL tree over a plain binary search tree?
- Guaranteed O(log n) operations via balancing (Correct answer)
- Lower memory usage per node
- Faster in-order traversal
- Support for duplicate keys
Correct answer: Guaranteed O(log n) operations via balancing
AVL rotations keep the tree height logarithmic, preventing the O(n) degeneration of an unbalanced BST.
Question 5: The recurrence T(n) = 2T(n/2) + O(n) solves to which complexity?
- O(n log n) (Correct answer)
- O(n^2)
- O(n)
- O(log n)
Correct answer: O(n log n)
By the master theorem, splitting into two half-size problems with linear combine work gives O(n log n).
Question 6: Which of the following problems is a classic application of dynamic programming?
- Longest common subsequence (Correct answer)
- Binary search
- Topological sort
- Finding the minimum of an array
Correct answer: Longest common subsequence
LCS has overlapping subproblems and optimal substructure, the two hallmarks of dynamic programming.
Question 7: In a circular queue implemented with an array of size k, what condition typically indicates the queue is full when one slot is kept empty?
- (rear + 1) % k == front (Correct answer)
- rear == front
- rear == k - 1
- front == 0
Correct answer: (rear + 1) % k == front
Keeping one slot empty lets (rear + 1) % k == front unambiguously signal a full queue.
CS Algorithms & Data Structures 3
Dijkstra's shortest path algorithm fails to produce correct results when the graph contains what?