COP 3530
Data Structures & Algorithm
4.0 Credits
Final Exam Review (Qns & Ans)
2025
©2025
, Multiple Choice Questions
1. Question:
In the analysis of dynamic arrays, which concept best explains
why insertions have an amortized cost of O(1)?
A. Worst‑case analysis
B. Aggregate analysis
C. Probabilistic analysis
D. Recurrence relation analysis
Correct ANS: B. Aggregate analysis
Rationale:
Aggregate analysis sums the total cost of a sequence of
operations (including occasional expensive resizing operations)
and divides by the number of operations, showing that the average
(amortized) cost per insertion is O(1).
2. Question:
Consider a self‑balancing binary search tree used for dynamic
ordered data. Which of the following trees guarantees O(log n)
worst‑case search, insertion, and deletion operations?
A. Binary Search Tree (without balancing)
B. Red‑Black Tree
C. Splay Tree
D. B‑Tree of order 2
Correct ANS: B. Red‑Black Tree
Rationale:
A Red‑Black tree enforces a balanced structure using coloring
properties, ensuring that operations run in O(log n) time in the
worst case.
3. Question:
Which advanced data structure is especially useful for ANSing
range queries (e.g., sum or minimum over an interval) on an array
with frequent updates?
A. Binary Search Tree
©2025
, B. Segment Tree
C. Hash Table
D. Linked List
Correct ANS: B. Segment Tree
Rationale:
The segment tree is designed for efficient range queries and
modifications on arrays, with update and query operations typically
executing in O(log n) time.
4. Question:
In graph algorithms, which data structure is preferred for
implementing Dijkstra's algorithm when the graph is dense, to
improve efficiency?
A. Binary Heap
B. Fibonacci Heap
C. Queue
D. Stack
Correct ANS: B. Fibonacci Heap
Rationale:
Although Fibonacci heaps have a higher constant factor, their
decrease‑key operation runs in O(1) amortized time, making them
more efficient for dense graphs in Dijkstra’s algorithm.
5. Question:
When analyzing the worst‑case performance of union‑find
(disjoint-set) with both union by rank and path compression, what is
the complexity per operation (amortized)?
A. O(1)
B. O(α(n)) (inverse Ackermann function)
C. O(log n)
D. O(n)
Correct ANS: B. O(α(n))
Rationale:
With union by rank and path compression, the amortized time per
©2025
Data Structures & Algorithm
4.0 Credits
Final Exam Review (Qns & Ans)
2025
©2025
, Multiple Choice Questions
1. Question:
In the analysis of dynamic arrays, which concept best explains
why insertions have an amortized cost of O(1)?
A. Worst‑case analysis
B. Aggregate analysis
C. Probabilistic analysis
D. Recurrence relation analysis
Correct ANS: B. Aggregate analysis
Rationale:
Aggregate analysis sums the total cost of a sequence of
operations (including occasional expensive resizing operations)
and divides by the number of operations, showing that the average
(amortized) cost per insertion is O(1).
2. Question:
Consider a self‑balancing binary search tree used for dynamic
ordered data. Which of the following trees guarantees O(log n)
worst‑case search, insertion, and deletion operations?
A. Binary Search Tree (without balancing)
B. Red‑Black Tree
C. Splay Tree
D. B‑Tree of order 2
Correct ANS: B. Red‑Black Tree
Rationale:
A Red‑Black tree enforces a balanced structure using coloring
properties, ensuring that operations run in O(log n) time in the
worst case.
3. Question:
Which advanced data structure is especially useful for ANSing
range queries (e.g., sum or minimum over an interval) on an array
with frequent updates?
A. Binary Search Tree
©2025
, B. Segment Tree
C. Hash Table
D. Linked List
Correct ANS: B. Segment Tree
Rationale:
The segment tree is designed for efficient range queries and
modifications on arrays, with update and query operations typically
executing in O(log n) time.
4. Question:
In graph algorithms, which data structure is preferred for
implementing Dijkstra's algorithm when the graph is dense, to
improve efficiency?
A. Binary Heap
B. Fibonacci Heap
C. Queue
D. Stack
Correct ANS: B. Fibonacci Heap
Rationale:
Although Fibonacci heaps have a higher constant factor, their
decrease‑key operation runs in O(1) amortized time, making them
more efficient for dense graphs in Dijkstra’s algorithm.
5. Question:
When analyzing the worst‑case performance of union‑find
(disjoint-set) with both union by rank and path compression, what is
the complexity per operation (amortized)?
A. O(1)
B. O(α(n)) (inverse Ackermann function)
C. O(log n)
D. O(n)
Correct ANS: B. O(α(n))
Rationale:
With union by rank and path compression, the amortized time per
©2025
