Data Structures & Algorithms Flashcards

In Big-O notation, what does O(1) indicate about an algorithm?

Answer: Its runtime is constant regardless of input size

O(1) means the algorithm's running time does not grow with the size of the input.

A deque (double-ended queue) supports efficient insertion and deletion at:

Answer: Both the front and the rear

A deque allows O(1) insertions and deletions at both the front and the rear of the structure.

Which graph algorithm is used to detect a cycle in a directed graph?

Answer: Depth-first search with coloring

DFS with three-color marking (white/gray/black) detects back edges that indicate cycles in directed graphs.

What is the minimum number of nodes in a complete binary tree of height h?

Answer: 2^h

A complete binary tree of height h has at least 2^h nodes (all levels full except possibly the last).

Which of the following operations on a balanced BST (e.g., AVL or Red-Black tree) runs in O(log n) time?

Answer: Search, insert, and delete

Balanced BSTs maintain height O(log n), guaranteeing search, insert, and delete operations in O(log n) time.

Topological sorting applies to which type of graph?

Answer: Directed acyclic graphs (DAGs)

Topological sorting produces a linear ordering of vertices in a DAG such that every directed edge goes from earlier to later in the ordering.

What is the time complexity of building a heap from an unsorted array of n elements?

Answer: O(n)

Using the bottom-up heapify approach, a heap can be built from an arbitrary array in O(n) time.