BSCS Bachelor of Science in Computer Science: Algorithms and Data Structures 5 — Questions and Answers
Question 1: What is the load factor of a hash table, and why does it matter?
- The ratio of collisions to insertions; it determines memory usage
- The ratio of stored elements to total buckets; it affects average lookup time (Correct answer)
- The number of elements divided by the hash function range squared
- The percentage of buckets using chaining versus open addressing
Correct answer: The ratio of stored elements to total buckets; it affects average lookup time
Load factor λ = n/m (elements/buckets) directly controls collision frequency; as λ approaches 1, average search time degrades significantly.
Question 2: Which traversal of a binary search tree produces keys in sorted ascending order?
- Preorder
- Postorder
- Inorder (Correct answer)
- Level-order
Correct answer: Inorder
Inorder traversal visits left subtree, root, then right subtree; in a BST this produces keys in non-decreasing order.
Question 3: What problem does the Bellman-Ford algorithm solve that Dijkstra's cannot?
- Single-source shortest paths in unweighted graphs
- Single-source shortest paths in graphs with negative-weight edges (Correct answer)
- All-pairs shortest paths in dense graphs
- Minimum spanning tree in directed graphs
Correct answer: Single-source shortest paths in graphs with negative-weight edges
Bellman-Ford handles negative edge weights and detects negative-weight cycles, whereas Dijkstra's algorithm requires non-negative weights to guarantee correctness.
Question 4: What is the worst-case time complexity of searching in a hash table with chaining when the load factor is λ?
- O(1)
- O(log n)
- O(λ)
- O(n) (Correct answer)
Correct answer: O(n)
In the worst case, all n elements hash to the same bucket, making search O(n) regardless of the load factor.
Question 5: In the context of NP-completeness, what does a polynomial-time reduction from problem A to problem B imply?
- A is easier than B
- If B can be solved in polynomial time, so can A (Correct answer)
- A and B have the same number of solutions
- B requires exponential time to solve
Correct answer: If B can be solved in polynomial time, so can A
A poly-time reduction transforms any instance of A into an instance of B in polynomial time, so a poly-time solver for B yields a poly-time solver for A.
Question 6: Which data structure supports O(1) amortized push and pop operations and is the basis for function call management?
- Queue
- Stack (Correct answer)
- Deque
- Priority queue
Correct answer: Stack
A stack provides O(1) push and pop, and the call stack uses this structure to manage function invocations, local variables, and return addresses.
Question 7: What is the time complexity of building a heap from an unsorted array of n elements?
- O(n log n)
- O(n²)
- O(n) (Correct answer)
- O(log n)
Correct answer: O(n)
The linear-time heap construction (bottom-up heapify) runs in O(n) because lower-level nodes require less work, and the summed series converges to O(n).
BSCS Bachelor of Science in Computer Science: Algorithms and Data Structures 5
What is the load factor of a hash table, and why does it matter?