C949 ICSC 2100
Data Structures & Algorithms I
4.0 Credits
Objective Assessment Review (Qns &
Ans)
2025
©2025
,**Question 1:*
Which property distinguishes problems that are well suited for dynamic
programming as opposed to a simple divide‐and‑conquer approach?
A. Problems with independent subproblems
B. Problems with overlapping subproblems and optimal substructure
C. Problems that can be solved using recursion
D. Problems that are parallelizable without coordination
**Correct ANS:* B. Problems with overlapping subproblems and optimal
substructure
**Rationale:*
Dynamic programming is effective for problems where the subproblems
overlap and share common computations. In contrast, divide‐
and‑conquer typically divides the problem into independent
subproblems. Recognizing overlapping subproblems allows the use of
memoization to avoid redundant work.
---
**Question 2:*
What is the worst‑case time complexity of QuickSort when the pivot
selection consistently produces extremely unbalanced partitions (for
example, always choosing the smallest element as the pivot)?
A. O(n)
B. O(n log n)
C. O(n²)
D. O(log n)
**Correct ANS:* C. O(n²)
**Rationale:*
When the pivot is chosen poorly—such as always selecting the smallest
element in an already sorted array—QuickSort degrades to O(n²) time
©2025
, complexity because the recursive partitioning produces one subproblem
of size n–1 and one of size 0 at every step.
---
**Question 3:*
Which balanced binary search tree guarantees that for every node the
heights of the left and right subtrees differ by at most one?
A. Red‑Black Tree
B. AVL Tree
C. Splay Tree
D. B‑Tree
**Correct ANS:* B. AVL Tree
**Rationale:*
An AVL tree enforces a strict balance condition by maintaining a
maximum height difference of one between the left and right subtrees at
every node. This strict balancing provides excellent lookup performance,
albeit at a cost of more frequent rebalancing during insertions and
deletions.
---
**Question 4:*
Which algorithm is typically used to construct a minimum spanning tree
in a connected, weighted graph with non‑negative edge weights?
A. Dijkstra’s algorithm
B. Kruskal’s algorithm
C. Bellman‑Ford algorithm
D. Floyd‑Warshall algorithm
**Correct ANS:* B. Kruskal’s algorithm
**Rationale:*
Kruskal’s algorithm builds a minimum spanning tree (MST) by repeatedly
selecting the smallest edge that does not form a cycle. It is especially
©2025
Data Structures & Algorithms I
4.0 Credits
Objective Assessment Review (Qns &
Ans)
2025
©2025
,**Question 1:*
Which property distinguishes problems that are well suited for dynamic
programming as opposed to a simple divide‐and‑conquer approach?
A. Problems with independent subproblems
B. Problems with overlapping subproblems and optimal substructure
C. Problems that can be solved using recursion
D. Problems that are parallelizable without coordination
**Correct ANS:* B. Problems with overlapping subproblems and optimal
substructure
**Rationale:*
Dynamic programming is effective for problems where the subproblems
overlap and share common computations. In contrast, divide‐
and‑conquer typically divides the problem into independent
subproblems. Recognizing overlapping subproblems allows the use of
memoization to avoid redundant work.
---
**Question 2:*
What is the worst‑case time complexity of QuickSort when the pivot
selection consistently produces extremely unbalanced partitions (for
example, always choosing the smallest element as the pivot)?
A. O(n)
B. O(n log n)
C. O(n²)
D. O(log n)
**Correct ANS:* C. O(n²)
**Rationale:*
When the pivot is chosen poorly—such as always selecting the smallest
element in an already sorted array—QuickSort degrades to O(n²) time
©2025
, complexity because the recursive partitioning produces one subproblem
of size n–1 and one of size 0 at every step.
---
**Question 3:*
Which balanced binary search tree guarantees that for every node the
heights of the left and right subtrees differ by at most one?
A. Red‑Black Tree
B. AVL Tree
C. Splay Tree
D. B‑Tree
**Correct ANS:* B. AVL Tree
**Rationale:*
An AVL tree enforces a strict balance condition by maintaining a
maximum height difference of one between the left and right subtrees at
every node. This strict balancing provides excellent lookup performance,
albeit at a cost of more frequent rebalancing during insertions and
deletions.
---
**Question 4:*
Which algorithm is typically used to construct a minimum spanning tree
in a connected, weighted graph with non‑negative edge weights?
A. Dijkstra’s algorithm
B. Kruskal’s algorithm
C. Bellman‑Ford algorithm
D. Floyd‑Warshall algorithm
**Correct ANS:* B. Kruskal’s algorithm
**Rationale:*
Kruskal’s algorithm builds a minimum spanning tree (MST) by repeatedly
selecting the smallest edge that does not form a cycle. It is especially
©2025
