CPSC 225, Spring 2002                         Information for the Second Test
------------------------------------------------------------------------------
   The second test for this course will take place on Friday, April 5.  It will
cover everything we have done since the first test.  This includes Chapter
8 (operator overloading), Chapter 10 (pointers), Section 17.1 (linked
lists, but not including templates), and Chapter 13 (recursion).  In addition
to the material from the text, we also covered binary trees and binary sort
trees and several applications of recursion.  You should make sure that you
understand the programming assignments 6 and 7 and sample programs that
I have handed out in class.  (The sample programs mystrings.cc, blobber.cc,
percolation.cc, expression.cc, and sentence.cc can be found in /home/cs225.)
Here is a list of some of the things you need to know about:

   operator overloading
   overloaded operators as independent functions
   overloaded operators as class members
   overloading the assignment operator
   pointers
   declaring pointer variables
   the unary * operator ( *ptr, where ptr is a pointer variable )
   the unary & operator ( &x, where x is any variable )
   pointer types for parameters and return values
   the "new" operator for constructing objects on the heap
   the "delete" operator
   the -> operator ( ptr->field, where ptr is a pointer to an object,
                     and field is the name of a member of the object )
   the notation "(*ptr).field" as an alternative to ptr->field
   pointers in C++ compared to pointers in Java
   pointer arithmetic:  ptr++ and ptr--, where ptr is a pointer variable;
                        ptr + i, where i is an integer
   equivalence of A[i] and  *(A + i)
   using the "new" operator to create arrays ( new int[100], for example )
   the "delete[]" operator
   using the type  char*  for C-style strings
   linked data structures
   linked lists
   NULL pointers
   using "runner = runner->next" to traverse a list
   linked list operations:  insert a node at head of list, or in middle of list
                            delete first node, or a node in the middle of list
                            find an item in a linked list, etc.
   sorted linked lists
   recursive functions
   base case of a recursion; recursive case of a recursion
   examples of recursion, such as factorial, blob counting, maze solving
   BNF grammars and recursion
   binary trees
   empty tree
   root of a binary tree
   left subtree and right subtree of a binary tree
   tree traversal algorithms:  preorder, inorder, and postorder
   binary sort trees
   the binary sort tree property
   examples of recursion with binary trees, such as copying, printing all
        the nodes, counting the nodes, counting the leaves, finding an
        item, inserting an item in a BST, etc.
   leaf node in a tree
   recursive evaluation of arithmetic expressions
   activation record
   implementation of recursion using activation records