BSCS Bachelor of Science in Computer Science: Algorithms and Data Structures 5

Question 1

What is the load factor of a hash table, and why does it matter?

Accepted Answer

The ratio of stored elements to total buckets; it affects average lookup time

Answer

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?

Accepted Answer

Inorder

Answer

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?

Accepted Answer

Single-source shortest paths in graphs with negative-weight edges

Answer

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 λ?

Accepted Answer

O(n)

Answer

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?

Accepted Answer

If B can be solved in polynomial time, so can A

Answer

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.

BSCS - Bachelor of Science in Computer Science Practice Test

BSCS - Bachelor of Science in Computer Science Practice Test

BSCS Bachelor of Science in Computer Science: Algorithms and Data Structures 5