Data Structures Exam Cheat Sheet (C++ Quick Reference)

1. Array — declarations

Asked: pointer-arithmetic output, 2D indexing, array length.

int a[5] = {10, 20, 30, 40, 50};
int* p = a;              // array name decays to &a[0]
int m[2][3] = {{1,2,3},{4,5,6}};
int len = sizeof(a) / sizeof(a[0]);

1. Array — outputs, complexity, and the rule

The rule: *(ptr + n) advances by n * sizeof(element), not n bytes. Row-major address: base + (i * COLS + j) * sizeof(element).

Costliest mistake: sizeof(arr)/sizeof(arr[0]) gives the wrong answer inside a function — the parameter is a pointer, so sizeof returns the pointer size. Only valid where the array is declared.

2. Singly linked list — the node

Asked: insert, delete by value, in-place reverse, count nodes.

struct Node {
    int data;
    Node* next;
    Node(int v) : data(v), next(nullptr) {}
};

2. Singly linked list — insert, delete, reverse

Insert at the front, delete by value, and reverse in place.

void insertFront(Node*& head, int v) {
    Node* n = new Node(v);
    n->next = head;          // link new node first
    head = n;                // then move head
}

bool deleteValue(Node*& head, int v) {
    if (head == nullptr) return false;
    if (head->data == v) {               // deleting the head is a separate case
        Node* t = head; head = head->next; delete t; return true;
    }
    Node* prev = head;
    while (prev->next != nullptr && prev->next->data != v) prev = prev->next;
    if (prev->next == nullptr) return false;
    Node* t = prev->next;
    prev->next = t->next;
    delete t;
    return true;
}

void reverseList(Node*& head) {
    Node* prev = nullptr;
    Node* cur  = head;
    while (cur != nullptr) {
        Node* nxt = cur->next;   // 1. save
        cur->next = prev;        // 2. flip
        prev = cur;              // 3. advance prev
        cur  = nxt;              // 4. advance cur
    }
    head = prev;                 // do not forget this line
}

2. Singly linked list — output and cost table

Real output from the compiled demo:

built:    5 -> 10 -> 20 -> 30
del 20:   5 -> 10 -> 30
reversed: 30 -> 10 -> 5
count = 3

The rule: in reversal, save next before overwriting cur->next. Order is save → flip → advance → advance.

Costliest mistake: forgetting head = prev; at the end of reverse — the list is correctly reversed in memory but head still points at what is now the tail, so printing shows one node.

3. Stack — array implementation

LIFO. Array version, top starts at -1.

