Data Structures: Final Exam
The final exam will be held on Tuesday, Dec. 20, 2:003: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
exam booklet.
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
topics discussed
in lecture that you do not have to prepare for the exam; these are listed
below.
The test will cover all the material of the course up through and including
the first lecture on 23 trees (notes on lectures 121).
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
nonhonors section.
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.
 Overriding
 Overloading
 Dynamic dispatching
 Abstract methods
 Interfaces
 Generics
 Wrapper classes for primitive types
 Recursion.
 Lists
 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.
 Trees
 Implementations
 Traversals: Preorder, postorder, inorder, breadthfirst.
 Expression trees
 Binary search trees: Definition, search, add, delete.
 Sets
 Implementations: Arrays, linked lists, bit vectors.
 Operations: Element, add, delete, union, intersect, subset.
 Preorder and postorder expressions.
 Order of magnitude comparison. (Basic concept)
 Worstcase asymptotic analysis. (Basic concept)
 Min heaps
 Sorting algorithms: Selection sort, insertion sort, heapsort,
mergesort, quicksort, bin sort, radix sort, bucket sort.

Graphs:
 Basic definition.
 Implementation: Adjacency list representation and adjacency matrix
representation.
 DAGs: definition, topological sort.
 23 trees: Definition, search, add, delete, enumerate
The following topics were discussed in class but will NOT be on the
final exam.
 Exception handling.
 Redefining the "equals" and "hashcode" methods for hashing complex
object.
 Using hashing for large sets of large objects.
 The lineartime algorithm for constructing a minheap.
 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.
 Btrees
 Algorithms for 23 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.)