CPA Data Structures & Algorithms 5

Question 1

Which algorithm paradigm solves a problem by breaking it into overlapping subproblems and storing their results to avoid recomputation?

Accepted Answer

Dynamic programming

Answer

Dynamic programming uses memoization or tabulation to store subproblem results, eliminating redundant computations.

Question 2

In a circular queue implemented with an array of size n, the maximum number of elements that can be stored is:

Accepted Answer

n - 1

Answer

One slot is typically kept empty to distinguish between a full and empty queue, limiting capacity to n-1 elements.

Question 3

Which data structure underpins Dijkstra's shortest-path algorithm to efficiently extract the minimum-distance vertex?

Accepted Answer

Min-heap (priority queue)

Answer

Dijkstra's algorithm uses a min-heap priority queue to always process the unvisited vertex with the smallest known distance next.

Question 4

What distinguishes an AVL tree from a standard binary search tree?

Accepted Answer

It maintains a height balance factor of at most 1 for every node

Answer

An AVL tree self-balances by ensuring the height difference between left and right subtrees of any node is at most 1.

Question 5

Which of the following is NOT a characteristic of a greedy algorithm?

Accepted Answer

It always produces a globally optimal solution for every problem

Answer

Greedy algorithms do not guarantee global optimality for all problems; they only work when the greedy-choice property holds.

(CPA) Certified Associate Programmer Practice Test