Precedence (highest first): ^ → * / → + -. ( has lowest precedence once on the stack.

const int MAX = 100;
class ArrayStack {
    int arr[MAX];
    int top;
public:
    ArrayStack() : top(-1) {}
    bool isEmpty() const { return top == -1; }
    bool isFull()  const { return top == MAX - 1; }
    void push(int v) { if (isFull()) return; arr[++top] = v; }   // pre-increment
    int  pop()       { if (isEmpty()) return -1; return arr[top--]; } // post-decrement
    int  peek() const{ return isEmpty() ? -1 : arr[top]; }
    int  size() const{ return top + 1; }
};

3. Stack — postfix evaluation

Postfix evaluation:

int evaluatePostfix(const string& exp) {
    stack<int> s;
    for (char c : exp) {
        if (isdigit(c)) {
            s.push(c - '0');
        } else {
            int op2 = s.top(); s.pop();   // RIGHT operand pops first
            int op1 = s.top(); s.pop();   // LEFT operand pops second
            switch (c) {
                case '+': s.push(op1 + op2); break;
                case '-': s.push(op1 - op2); break;
                case '*': s.push(op1 * op2); break;
                case '/': s.push(op1 / op2); break;
            }
        }
    }
    return s.top();
}

3. Stack — the operand-order trap

Compiled output: evaluatePostfix("62/3-42*+") prints 8 (6/2 = 3, 3−3 = 0, 4×2 = 8, 0+8 = 8).

Costliest mistake: popping the operands in the wrong order. The first value popped is the right operand. Gets - and / wrong every time and + and * right, so it hides until it costs marks.

4a. Queue — linked-list queue

FIFO. Insert at rear, remove from front.

struct QNode { int data; QNode* next; QNode(int v) : data(v), next(nullptr) {} };

class LinkedQueue {
    QNode* qFront; QNode* qRear; int count;
public:
    LinkedQueue() : qFront(nullptr), qRear(nullptr), count(0) {}
    bool isEmpty() const { return qFront == nullptr; }
    void enqueue(int v) {
        QNode* n = new QNode(v);
        if (qRear == nullptr) { qFront = qRear = n; }   // first node: both pointers
        else { qRear->next = n; qRear = n; }
        count++;
    }
    bool dequeue(int& out) {
        if (qFront == nullptr) return false;
        QNode* t = qFront;
        out = t->data;
        qFront = qFront->next;
        if (qFront == nullptr) qRear = nullptr;         // <-- the line people drop
        delete t;
        count--;
        return true;
    }
};

4a. Queue — the dangling rear pointer

Costliest mistake: not resetting qRear = nullptr when the last element leaves. The queue reports empty, but qRear dangles at freed memory and the next enqueue writes through it.

4b. Queue — circular queue

The array version, with every index advance taken modulo capacity.

class CircularQueue {
    int* arr; int capacity, front, rear;
public:
    CircularQueue(int cap) : capacity(cap), front(0), rear(0) { arr = new int[cap]; }
    ~CircularQueue() { delete[] arr; }
    bool isEmpty() const { return front == rear; }
    bool isFull()  const { return (rear + 1) % capacity == front; }
    int  size()    const { return (rear - front + capacity) % capacity; }
    bool enqueue(int v) {
        if (isFull()) return false;
        arr[rear] = v;
        rear = (rear + 1) % capacity;
        return true;
    }
    bool dequeue(int& out) {
        if (isEmpty()) return false;
        out = arr[front];
        front = (front + 1) % capacity;
        return true;
    }
};

4b. Queue — the four formulas and a real trace

The formulas — memorise these four:

Real trace, capacity = 5:

start             front=0 rear=0 size=0 empty=Y full=N
enq 10,20,30,40   front=0 rear=4 size=4 empty=N full=Y
enqueue(50) accepted? no
deq twice         front=2 rear=4 size=2 empty=N full=N
enq 50,60         front=2 rear=1 size=4 empty=N full=Y

Note rear wrapped from 4 to 1 — that is the whole point.

Why circular at all (the essay answer): a simple linear array queue suffers false overflow. After dequeues, front moves forward and leaves free slots at the start, but once rear reaches MAX - 1 the queue refuses new elements even though the array is mostly empty. Fixing it by shifting everything down is O(n) per dequeue. A circular queue wraps the indices with % capacity and reuses those slots in O(1).

Costliest mistake: if you do not sacrifice a slot and do not keep a counter, front == rear means both "empty" and "full" and the two states are indistinguishable.

5. Tree / BST — terminology

Get these exact.

Depth counts downward from the root, height counts upward from the leaves. They are equal only at the root.

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : data(v), left(nullptr), right(nullptr) {}
};

5. Tree / BST — operations

Insert, search, height, leaf count, the three depth-first traversals, and level order.

TreeNode* insertBST(TreeNode* root, int v) {
    if (root == nullptr) return new TreeNode(v);       // base case creates the node
    if (v < root->data) root->left  = insertBST(root->left, v);
    else                root->right = insertBST(root->right, v);
    return root;                                       // re-attach on the way back up
}

bool searchBST(TreeNode* root, int target) {
    if (root == nullptr) return false;
    if (root->data == target) return true;
    if (target < root->data) return searchBST(root->left, target);
    return searchBST(root->right, target);
}

int height(TreeNode* r) {                    // edge convention
    if (r == nullptr) return -1;
    return 1 + max(height(r->left), height(r->right));
}

int countLeaves(TreeNode* r) {
    if (r == nullptr) return 0;
    if (r->left == nullptr && r->right == nullptr) return 1;
    return countLeaves(r->left) + countLeaves(r->right);
}

void inorder(TreeNode* r)  { if (!r) return; inorder(r->left);  cout << r->data << " "; inorder(r->right); }
void preorder(TreeNode* r) { if (!r) return; cout << r->data << " "; preorder(r->left); preorder(r->right); }
void postorder(TreeNode* r){ if (!r) return; postorder(r->left); postorder(r->right); cout << r->data << " "; }

