BSCS Bachelor of Science in Computer Science: Algorithms and Data Structures 2 — Questions and Answers
Question 1: What is the worst-case time complexity of quicksort?
- O(n log n)
- O(n²) (Correct answer)
- O(n)
- O(log n)
Correct answer: O(n²)
Quicksort degrades to O(n²) when the pivot is always the smallest or largest element, causing maximally unbalanced partitions.
Question 2: Which data structure is used to implement Dijkstra's shortest-path algorithm most efficiently?
- Stack
- Queue
- Min-heap (priority queue) (Correct answer)
- Hash table
Correct answer: Min-heap (priority queue)
A min-heap priority queue allows extracting the minimum-distance unvisited node in O(log n), giving Dijkstra's algorithm O((V + E) log V) overall.
Question 3: What property distinguishes a red-black tree from a standard BST?
- All leaves are at the same depth
- Each node is colored red or black with rules ensuring O(log n) height (Correct answer)
- It stores only even-valued keys in red nodes
- It allows duplicate keys in red nodes only
Correct answer: Each node is colored red or black with rules ensuring O(log n) height
Red-black trees enforce coloring invariants (e.g., no two consecutive red nodes, equal black-height on all paths) that bound tree height to O(log n).
Question 4: What does the Master Theorem solve?
- Recurrences of the form T(n) = aT(n/b) + f(n) (Correct answer)
- Dynamic programming subproblem overlaps
- Graph traversal depth limits
- Hash collision resolution strategies
Correct answer: Recurrences of the form T(n) = aT(n/b) + f(n)
The Master Theorem provides closed-form solutions for divide-and-conquer recurrences T(n) = aT(n/b) + f(n) by comparing f(n) to n^(log_b a).
Question 5: In a min-heap, which node always contains the smallest element?
- The rightmost leaf
- The leftmost leaf
- The root (Correct answer)
- The node at depth 1
Correct answer: The root
The heap property guarantees that every parent is ≤ its children, so the minimum element always resides at the root.
Question 6: Which algorithm finds a minimum spanning tree by greedily adding the globally cheapest edge that doesn't form a cycle?
- Prim's algorithm
- Kruskal's algorithm (Correct answer)
- Bellman-Ford algorithm
- Floyd-Warshall algorithm
Correct answer: Kruskal's algorithm
Kruskal's algorithm sorts all edges by weight and adds the cheapest edge to the MST as long as it doesn't create a cycle, using a union-find structure.
Question 7: What is the space complexity of a recursive depth-first search on a graph with V vertices and E edges?
- O(1)
- O(E)
- O(V) (Correct answer)
- O(V + E)
Correct answer: O(V)
The recursion stack in DFS can hold at most V frames (one per vertex on the deepest path), giving O(V) space complexity.
BSCS Bachelor of Science in Computer Science: Algorithms and Data Structures 2
What is the worst-case time complexity of quicksort?