Data Structures: Final Exam
The final exam will be held on Tuesday, Dec. 20, 2:00-3:50 in WWH 102.
The exam is closed book and closed notes. Please bring nothing to the exam room
except pen or pencil. Answers do not have to be in order in your
The exam will be cumulative; that it covers both material from before the
midterm and from after the midterm, though it will focus more on material
from after the midterms.
The class will cover only material discussed in lecture. There are a few
in lecture that you do not have to prepare for the exam; these are listed
The test will cover all the material of the course up through and including
the first lecture on 2-3 trees (notes on lectures 1-21).
I will only ask about
material that I have covered
in class. I will not ask about anything that is in the textbook
that I did not cover in class.
The students in the honors section take the same exam as those in the
In problems that ask you to write Java code, I will not deduct points for
trivial syntactic errors.
I will not ask about the Java library classes.
I will not ask about access control and visibility (public, private, and
protected). You are, of course, expected to know the basic features of
Java statements and methods.
Specifically, the topics on the test include:
- Object oriented features of Java:
- Classes and subclasses.
- Objects and references.
- Dynamic dispatching
- Abstract methods
- Wrapper classes for primitive types
- Array implementation of lists
- Singly linked lists
- Doubly linked lists
- Ordered lists
- Binary search in ordered arrays.
- Distinction between constant time and linear time operations.
- Hash tables.
- Traversals: Preorder, postorder, inorder, breadth-first.
- Expression trees
- Binary search trees: Definition, search, add, delete.
- Implementations: Arrays, linked lists, bit vectors.
- Operations: Element, add, delete, union, intersect, subset.
- Preorder and postorder expressions.
- Order of magnitude comparison. (Basic concept)
- Worst-case asymptotic analysis. (Basic concept)
- Min heaps
- Sorting algorithms: Selection sort, insertion sort, heapsort,
mergesort, quicksort, bin sort, radix sort, bucket sort.
- Basic definition.
- Implementation: Adjacency list representation and adjacency matrix
- DAGs: definition, topological sort.
- 2-3 trees: Definition, search, add, delete, enumerate
The following topics were discussed in class but will NOT be on the
- Exception handling.
- Redefining the "equals" and "hashcode" methods for hashing complex
- Using hashing for large sets of large objects.
- The linear-time algorithm for constructing a min-heap.
- The iterative "sloshing" version of mergesort. In any question about
mergesort, you may use the conceptually simpler recursive version.
- Lower bounds for sorting.
- Combinatorial formulas (number of permutations, number of combinations).
- Abstract mathematical questions about order of magnitude.
- Algorithms for 2-3 trees other than those listed above.
- Any new material presented after lecture 21.
- Terminology for different categories of algorithms: "Divide and conquer"
and so on.
If the exam includes any questions that involves knowing a large power of
2 or a logarithm, I will provide the number. You need not memorize the
large powers of 2 or logarithms to pass the exam (though of course you should,
on general principles.)