Data Structures Final Exam Study Guide – 2025

1. Runtime Complexity & Big-O

Subtopics

  • Reading loop structures and counting “how many times does this run?”
  • Nested loops vs independent loops
  • Data-dependent loops with different parameters (e.g. N vs M)
  • Logarithmic loops (i *= 2 or dividing ranges)
  • Polynomial growth: O(N),O(N^2),O(N^3)
  • Mixed complexities: O(N+M), O(Nlog⁡N)

Sample practice question

For each function, give the Big-O runtime (in terms of N and/or M) and a short justification.

// (a)
int countPos(const vector<int>& v) {
    int c = 0;
    for (int i = 0; i < (int)v.size(); i++) {
        if (v[i] > 0) c++;
    }
    for (int k = 0; k < 100; k++) {
        // constant-time logging
    }
    return c;
}

// (b)
bool shareAny(const vector<int>& a, const vector<int>& b) {
    for (int i = 0; i < (int)a.size(); i++) {
        for (int j = 0; j < (int)b.size(); j++) {
            if (a[i] == b[j]) return true;
        }
    }
    return false;
}

// (c)
void weird(int n) {
    for (int i = 1; i < n; i *= 2) {
        for (int j = 0; j < n * n; j++) {
            // O(1) work
        }
    }
}
  • Identify the complexity of (a), (b), (c) and explain which loop(s) dominate.

2. Classes, Overloading, Inheritance, Polymorphism, Deep Copy

Subtopics

  • Overloaded constructors and member functions (same name, different parameters)
  • Virtual functions and overriding in subclasses
  • Calling base-class constructors from derived-class constructors
  • virtual destructors for polymorphic use
  • Classes with dynamically allocated members:
    • copy constructor
    • destructor
    • (optionally) assignment operator
  • Shallow vs deep copy and why shallow can break

Sample practice question

You are designing a simple shape hierarchy:

class Shape {
public:
    virtual double area() const = 0;
    virtual ~Shape() {}
};

class Rectangle : public Shape {
public:
    Rectangle(double w, double h) : width(w), height(h) {}
    double area() const override { return width * height; }
private:
    double width, height;
};
  1. Add a subclass Square that:
    • Inherits publicly from Rectangle.
    • Has a constructor Square(double side) that calls the Rectangle constructor with (side, side).
  2. Add to Rectangle an overloaded method:double area(double scale) const; that returns the area of a rectangle whose width and height are both multiplied by scale.
  3. Explain what will be printed by:Shape* p = new Square(3.0); cout << p->area() << endl; delete p; and why the virtual keyword matters here.

3. Dynamic Memory & Pointer Errors

Subtopics

  • new / delete vs new[] / delete[]
  • Memory leaks (never freed)
  • Dangling pointers (use-after-free, returning pointer to local)
  • Out-of-bounds array access on the heap
  • Object lifetime and ownership responsibilities

Sample practice question

For each snippet, describe:

  • Whether there is a memory bug.
  • What kind (leak, dangling, bounds error, etc.).
  • Why it’s dangerous.
// (a)
int* makeOne() {
    int* p = new int(7);
    return p;
}
void foo() {
    int* q = makeOne();
    cout << *q << endl;
    // no delete
}

// (b)
void g() {
    int* arr = new int[3];
    arr[0] = 1;
    arr[1] = 2;
    arr[2] = 3;
    delete[] arr;
    cout << arr[1] << endl;  // use after delete
}

// (c)
void h() {
    int* data = new int[2];
    for (int i = 0; i <= 2; i++) { // note <=
        data[i] = i * 10;
    }
    delete[] data;
}

4. Linked Lists

Subtopics

  • Basic singly-linked list node and traversal
  • Manipulating pointers instead of indices
  • Handling head == nullptr and single-node lists
  • Modifying lists “in place” without allocating new nodes
  • Reusing nodes when rearranging a list

Sample practice questions

(a) Remove adjacent duplicates from an unsorted list

You are given a singly linked list of integers that is not sorted, but you only need to remove adjacent duplicates:

Example:
Input: 3 → 3 → 5 → 5 → 5 → 2 → 2 → 7
Output: 3 → 5 → 2 → 7

Write:

Node* removeAdjacentDuplicates(Node* head);

that merges any run of equal consecutive values into a single node but does not reorder the list.

(b) Insert “double” nodes

Given a list like 4 → 1 → 6, transform it into
4 → 8 → 1 → 2 → 6 → 12
by inserting after each node a new node whose value is double the original node’s value.

Write:

void insertDoubles(Node* head);

which modifies the list in place by allocating the new “double” nodes.

5. Stacks & Postfix (RPN) Evaluation

Subtopics

  • Stack behavior: LIFO
  • Pushing operands and using pops for operators
  • Proper order: pop right operand second (careful with subtraction/division)
  • Handling multi-digit numbers and whitespace-separated tokens