void levelOrder(TreeNode* root) {            // uses a QUEUE, not recursion
    if (!root) return;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front(); q.pop();
        cout << cur->data << " ";
        if (cur->left)  q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

5. Tree / BST — insert rule, real output, complexity

BST insert rule: value < node->data → go left, otherwise go right. New nodes always become leaves; nothing already in the tree moves.

Inserting 50, 30, 70, 20, 40, 60, 80, 35 gives this real output:

inorder:    20 30 35 40 50 60 70 80
preorder:   50 30 20 40 35 70 60 80
postorder:  20 35 40 30 60 80 70 50
levelorder: 50 30 70 20 40 60 80 35
height(edges)=3  leaves=4  search(40)=found  search(45)=not found

The check that catches errors: in-order on a BST must come out in ascending order. If it does not, your tree is wrong — redo it before answering anything else.

Costliest mistake: mixing up height and depth, and off-by-one from the two conventions. Say which one you are using ("height in edges, empty tree = −1") and stay consistent across the whole answer.

6. Graph — representation

// adjacency list — preferred for sparse graphs
vector<vector<int>> adj(V);
void addEdgeUndirected(vector<vector<int>>& adj, int u, int w) {
    adj[u].push_back(w);
    adj[w].push_back(u);        // BOTH directions
}
void addArcDirected(vector<vector<int>>& adj, int u, int w) {
    adj[u].push_back(w);        // one direction only
}

6. Graph — degree

For the directed graph A→B, A→C, C→B, B→D, C→D, C→E, D→E (7 arcs):

Use Σin = Σout = E as your instant self-check.

6. Graph — breadth-first traversal

Breadth-first traversal is driven by a queue.

vector<bool> visited(V, false);
queue<int> q;
visited[start] = true;      // mark WHEN ENQUEUEING
q.push(start);
while (!q.empty()) {
    int u = q.front(); q.pop();
    cout << u << " ";
    for (int w : adj[u]) {
        if (!visited[w]) { visited[w] = true; q.push(w); }
    }
}

6. Graph — the BFT marking trap

Costliest mistake: marking a vertex visited when you dequeue it instead of when you enqueue it. A vertex with two unvisited-at-the-time neighbours then gets pushed twice and appears twice in the output.

DFS is the same code with a stack instead of a queue (or recursion).

6. Graph — Dijkstra

Relaxation step — the one line the whole question turns on:

if dist[u] + weight(u, v) < dist[v] then dist[v] = dist[u] + weight(u, v) and parent[v] = u

Loop: pick the unsettled vertex with the smallest dist, mark it settled (its distance is now final), relax all its outgoing edges, repeat.

vector<int> dist(V, INT_MAX), parent(V, -1);
vector<bool> done(V, false);
dist[src] = 0;
for (int it = 0; it < V; it++) {
    int u = -1;
    for (int i = 0; i < V; i++)
        if (!done[i] && dist[i] != INT_MAX && (u == -1 || dist[i] < dist[u])) u = i;
    if (u == -1) break;
    done[u] = true;
    for (auto& e : adj[u]) {                 // e = {neighbour, weight}
        int v = e.first, w = e.second;
        if (!done[v] && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; parent[v] = u; }
    }
}

6. Graph — Dijkstra complexity and limits

Costliest mistake: using Dijkstra on a graph with a negative edge weight. Once a vertex is settled its distance is never revisited, so a negative edge can produce a wrong answer. Say "Bellman-Ford" if negative weights appear.

6. Graph — Kruskal (MST)

1. Sort all edges by weight, ascending.
2. Take the next cheapest edge; keep it only if it joins two different components (no cycle).
3. Stop at V − 1 edges.

Cycle detection with union-find. Contrast: Prim's grows one tree from a start vertex (vertex-based); Kruskal's picks globally cheapest edges (edge-based). Both give the same total weight.

7. Sorting

Bubble, selection and insertion, written the way they are marked.

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); swapped = true; }
        if (!swapped) break;                 // makes best case O(n)
    }
}

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) if (a[j] < a[minIdx]) minIdx = j;
        if (minIdx != i) swap(a[i], a[minIdx]);
    }
}

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}

7. Sorting — comparison table and a real trace

Real bubble-sort passes on 5 1 4 2 8:

pass 1: 1 4 2 5 8
pass 2: 1 2 4 5 8
pass 3: 1 2 4 5 8      (no swap -> stop early)

