What You Actually Need to Know for the Exam
The midterm usually covers trees, hash tables, graphs, and big-O analysis. That's about it. Your professor will pick three or four topics and make you draw them, trace through algorithms by hand, and occasionally ask you to code something on a whiteboard. The problems aren't hard if you've actually done the work during the semester. They're brutal if you've never written a tree traversal from scratch or counted comparisons for merge sort on paper. I spent way too long studying the wrong things when I took mine. I was memorizing definitions like AVL rotation cases without understanding why they mattered. That approach doesn't help when the question asks you to balance a specific sequence of insertions and show every intermediate tree.
Data Structures Midterm Exam
Here's how I'd approach it now. Focus on tracing first. Can you take an array and build a binary search tree by inserting elements one by one? Can you show the tree after each insertion, mark which nodes are left children and which are right, and label the height? If not, practice that until your hand moves without thinking. Professors love that question. Hash table collisions come up constantly. Know linear probing, chained hashing, and double hashing cold. Know how to compute load factor and when rehashing triggers. The tricky part most people miss is that collision resolution strategy changes the average case time complexity in practice even though the worst case stays O(n) for everything. With linear probing, you get clustering that degrades performance well before the table hits 70% full. Double hashing pushes that threshold much higher, closer to 90%, but it costs more per probe. There's no free lunch. I once had a question on a practice exam that asked about open addressing with a table size that wasn't prime. The textbook examples always used primes. When the table size and the key share a common factor, some slots become unreachable and you probe infinitely. The workaround is simple: always verify the hash table size is prime and that the secondary hash function produces values coprime to the table size. I lost points on this exact scenario because I never considered non-prime sizes. I went back and added a checklist item for my own reference sheets after that.
Graph Traversals and Shortest Path
BFS and DFS. Everyone knows them. The exam won't ask you to define them. It will give you a graph with weighted edges and ask you to trace BFS level by level, showing the queue state after each operation. Or it will ask for DFS and require you to show the recursion stack. Don't skip the mechanics. Writing "BFS visits nodes in order" is worth two points. Showing the queue as [A, C, D] then [C, D, B] with timestamps is worth six. Dijkstra's algorithm is fair game. Know how to maintain the distance table, the priority queue, and the set of visited nodes. The common pitfall is forgetting that Dijkstra doesn't work with negative edge weights. If your professor includes a graph with negative weights and expects Dijkstra, the answer is that Dijkstra gives incorrect results and you should use Bellman-Ford instead. Pointing that out explicitly often earns partial credit even if you don't complete the full algorithm. A counter-intuitive thing about Dijkstra: using a Fibonacci heap gives you O(E + V log V) theoretical complexity, but in practice a binary heap is almost always faster because the constant factors in a Fibonacci heap are so large. For an exam, binary heap is sufficient. For a real implementation, benchmark it. I learned this the hard way when I tried to optimize a shortest-path project in undergrad and it actually ran slower than the naive binary heap version.
Get the Full Details
Big-O and Recurrence Relations
You will get at least one recurrence relation to solve. Master the Master Theorem. Know the three cases. But also know when the Master Theorem doesn't apply, like when f(n) isn't polynomially larger or smaller than n^log_b(a). That's where the substitution method or recursion tree method comes in. I used to skip those and just guess, which worked sometimes and bombed me completely on a single problem that required the substitution proof. Amortized analysis also shows up. The classic example is dynamic arrays. The analysis is straightforward once you see it: charge each insertion 3 units, use 1 for the insert, 1 to save for a future copy, and 1 more to pay for moving the element when the resize happens. The math works out to O(1) amortized per operation even though individual resizes are O(n). If you can explain that clearly, you'll separate yourself from most of the class.
What to Review Before You Walk In
Make sure you can do these without looking anything up: - Insert and delete in a binary search tree, including the case where the node has two children and you need to find the inorder successor - Rotate a BST: left rotation, right rotation, and the combination for double rotations in AVL trees
- Build a min-heap from an array using the bottom-up heapify method - Run union-find with path compression and union by rank, and explain why the complexity is nearly constant - Convert an infix expression to postfix and evaluate it using a stack
Priority queues based on heaps come up in every exam I've seen. Know how to implement insert, extract-min, and decrease-key. The decrease-key operation is where most implementations diverge between binary heap, binomial heap, and Fibonacci heap. For the midterm, binary heap is fine. Just know that decrease-key is O(log n) in a binary heap but O(1) amortized in a Fibonacci heap, which is why Fibonacci heaps win for Dijkstra in theory. One last thing nobody warns you about: draw everything. The exam is usually paper-based. Draw the tree. Draw the hash table array. Draw the graph with edge weights. Write out the priority queue state after each step. Half the points are lost to sloppy notation, not wrong logic. I've seen students who knew the answer but drew the right child on the left side of the tree and lost 40% of the points for that section alone. If your professor has posted past exams, do them under timed conditions. Three hours goes fast when you're writing out full traversals by hand. I usually aim for about eight minutes per major problem. If you're spending twenty minutes on a single tree rotation question, you're overcomplicating it or you haven't practiced enough.
