Final Review

Tom Kelliher, CS23

May 13, 1996

• The final is cumulative.
• This review only covers what we've done since the second midterm.
• The final is Thursday, May 16 at 11:30am in 150 Hoyt.

1. Trees, binary and otherwise.
   • Why not just use a list?
   • Nomenclature: vertex, edge, search tree, leaf, etc.
   • Traversals: preorder, inorder, postorder, postmodern.
   • Under what conditions can an array-based implementation be used?
   • Search tree operations: retrieve, insert, delete. Do insert/delete keep the tree balanced?
   • How are n-ary trees represented?
2. Advanced class features, again.
   • Virtual functions.
   • Polymorphism.
   • Late- early-binding.
   • Pure virtual functions, abstract base classes.
   • Static class members.
   • Friends.
3. Hash tables.
   • Hash functions: purpose, properties of good ones, collision resolution (linear, quadratic, double hashing).
   • Clustering.
   • Three entry states in a closed hash table.
   • Separate chaining.
   • Inefficiencies.
4. SIMPL --- writing, interpreting small programs.