Costliest mistake: the inner bound. It is j < n - 1 - i, not j < n - 1. Without - i you re-compare the already-sorted tail; with j <= n - 1 you read a[n] off the end.

8. Searching

Binary search, in the form that survives marking.

int binarySearch(const int a[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {                       // <=, not <
        int mid = low + (high - low) / 2;       // overflow-safe form
        if (a[mid] == target) return mid;
        else if (a[mid] < target) low  = mid + 1;
        else                      high = mid - 1;
    }
    return -1;
}

8. Searching — comparison and the loop-bound trap

On 2 5 8 12 16 23 38 56 72 91 the compiled program prints: index of 23 = 5, index of 24 = -1, linear index of 56 = 7.

Costliest mistake: while (low < high) or low = mid / high = mid. The first misses the last candidate; the second loops forever when low and high are adjacent.

Worked trace A — infix to postfix: P - Q / (R + S) * T

Rules: operand → output. ( → push. ) → pop to output until (, discard (. Operator → while the stack top is an operator of higher or equal precedence, pop it to output; then push. End → pop everything.

Answer: PQRS+/T*- (verified by the compiled program).

Two traps: ( is never sent to the output, and equal precedence pops (left-associative), which is what makes / come out before *.

Worked trace B — BFT queue state, start = 0

Undirected graph: 0–1, 0–2, 1–3, 1–4, 2–4, 3–5, 4–5.

Visit order: 0 1 2 3 4 5. Step 3 is the mark: 2's neighbour 4 was already marked at step 2, so it is not enqueued again.

Worked trace C — Dijkstra table, source A

Directed, weighted: A→B 4, A→C 2, C→B 1, B→D 5, C→D 7, C→E 10, D→E 3.

Shortest path A→E = A→C→B→D→E, cost 11 (2+1+5+3). All values are real program output.

The teaching point is row 2: the direct arc A→B cost 4, but going through C cost 3. Always pick the smallest unsettled distance next, and always re-check whether a shorter route just appeared.

If you only have twenty minutes

1. Circular queue tests. Empty front == rear; full (rear + 1) % capacity == front; advance with % capacity; capacity − 1 usable.
2. Postfix operand order. First pop = right operand. Second pop = left.
3. Height vs depth. Depth counts down from the root (root = 0); height counts up from the leaves (leaf = 0, empty = −1).
4. BST insert rule. < goes left, otherwise right; new nodes are always leaves; in-order must come out ascending.
5. Mark visited on enqueue in BFT, never on dequeue.
6. Dijkstra relaxation. if (dist[u] + w < dist[v]) dist[v] = dist[u] + w; and settle the smallest unsettled vertex each round.
7. Reset rear = nullptr when a linked queue empties.
8. head = prev; at the end of an in-place list reverse.
9. Degree checks. Undirected Σdeg = 2E; directed Σin = Σout = E.
10. Complexities worth memorising cold. Array access O(1); list search O(n); stack/queue ops O(1); balanced BST O(log n) but degenerate O(n); binary search O(log n) and it needs a sorted array; bubble/selection/insertion O(n²), merge O(n log n).
11. Precedence. ^ > * / > + -; ( is never output; equal precedence pops.
12. Write the struct first. In a code question the node declaration and the null checks are marks on their own — put them down even if the algorithm body stalls.

Good luck. Sleep beats one more re-read.

Which C++ standard does this page assume?

Standard C++17. C++ began as C with Classes in 1979 and first shipped commercially in 1985; what a compiler flag actually selects today is one of the ISO revisions below, and the committee has published a new one every 3 years since 2011. Build these listings with -std=c++17 and they compile as written.

Common questions

Where can I check this against the language itself?

Nothing on this page outranks the standard or the library reference. When this page and one of these disagree, they are right and we want to know.

• cppreference — the C++ standard library referenceThe fastest correct answer for what a container or algorithm actually guarantees.
• isocpp.org — the Standard C++ FoundationThe FAQ and the core guidelines, written by the people who define the language.
• ISO/IEC JTC1/SC22/WG21 — the C++ standards committeeWorking drafts of the standard itself, free to read, when the wording is the question.
• GCC online documentationWhat -Wall, -Wextra and the sanitizers used on these listings actually check.
• Microsoft Learn — C++ language documentationThe MSVC view, for readers whose lab machines build with Visual Studio.

Related pages