also see the individual quizzes (the Final Exam is comprehensive)

Overview of C++ features

built-in data types, arrays, data (variable) declarations; function declarations and definitions; statements, expressions,
operators and precedence; logic statements:  iteration (while, for, do-while), selection (if, if-else, switch);
classes with member functions and private areas; function overloading; inheritance; dynamic objects using new &
delete,
scope & storage class (static, auto, extern), inline, constructors & destructors, copy constructors, ctor-initializer;
stream I/O (ios, istream, and ostream classes; overloaded << and >> operators, manipulators); scope resolution
operator ::
 

Object-Oriented concepts and programming

objects (states, methods, messages, classes); prototype vs. instance,
key properties: encapsulation, polymorphism, inheritance;
 

Style

definition, reasons, aspects; readability (methods), modularity, efficiency, robustness, maintainablity, portability:
readability methods: choice of algorithms & data structures, comments, white space & indenting, choice of identifiers
 

Dense Lists, Stacks, and Queues

structured data concepts:  scalar vs. structured data, homogeneous vs. heterogeneous, linear/sequential vs. branching;
linear homogeneous data structures: lists, vectors, arrays (mapping concept);
stack concepts: linear homogeneous container class, LIFO protocol, terminology: Top, Push, Pop;
specification and dense implementation of Push, Pop, and Empty operations; underflow and overflow exceptions;
queue concepts: FIFO protocol, operations (Insert, Remove, PeekFront, Empty), dense implementation (circular array
use);
stack applications:  sub-task management, expression evaluation, system stack; queue applications:  fair service,
buffering
 

Abstract Data Types

ADT concept/definition; features of "type" -- allowed values, representation/storage needed, operations;
overloading operators natural to the operations on the type; , overload resolution process;
rules of overloading operators:    declaring and defining overloaded operators {unary, binary; regular, member}; only
user types; allowed operators, maintain precedence and syntax rules;
 

Exceptions

approaches to error handling; goals of C++ exception approach;
throwing, propagation, and catching of C++ exceptions; try-catch blocks; catch handler structure; re-throwing;
exception specifications (throw lists); types for exceptions: basic types (integer, string), class types and inheritance;
 

Linked Stacks and Queues

pointers, dynamic structures, storage allocation/management, operations (new, delete, new[], delete[]), pointer
arithmetic;
Node class with link field, ctor? linked stack implementation; assignment operator overloading and copy ctors;
linked queue implementation, which ends for Head and Tail;
 

Recursion

recursion concepts; structure of a recursive algorithm:  selection logic, base case, recursive call(s);
relations between program call structures (trees, dags), recursive structure, and stack processing;
examples of recursive applications, relative efficiency of iteration and recursion for various applications;
 

Lists and Strings

linked-list operations and implementation:  AddFirst, AddAfter, Remove, Search, Scan/Traverse;
simple/forward linked lists, doubly-linked lists, circularly-linked lists, sentinel nodes; pros and cons of each;
string manipulation: C-strings (null-terminated char arrays, string literals, string.h/cstring functions),
    ISO-ANSI C++ string class (operations, advantages); CString and user-defined string classes;
files and string streams (under old and new standards; header files; behavior of input and output string streams)
 

Standard Template Library

template functions, classes, type parameters;  containers, container adaptors, iterators, and algorithms;
header files, <deque>, <stack>, <queue>, <vector>, <list>
operations provided for all containers, those specific to stack, queue, vector, and list classes
 

Files & String Streams

classes ios, istream, ostream, streambuf, ifstream, ofstream, etc
constructor and open for file stream classes; arguments:
        file name, mode flags (ios::in, ios::app, ios::binary, etc)
disk file operations:  ctor, open, close, + istream and/or ostream operations
direct access files:  tellp/g( ), seekp/g(position +); binary data: read(ptr, nbytes), write(ptr, nbytes)
string streams:  old C++ vs ISO versions; extract from line, data conversions, dynamic
        buffer use and access with str()
safer input processing with cin.getline(buf,size) and istream IB(buf)
using strstreams for string <=> numeric conversions
 

Algorithmic Efficiency; Searching Methods

efficiency: run-time, storage; big-O notation: O(f(N))
relative orders of efficiency: C, log N, N, polynomial, N! or exponential
Searching methods: linear search, improved linear (search value added),
        binary search; efficiency and costs of each
 

Sorting Methods

variety and efficiency of sorting algorithms; details of specific algorithms:
     bubble, insertion, selection, Shell, merge, Quicksort, Heapsort; STL sorting
 

Storage and Retrieval Structures

concepts of storage and retrieval structures; operations: Add(obj), Retrieve(key), Delete(key);
efficiency issues and implementations:  arrays/lists/tables, tree-based, hash tables
concepts and principles of hashing:  map keys to locations by hash function,
        collision handling: sequential (why bad), re-hash, linked/overflow, buckets;
implementation of hash tables
 

Trees and Tree-based Retrieval Structures

tree concepts (graphs, nodes, edges, digraphs, cycles, indegree, outdegree, definition of a directed tree)
        and terminology (degree, level, height, root, branch, leaf, parent, child, sibling, ancestor, descendant)
tree implementations and operations, traversals (Pre-order, Post-order, Level-order);
ordered trees, implementations, and equivalent binary trees;
binary trees; operations, recursive traversals (NLR, LNR, LRN), key-structured and sort trees;
storage/retrieval balanced trees and algorithms:  AVL trees, tries, B-trees (2-3 trees);
 

Graphs and Graph Applications

graph concepts, mathematical theory, and applications;
graph implementations: fixed pointers, linked pointer lists, node, edge, and link storage node types;
graph traversals:  depth-first, breadth-first; flags or list to avoid duplicate visits;
weighted graphs:  applications, implementations (weight matrix), algorithms: short path, traveling salesman,
        minimal spanning tree, PERT/CPM