BSCS Bachelor of Science in Computer Science: Algorithms and Data Structures 3 ā Questions and Answers
Question 1: Which collision resolution strategy uses a linked list at each hash table bucket?
- Open addressing
- Linear probing
- Chaining (Correct answer)
- Double hashing
Correct answer: Chaining
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?
- O(1)
- O(log n) (Correct answer)
- O(n)
- O(n log n)
Correct answer: O(log n)
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?
- Optimal substructure
- Greedy choice
- Overlapping subproblems (Correct answer)
- Memoization boundary
Correct answer: Overlapping subproblems
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?
- A minimum spanning tree
- A linear ordering where each vertex appears before all vertices it has edges to (Correct answer)
- The shortest path between all pairs of vertices
- A sorted array of edge weights
Correct answer: A linear ordering where each vertex appears before all vertices it has edges to
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?
- The average-case cost assuming random input
- The average cost per operation over a worst-case sequence of operations (Correct answer)
- The minimum cost of any single operation
- The expected cost under a probability distribution
Correct answer: The average cost per operation over a worst-case sequence of operations
Amortized analysis spreads the cost of expensive operations over a sequence, giving a per-operation average even in the worst case.
Question 6: What is the output of a breadth-first search (BFS) traversal starting from the source vertex?
- Vertices in decreasing order of degree
- Vertices in order of increasing distance from the source (Correct answer)
- A minimum spanning tree
- Vertices sorted by discovery time
Correct answer: Vertices in order of increasing distance from the source
BFS explores vertices layer by layer, visiting all vertices at distance d before any vertex at distance d+1, producing shortest-path distances in unweighted graphs.
Question 7: Which sorting algorithm is stable and has O(n log n) worst-case time complexity?
- Quicksort
- Heapsort
- Merge sort (Correct answer)
- Selection sort
Correct answer: Merge sort
Merge sort is stable (preserves relative order of equal elements) and guarantees O(n log n) in all cases by recursively merging sorted halves.
BSCS Bachelor of Science in Computer Science: Algorithms and Data Structures 3
Which collision resolution strategy uses a linked list at each hash table bucket?