CPSC 225, Spring 2003                      Information about the Third Test
----------------------------------------------------------------------------

   The third test in this course will be given in class on Monday,
April 7.  It covers everything that we have done since the previous test.
This includes recursion, linked lists, and binary trees.  The reading
from the textbook is Chapter 13 on recursion and pages 690--710 on
linked lists.  The reading on binary trees is the handout that was given
out in class.  You will not be responsible on this test for "expression
trees", which are covered near the end of the handout.  Note that we did
many examples of recursion in class that are not in the book.  Here is
a list of the things that we have covered:

   command-line parameters
   using  "int main(int argc, char *argv[])" for a main function
   recursion
   recursive functions
   iterative algorithms
   the recursive Merge Sort algorithm
   binary search
   comparison of binary search with linear search
   base case of a recursion
   infinite recursion errors
   why does recursion work?
   computing power(x,n) recursively (x raised to the power n)
   activation frame
   contents of an activation frame
   stack of activation frames
   implementation of recursion using activation frames
   the Knight's Tour problem and its recursive solution
   Quicksort
   recursive maze solving
   recursive "blob" counting
   "marking" a visited spot in a maze, chessboard, blob, etc.
        and why this is important in recursion
   objects that contain pointers to other objects
   the "->" notation for accessing a member of an object through a pointer
   linked lists
   list nodes
   empty list
   using the "next" pointer in a list node
   traversing a linked list, and processing all the items that it contains
   adding an item at the start of a list
   using a "previous" pointer, in addition to a "runner"
   deleting an item from a list
   sorted linked lists
   inserting an item into a sorted linked list
   recursive algorithm for copying a linked list
   binary trees
   left subtree and right subtree of a tree
   empty tree
   tree nodes
   traversing a tree, and processing all the items that it contains:
      pre-order traversal
      in-order traversal
      post-order traversal
   root of a tree
   leaf node in a tree
   binary sort trees
   efficiency of binary sort trees
   finding an item in a binary sort tree, recursively or iteratively
   inserting an item into a binary sort tree using recursion

Here are some examples of the types of things you could be asked to do
with linked lists and with binary trees:

   --Write C++ code to create a given tree or list shown as a picture
   --Count the number of nodes in a linked list or binary tree
   --Count the number of leaf nodes in a binary tree
   --Make an exact copy of a binary tree
   --Determine whether a linked list of strings contains the word "Fred"
   --Count the number of times the word "Fred" occurs in a linked list
   --Add a node at the end of a linked list
   --Suppose that  root  is a pointer to a binary tree in which the items
       are integers.  Find the sum of all the numbers.
   --Make a reversed copy of the linked list, in which the first node
       becomes the last node and so on
   --Given a binary tree, show the order in which elements would be 
       visited in a pre-, in-, or post-order traversal of the tree