Sample practice question

Implement a postfix evaluator that supports multi-digit integers and the operators +, -, *, /.

int evalPostfix(const string& expr);

Example expressions:

  • "10 5 -" → 5
  • "2 3 4 * + 6 /" → (3*4) = 12; 2+12 = 14; 14/6 = 2 (integer division)

Outline:

  • Use a stack<int>.
  • Use istringstream to read tokens.
  • Describe what happens on each token for "5 9 8 + 4 6 * * 7 + *".

6. Queues & Simple Simulations

Subtopics

  • Queue behavior: FIFO
  • Representing waiting lines with queue<>
  • Modeling discrete time and events (arrivals, service start, service finish)
  • Keeping track of server busy/idle and when it will be free
  • Stop condition (no more arrivals, queue empty, server idle)

Sample practice question

You are simulating a car wash with one machine:

  • Car i arrives at time arrival[i].
  • Washing car i takes duration[i] minutes.
  • If the washer is free when a car arrives, start washing immediately.
  • Otherwise, the car waits in a queue.

Implement:

int carWashFinishTime(const vector<int>& arrival,
                      const vector<int>& duration);

that returns the time when the last car finishes.
Describe how you use a queue<int> of indices and a currentTime or freeAt variable.

7. Hash Tables: Chaining & Linear Probing

Subtopics

  • Hash function basics: index = key % tableSize
  • Chaining with vector<list<int>>:
    • Insertion: compute bucket index, push value there
    • Reasoning about distribution
  • Linear probing with vector<int> and a special empty marker (like -1)
    • Searching forward and wrapping around
    • Stopping at first empty slot
  • Manually tracing insert sequences

Sample practice questions

(a) Chaining

Implement:

class ChainHash {
    vector<list<int>> table;
public:
    ChainHash(int n) : table(n) {}
    void insert(int x) {
        int h = x % table.size();
        // append x to table[h]
    }
};

If the table has size 4 and you insert in order: 10, 6, 7, 14, 3,
what values end up in each bucket (in insertion order)?

(b) Linear probing

A linear probing table of size 6 uses -1 for empty slots. The hash is h(x) = x % 6.
Start from all -1 and insert 8, 14, 20, 5 in that order. Show the final table contents and explain each probing step.

8. Trees: BSTs, Height, and Basic B-Tree Ideas

Subtopics

  • BST property and its impact on search path
  • Recursive BST search and complexity
  • Inorder traversal → sorted output
  • Height of a binary tree (0 for empty, 1 for leaf, etc.)
  • How height affects search complexity (balanced vs skewed)
  • B-tree intuition: nodes can hold multiple keys; splits keep tree shallow

Sample practice questions

(a) BST insertion and inorder

Insert 25, 15, 35, 10, 20, 30, 40 into an initially empty BST (no balancing).

  1. Draw the resulting tree structure.
  2. Write the inorder traversal sequence.

(b) Recursive height

Write:

int treeHeight(Node* root);

that returns 0 for nullptr, 1 for a single node, and e.g. 3 for a root with a chain of length 3.
Explain informally why this algorithm visits every node at most once.

(c) B-tree sketch (conceptual, not full implementation)

Consider a B-tree of minimum degree t = 2 (max 3 keys per node). Starting from empty, keys 5, 15, 25, 35, 45 are inserted.
Sketch one possible final arrangement of keys in the root and its children after splits (you don’t need to show exact pointer structure—just which keys end up together in which nodes).

9. Greedy Algorithms & Activity Scheduling

Subtopics

  • Definition of a greedy algorithm
  • “Locally optimal” vs “globally optimal” solutions
  • Activity (interval) selection: picking maximum number of non-overlapping intervals
  • Correct greedy rule: earliest finishing time
  • Examples of bad greedy rules (earliest start, longest duration) and why they can fail
  • Sorting intervals and scanning to select compatible ones

Sample practice questions

(a) Conceptual

In 3–4 sentences:

  • Define a greedy algorithm.
  • Explain what we mean by a “local choice”.
  • Describe how the earliest-finish-time rule works for scheduling talks in a single conference room.

(b) Activity selection example (different from test)

You have one room and these candidate talks (start, finish):

  • P: (1, 3)
  • Q: (2, 6)
  • R: (4, 7)
  • S: (6, 8)
  • T: (5, 9)
  • U: (8, 10)

Use the earliest finish time greedy algorithm to choose a maximum set of non-overlapping talks.

  • First sort by finish time.
  • Then simulate the greedy selection and list the talks you choose in order.

(c) Greedy vs bad rule

Consider the same set of talks, but now use this rule:
“Always pick the talk with the shortest duration that is compatible with the ones already scheduled.”
Show one possible sequence of talks chosen by this rule and argue (in words) why this set might not be optimal.

Scroll to Top