CS Algorithms & Data Structures 2 — Questions and Answers
Question 1: What is the worst-case time complexity of quicksort when the pivot is always the smallest element?
- O(n^2) (Correct answer)
- O(n log n)
- O(n)
- O(log n)
Correct answer: O(n^2)
A consistently bad pivot creates maximally unbalanced partitions, degrading quicksort to O(n^2).
Question 2: Which data structure is most appropriate for implementing an undo feature in a text editor?
- Stack (Correct answer)
- Queue
- Heap
- Hash table
Correct answer: Stack
Undo requires reversing the most recent action first, which matches a stack's LIFO behavior.
Question 3: In a min-heap with n elements, what is the time complexity of finding the maximum element?
- O(n) (Correct answer)
- O(1)
- O(log n)
- O(n log n)
Correct answer: O(n)
The maximum in a min-heap must be a leaf, so roughly half the nodes must be scanned, giving O(n).
Question 4: Which traversal of a binary search tree visits nodes in ascending sorted order?
- In-order (Correct answer)
- Pre-order
- Post-order
- Level-order
Correct answer: In-order
In-order traversal visits left subtree, node, then right subtree, yielding sorted order in a BST.
Question 5: A hash table with separate chaining has n keys stored in m buckets. What is the expected time for a successful search assuming uniform hashing?
- O(1 + n/m) (Correct answer)
- O(log n)
- O(m)
- O(n log m)
Correct answer: O(1 + n/m)
Expected search time is proportional to the load factor n/m plus the constant hash computation.
Question 6: Which algorithm design technique does merge sort primarily use?
- Divide and conquer (Correct answer)
- Dynamic programming
- Greedy strategy
- Backtracking
Correct answer: Divide and conquer
Merge sort splits the array in half, recursively sorts each half, and merges the results.
Question 7: What is the space complexity of a recursive depth-first search on a graph with V vertices and E edges, excluding the graph itself?
- O(V) (Correct answer)
- O(E)
- O(V + E)
- O(1)
Correct answer: O(V)
DFS needs the visited set and a recursion stack that can grow to at most V frames, giving O(V).
CS Algorithms & Data Structures 2
What is the worst-case time complexity of quicksort when the pivot is always the smallest element?