C949 ICSC 2100 Data Structures &
Algorithms I
Finals Assessment Review
(Questions & Solutions)
2025
©2025
, Q1. In a splay tree , which mechanism ensures that the amortized cost
for operations (search, insertion, deletion) remains O(log n)?
A. Clockwise rotations
B. Randomized rebalancing
C. The splaying operation that moves accessed elements closer to the
root
D. Strict balancing at every insertion
<br> ANS: C
<br> Rationale: Splaying reorganizes the tree on each access so that
recently used nodes are near the root. Although a single operation may
take O(n) time, the amortized cost is O(log n).
---
Q2. Which of the following is a primary advantage of using a B+ tree
over a standard B-tree in database indexing?
A. Data entries are stored in all nodes for faster access.
B. Range queries are optimized because all records reside in the leaf
nodes linked sequentially.
C. It guarantees a perfectly balanced structure with no variations in node
occupancy.
D. It eliminates the need for key comparisons during search operations.
<br> ANS: B
<br> Rationale: B+ trees store all actual data records in the leaf nodes
(which are often linked), thereby enabling efficient sequential access for
range queries.
---
Q3. Which sorting algorithm is non-comparative and can achieve
linear time complexity under appropriate conditions?
©2025
, A. QuickSort
B. MergeSort
C. HeapSort
D. Radix Sort
<br> ANS: D
<br> Rationale: Radix sort leverages the properties of integer
representation by sorting on individual digits. With a fixed digit length (or
under certain assumptions), it can run in linear time.
---
Q4. In the Longest Increasing Subsequence problem solved using
dynamic programming, which property is essential to building the
solution?
A. Greedy-choice property
B. Optimal substructure
C. Backtracking
D. Divide and Conquer without overlapping subproblems
<br> ANS: B
<br> Rationale: The optimal solution for an increasing subsequence is
composed of optimal solutions to its subproblems, demonstrating the
optimal substructure property needed for dynamic programming.
---
Q5. Which algorithm guarantees the shortest path (by number of
edges) in an unweighted graph?
A. Depth-First Search (DFS)
B. Breadth-First Search (BFS)
C. Dijkstra’s Algorithm
D. A Search
<br> ANS: B
<br> Rationale: BFS explores vertices level-by-level, ensuring that the
first time a node is reached, the path taken is the shortest in terms of the
number of edges.
©2025
Algorithms I
Finals Assessment Review
(Questions & Solutions)
2025
©2025
, Q1. In a splay tree , which mechanism ensures that the amortized cost
for operations (search, insertion, deletion) remains O(log n)?
A. Clockwise rotations
B. Randomized rebalancing
C. The splaying operation that moves accessed elements closer to the
root
D. Strict balancing at every insertion
<br> ANS: C
<br> Rationale: Splaying reorganizes the tree on each access so that
recently used nodes are near the root. Although a single operation may
take O(n) time, the amortized cost is O(log n).
---
Q2. Which of the following is a primary advantage of using a B+ tree
over a standard B-tree in database indexing?
A. Data entries are stored in all nodes for faster access.
B. Range queries are optimized because all records reside in the leaf
nodes linked sequentially.
C. It guarantees a perfectly balanced structure with no variations in node
occupancy.
D. It eliminates the need for key comparisons during search operations.
<br> ANS: B
<br> Rationale: B+ trees store all actual data records in the leaf nodes
(which are often linked), thereby enabling efficient sequential access for
range queries.
---
Q3. Which sorting algorithm is non-comparative and can achieve
linear time complexity under appropriate conditions?
©2025
, A. QuickSort
B. MergeSort
C. HeapSort
D. Radix Sort
<br> ANS: D
<br> Rationale: Radix sort leverages the properties of integer
representation by sorting on individual digits. With a fixed digit length (or
under certain assumptions), it can run in linear time.
---
Q4. In the Longest Increasing Subsequence problem solved using
dynamic programming, which property is essential to building the
solution?
A. Greedy-choice property
B. Optimal substructure
C. Backtracking
D. Divide and Conquer without overlapping subproblems
<br> ANS: B
<br> Rationale: The optimal solution for an increasing subsequence is
composed of optimal solutions to its subproblems, demonstrating the
optimal substructure property needed for dynamic programming.
---
Q5. Which algorithm guarantees the shortest path (by number of
edges) in an unweighted graph?
A. Depth-First Search (DFS)
B. Breadth-First Search (BFS)
C. Dijkstra’s Algorithm
D. A Search
<br> ANS: B
<br> Rationale: BFS explores vertices level-by-level, ensuring that the
first time a node is reached, the path taken is the shortest in terms of the
number of edges.
©2025
