Data Structures & Algorithms Flashcards

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

Answer: Dynamic programming

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

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

Answer: n - 1

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

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

Answer: Min-heap (priority queue)

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

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

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

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

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

Answer: It always produces a globally optimal solution for every problem

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

What is the purpose of a sentinel node in a linked list implementation?

Answer: To simplify edge-case handling by providing a dummy head or tail node

A sentinel (dummy) node eliminates special cases for empty lists and boundary conditions, simplifying insert/delete logic.

In the context of algorithm complexity, which relationship correctly orders the following growth rates from slowest to fastest?

Answer: O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

The correct ascending order of growth rates is O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).