Data Structures | C-CAT Cheat Sheets

Question

Time complexity of array access

Answer

O(1) — random access by index

Question

Time complexity of binary search

Answer

O(log n) — requires a sorted array

Question

Which sorting algorithms are stable?

Answer

Bubble, Insertion, Merge, and Counting sort

Question

Quick sort worst-case complexity

Answer

O(n²) — happens when the pivot is always the min or max (e.g. an already-sorted array)

Question

What does an inorder traversal of a BST give you?

Answer

Ascending sorted order

Question

What does the formula n₀ = n₂ + 1 mean?

Answer

In any binary tree: leaf nodes = nodes with 2 children + 1

Question

Which data structure does BFS use?

Answer

A queue (FIFO)

Question

Which data structure does DFS use?

Answer

A stack, or the recursion call stack

Question

Which shortest-path algorithm handles negative edge weights?

Answer

Bellman-Ford — Dijkstra fails with negative weights

Question

Max heap parent rule

Answer

parent ≥ children

Question

Load factor formula in hashing

Answer

α = n / m (number of elements ÷ number of slots)

Question

What causes primary clustering?

Answer

Linear probing in open addressing

Question

What is Floyd's cycle detection technique also called?

Answer

The Tortoise and Hare algorithm (slow & fast pointers)

Question

Space complexity of merge sort

Answer

O(n) — needs a temporary array

Question

Space complexity of heap sort

Answer

O(1) — sorts in-place

Deck Complete!