Exam 3 Study Guide

You MUST present a picture ID upon turning your exam in.

Exam Date: Tuesday, May 21
Exam Time: 1:00 - 3:00pm

Use the list of topics below as a guide when studying for Exam 3. It is by no means a comprehensive list of all material that you are responsible for. In general, you are responsible for the material presented in lecture from inheritance through trees. You are also responsible for all associated reading assignments.

• Inheritance
  • Terminology: base class, derived class, multiple inheritance, public inheritance
  • The difference between public, private, and protected member access specifiers
  • How inheritance promotes code reuse
  • The difference between "uses a", "has a", and "is a " relationships
  • The syntax for a derived class and its members functions
  • The order in which constructors and destructors are called when using inheritance
  • Overriding vs. overloading member functions
  • How base and derived class objects and pointers may and may not be mixed
  • Why one would choose to use inheritance rather than a template class(es)

• Polymorphism
  • Terminology: abstract class, concrete class
  • Static vs. dynamic binding (be able to distinguish between the two)
  • Virtual vs. pure virtual member functions
  • The syntax used to implement polymorphism
  • Why virtual destructors are necessary

• Templates
  • The syntax for a non-member template function
  • The syntax for template classes and their member functions
  • Why one would choose to use a template class(es) rather than inheritance

• Lists
  • The difference between a list ADT and a list implementation
  • Typical list operations and their interfaces
  • Design decisions that must be made regarding typical list operations
  • The advantages and disadvantages of implementing a list as an array vs. implementing it as a linked list
  • The syntax for implementing a list as an array or a linked list (the .H file)
  • The syntax for basic operations on a singly-linked list (the .C file)
  • Performance of and tradeoffs between a singly-linked list vs. a doubly-linked list

• Exception Handling
  • Commons errors that might be dealt with using exception handling
  • The C++ syntax for exception handling
  • Why one would throw an exception object rather than throw a simple data type (e.g., an int)
  • Which function should throw and which should catch an exception
  • Why a function would rethrow the same exception or throw a new exception
  • Nested function calls and stack unwinding

• Trees
  • Terminology: node, edge, path, root, internal node, external node, leaf, subtree, parent, child, sibling, depth and height of a node, depth and height of a tree, full binary tree, perfect binary tree, ancestor, descendant
  • Understand the difference between a general tree, a binary tree, and a binary search tree.
  • Be able to illustrate the storage of a general tree using First Child, Next Sibling storage
  • Be able to show a breadth-first (using a queue) or a depth-first (using a stack) traversal of a general tree
  • Be able to show a preorder, inorder, or postorder traversal of a general binary tree
  • Be able to show how to search, insert items into, or remove items from a binary search tree
  • Be able to contrast the performance of search, insert, and remove operations on a general binary tree vs. a binary search tree