Data Structures and Algorithms Flashcards

What is the space complexity of merge sort?

Answer: O(n)

Merge sort requires O(n) auxiliary space to hold the temporary arrays during the merge step.

Which tree property guarantees O(log n) height for balanced binary search trees?

Answer: The height difference between left and right subtrees is at most 1

AVL trees enforce that the height difference (balance factor) between subtrees is at most 1, keeping height at O(log n).

What does amortized O(1) mean for dynamic array append operations?

Answer: Append is O(1) on average over many operations despite occasional O(n) resizing

Although resizing costs O(n), it happens infrequently enough that the average cost per append is O(1) amortized.

In graph theory, what is a topological sort used for?

Answer: Ordering nodes in a directed acyclic graph so all edges point forward

Topological sort linearly orders DAG vertices such that for every directed edge u→v, u appears before v.

What is the primary advantage of a trie (prefix tree) over a hash table for string lookups?

Answer: Tries support prefix searches and ordered iteration efficiently

Tries allow efficient prefix queries and alphabetical iteration, which hash tables cannot natively support.

Which algorithm is used to find a minimum spanning tree in a weighted undirected graph?

Answer: Prim's algorithm

Prim's algorithm (and Kruskal's) finds a minimum spanning tree by greedily selecting the lowest-weight edges.

What distinguishes a circular queue from a regular queue?

Answer: The rear of a circular queue wraps around to connect to the front, reusing space

A circular queue wraps its rear pointer to the front when it reaches the end of the array, efficiently reusing freed slots.