// STUHUB · C++ DATA STRUCTURES
C++ Data Structure Drills: Fill in the Blank
Twenty short fill-in-the-blank C++ drills on nodes, head insert/delete, reversal, array stacks, circular queues, BSTs and adjacency lists, with answers and the tempting wrong answer explained.
Introduction
Reading pointer code and writing pointer code are different skills, and only the second one is worth marks. These twenty drills are deliberately tiny: a few lines with one or two holes, an answer, and one line on the wrong answer that looks right. Work down a section with the answers covered, then reveal. If you get a blank wrong, write the whole function out by hand once before moving on — recognising the fix is not the same as being able to produce it.
Every completed drill on this page was compiled with g++ -std=c++17 -Wall and run; where a drill quotes output, that is the real output.
Two struct definitions are used throughout, so you can stop re-reading them:
struct Cell { int value; Cell* next; Cell(int v) : value(v), next(nullptr) {} };
struct TNode { int key; TNode* left; TNode* right; TNode(int k) : key(k), left(nullptr), right(nullptr) {} };The twenty drills are in the exercise list at the foot of the page, grouped in the same order as the sections below. Each section says what its group of drills is about and carries the shared setup that group assumes.
Dynamic allocation and delete
Drills 1–3. Every heap allocation has exactly one matching release, and the form of the release has to match the form of the allocation: new pairs with delete, new[] pairs with delete[]. Mismatching them is undefined behaviour, not merely a leak.
The other habit these three drills build is ordering. When you free a node that is part of a chain, read the next pointer out before the block goes back to the allocator — reading it afterwards usually prints garbage rather than crashing, which is exactly why the bug survives casual testing.
Head insertion and deletion
Drills 4–6. Head insertion is two assignments and the order of the two is the whole exercise: link the new cell forward at the old front first, then move the handle. Do it the other way round and the node points at itself while the rest of the list becomes unreachable.
Pushing 3, then 2, then 1 prints 1 2 3 — head insertion reverses the order you insert in, which is why it is the cheap way to build a list backwards.
In-place reversal
Drills 7–8. Reversal in place is a three-pointer loop — behind, the current node, and a saved ahead — and both drills turn on the same fact: once you have overwritten cur->next, the only way forward is the copy you saved before the overwrite. The function's return value is behind, the last node the loop touched, never the loop variable that has just run off the end.
Stack on a plain array
Drills 9–11. Throughout this section: const int CAP = 8; struct IntStack { int slot[CAP]; int top; }; and top starts at -1.
Push pre-increments and pop post-decrements; the asymmetry is the whole algorithm. The guards are where marks go missing, because top is an index and every bound stated in items has to be converted before it can be compared against it.
Pushing nine values into CAP = 8 prints 111111110: the ninth call is refused rather than overflowing.
Circular queue and the wrap arithmetic
Drills 12–14. Throughout: const int RCAP = 5; struct Ring { string slot[RCAP]; int front; int count; };. This version tracks a live count instead of a rear index, which makes full and empty unambiguous.
Every index that advances in a ring takes % capacity, without exception — that modulus is the thing that turns an array into a ring, and dropping it produces a bug that only appears after the first wrap.
Starting from front = 3 and enqueuing A, B, C really does lay the array out as [C][_][_][A][B] — C has wrapped into slot 0 while the queue is still, logically, A B C.
BST insert and recursive traversal
Drills 15–17. Recursive insert is written against a TNode*& — a reference to the parent's pointer slot — so assigning to the parameter is how the new subtree gets attached, and no return value is needed.
Inserting 40, 25, 60, 25, 70 gives root 40 with children 25 and 60, no left child under 25 — the second 25 matches neither < nor > and is silently dropped. Decide before the exam whether your convention discards duplicates or sends them right, and be consistent.
Adjacency-list construction
Drills 18–20. Two representations appear here: a vector<vector<int>> of out-lists, and an array of buckets built from raw linked nodes. The linked version is head insertion again, so each bucket lists its neighbours in reverse insertion order.
The counting questions are the ones that catch people: in-degree counts arrows arriving, so a directed arc credits its destination, and an undirected edge appears in two lists, so a total over the rows has to be halved.
How to use these
Work one section at a time rather than straight down the page: the value is in noticing which family of mistake is yours. Three patterns cover most of the losses above — saving a pointer before you overwrite it, remembering that an index is one less than a count, and putting % capacity on every index that advances in a ring.
When a blank defeats you, do not just read the answer. Close the page, write the whole function from the signature down, then compile it. Recall under a blank cursor is the thing being tested, and it is a different muscle from recognition.
Exercises with solutions
Work through each question before opening the solution below it.
Exercise 1
Drill 1 — one node on the heap
Cell* p = ______(1)______; // a heap cell holding 42
cout << p->value << "\n";
______(2)______; // hand the memory backSolution
(1) new Cell(42) (2) delete p
Writing Cell p(42); and passing &p compiles and even prints 42, but that cell dies at the end of the enclosing block, so any list still pointing at it holds a dangling pointer.
Exercise 2
Drill 2 — free a whole list
void destroy(Cell* head) {
while (head != nullptr) {
Cell* doomed = head;
head = ______(1)______;
______(2)______;
}
}Solution
(1) doomed->next (2) delete doomed
The tempting order is delete head; head = head->next; — that reads next out of a block you have already released, which is undefined behaviour and often prints garbage rather than crashing, so it survives casual testing.
Exercise 3
Drill 3 — array on the heap
struct Buffer { int* data; int n; };
Buffer makeBuffer(int n) { Buffer b; b.n = n; b.data = ______(1)______; return b; }
void freeBuffer(Buffer& b) { ______(2)______; b.data = nullptr; b.n = 0; }Solution
(1) new int[n]() (2) delete[] b.data
Plain delete b.data is the trap: it releases one int from a block of n, and the mismatch between new[] and delete is undefined behaviour, not merely a leak. The () on new int[n]() zero-initialises; without it the elements hold whatever was in that memory.
Exercise 4
Drill 4 — push at the front
void pushFront(Cell*& head, int v) {
Cell* fresh = new Cell(v);
______(1)______; // new cell points at the old front
______(2)______; // the new cell is now the front
}Solution
(1) fresh->next = head (2) head = fresh
Doing these two in the opposite order sets head = fresh first, after which fresh->next = head makes the node point at itself and every other node in the list is unreachable. Link forward, then move the handle.
Exercise 5
Drill 5 — pop from the front
bool popFront(Cell*& head, int& out) {
if (______(1)______) return false;
Cell* old = head;
out = old->value;
head = ______(2)______;
delete old;
return true;
}Solution
(1) head == nullptr (2) old->next
head = head->next; delete head; is the wrong-but-tempting pair: it deletes the second node and leaks the first. You need the saved old precisely because the handle has already moved on.
Exercise 6
Drill 6 — head insert when a tail pointer exists
void pushFront(Cell*& head, Cell*& tail, int v) {
Cell* fresh = new Cell(v);
fresh->next = head;
head = fresh;
if (______(1)______) tail = fresh;
}Solution
(1) tail == nullptr
Testing head == nullptr here always fails, because head was just assigned two lines above — the test has to look at the pointer you have not touched yet. Miss this and the first insertion into an empty list leaves tail null forever, and the next insertAtTail dereferences it.
Exercise 7
Drill 7 — the three-pointer loop
Cell* reverse(Cell* head) {
Cell* behind = nullptr;
Cell* cur = head;
while (cur != nullptr) {
Cell* ahead = cur->next;
______(1)______; // flip this link
behind = cur;
cur = ______(2)______;
}
return behind;
}Solution
(1) cur->next = behind (2) cur = ahead
Writing cur = cur->next for blank 2 is the natural reflex and it is fatal: line (1) has already overwritten cur->next, so you would walk backwards into the part you just reversed and loop forever. That is exactly what ahead was saved for.
Exercise 8
Drill 8 — reversal without a separate cursor
Cell* reverse(Cell* head) {
Cell* behind = nullptr;
while (head != nullptr) {
Cell* ahead = ______(1)______;
head->next = behind;
behind = head;
head = ahead;
}
return ______(2)______;
}Solution
(1) head->next (2) behind
return head is the classic loss of marks: the loop only ends when head is null, so you would hand back an empty list. The new front is the last node the loop touched, which is sitting in behind.
Exercise 9
Drill 9 — push with an overflow guard
bool push(IntStack& s, int v) {
if (______(1)______) return false; // no room
______(2)______; // move, then write
return true;
}Solution
(1) s.top == CAP - 1 (2) s.slot[++s.top] = v
s.top == CAP is the tempting guard and it is off by one: top is the index of the last item, so on a full stack it is 7, never 8, and the check never fires — you write slot[8] and corrupt whatever sits after the array. Note also that push moves first and writes second; pop is the mirror.
Exercise 10
Drill 10 — pop with an underflow guard
bool pop(IntStack& s, int& out) {
if (______(1)______) return false;
out = ______(2)______;
return true;
}Solution
(1) s.top == -1 (2) s.slot[s.top--]
s.slot[--s.top] is the symmetric-looking wrong answer: it decrements before reading, so it skips the actual top element and returns the one underneath. Push pre-increments, pop post-decrements — the asymmetry is the whole algorithm.
Exercise 11
Drill 11 — peek and size
int peek(const IntStack& s) { return ______(1)______; }
int size(const IntStack& s) { return ______(2)______; }Solution
(1) s.slot[s.top] (2) s.top + 1
Returning s.top from size is tempting because it is the only number in sight, but an index is one less than a count: a stack holding one item has top == 0. Note also that peek never modifies top — if your peek decrements, it is a pop.
Exercise 12
Drill 12 — enqueue
bool enqueue(Ring& r, const string& v) {
if (______(1)______) return false; // full
int rear = ______(2)______; // first free slot
r.slot[rear] = v;
r.count++;
return true;
}Solution
(1) r.count == RCAP (2) (r.front + r.count) % RCAP
Dropping the % RCAP is the whole bug the structure exists to prevent: with front = 3 and two items already queued, front + count is 5, one past the end of a five-slot array. The modulus is what turns the array into a ring.
Exercise 13
Drill 13 — dequeue
bool dequeue(Ring& r, string& out) {
if (r.count == 0) return false;
out = r.slot[r.front];
r.front = ______(1)______;
______(2)______;
return true;
}Solution
(1) (r.front + 1) % RCAP (2) r.count--
Plain r.front + 1 works for the first few dequeues and then walks off the end the moment front reaches the last slot — the failure appears only after the queue has wrapped once, which is why it survives a quick test. Forgetting blank 2 is worse: the queue reports itself permanently full.
Exercise 14
Drill 14 — how many items are in a ring?
Given a buffer where front is the index of the first item and rear is the index one past the last:
int occupancy(int front, int rear, int cap) { return ______(1)______; }Solution
(1) (rear - front + cap) % cap
rear - front is right only while the data has not wrapped; with front = 4, rear = 1, cap = 6 it gives -3 instead of 3. Adding cap before taking the modulus keeps the numerator non-negative, which matters because % in C++ returns a negative result for a negative left operand.
Exercise 15
Drill 15 — recursive insert through a pointer reference
void insert(TNode*& node, int k) {
if (node == nullptr) { ______(1)______; return; }
if (k < node->key) insert(______(2)______, k);
else if (k > node->key) insert(node->right, k);
}Solution
(1) node = new TNode(k) (2) node->left
Writing TNode* fresh = new TNode(k); in blank 1 compiles and leaks: the parameter is a reference to the parent's pointer, and assigning to node is how the new subtree gets attached. A local variable attaches to nothing. Because node is TNode*&, the recursive call passes the child slot itself, so no return value is needed.
Exercise 16
Drill 16 — postorder
void postorder(const TNode* n, vector<int>& out) {
if (n == nullptr) return;
postorder(n->left, out);
______(1)______;
______(2)______;
}Solution
(1) postorder(n->right, out) (2) out.push_back(n->key)
Swap those two lines and you have written inorder, which for a BST prints a sorted sequence and therefore looks convincingly correct. Postorder visits both children before the node, which is why it is the traversal you use to delete a tree.
For the tree built from 40, 25, 60, 10, 30, 70, postorder gives 10 30 25 70 60 40.
Exercise 17
Drill 17 — height in edges
Convention: an empty tree has height -1, a single node has height 0.
int height(const TNode* n) {
if (n == nullptr) return ______(1)______;
return 1 + ______(2)______;
}Solution
(1) -1 (2) max(height(n->left), height(n->right))
Returning 0 for the null case is the tempting answer and it silently switches you to counting nodes on the longest path rather than edges, so every answer comes out one too big. Using + instead of max in blank 2 is the other trap — that counts the whole subtree, not the deepest path.
Exercise 18
Drill 18 — a directed arc, with in-degrees
void addArc(vector<vector<int>>& out, vector<int>& indeg, int from, int to) {
______(1)______; // record the arc
______(2)______; // one more edge arriving at 'to'
}Solution
(1) out[from].push_back(to) (2) indeg[to]++
indeg[from]++ is the easy slip: in-degree counts arrows arriving, so the vertex to credit is the destination. A self-loop addArc(g, d, 3, 3) correctly bumps both the out-list and the in-degree of 3, which is why a self-loop contributes two to the total degree.
Exercise 19
Drill 19 — buckets made of linked nodes
struct Arc { int to; Arc* next; };
void addArc(Arc* buckets[], int from, int to) {
Arc* a = new Arc;
a->to = to;
______(1)______; // splice into the front of the bucket
______(2)______; // the bucket now starts here
}Solution
(1) a->next = buckets[from] (2) buckets[from] = a
Leaving a->next unset is the tempting shortcut when the bucket looks empty — but Arc has no constructor, so a->next holds garbage rather than null, and traversal runs off into nothing. This is head insertion again, so each bucket lists its neighbours in reverse insertion order: adding 0→1 then 0→2 prints 0 -> 2 1.
Exercise 20
Drill 20 — reading the structure back
// undirected graph: every edge stored in both endpoints' lists
int countEdges(const vector<vector<int>>& adj) {
int sum = 0;
for (const auto& row : adj) sum += static_cast<int>(row.size());
return ______(1)______;
}
bool hasArc(const vector<vector<int>>& adj, int u, int v) {
for (int w : adj[u]) if (______(2)______) return true;
return false;
}Solution
(1) sum / 2 (2) w == v
Returning sum counts every undirected edge twice, once from each end — the path 0–1–2–3 has three edges but six list entries. For blank 2, comparing w == u instead of w == v is the transposition to watch for; it silently answers "does u have a self-loop".
Published and updated 2026-08-09 · DUOCODE TECHNOLOGY