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

Question 1

Which collision resolution strategy uses a linked list at each hash table bucket?

Accepted Answer

Chaining

Answer

Chaining stores all keys that hash to the same bucket in a linked list, allowing unlimited collisions at the cost of extra pointer memory.

Question 2

What is the time complexity of inserting an element into a balanced AVL tree with n nodes?

Accepted Answer

O(log n)

Answer

AVL trees maintain O(log n) height through rotations, so insertion requires O(log n) time for the search path plus at most O(log n) rotation steps.

Question 3

In dynamic programming, what term describes subproblems whose solutions are reused multiple times?

Accepted Answer

Overlapping subproblems

Answer

Overlapping subproblems means the same subproblem recurs repeatedly; DP exploits this by caching results instead of recomputing them.

Question 4

What does a topological sort of a directed acyclic graph (DAG) produce?

Accepted Answer

A linear ordering where each vertex appears before all vertices it has edges to

Answer

Topological sort orders vertices so that for every directed edge u→v, u comes before v, which is only possible for DAGs.

Question 5

Which of the following best describes amortized analysis?

Accepted Answer

The average cost per operation over a worst-case sequence of operations

Answer

Amortized analysis spreads the cost of expensive operations over a sequence, giving a per-operation average even in the worst case.

BSCS - Bachelor of Science in Computer Science Practice Test