CSc 17 Test 1  Monday 22 November 1999
          >>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<
    1.  (25 pts)  Write a private recursive member function for the class
    Tree which visits every node in a binary tree and increments the number
    in each node by 1.  Assume the function is named INC and is called by
    other member functions as follows, INC(root), where the class Tree is
    defined as follows:
                      class Tree{
                          class BinaryNode{
                            public:
                              int key;
                              BinaryNode *child[2];
                          };
                        public:
                          //other stuff
                        private:
                          BinaryNode *root;
                          //other stuff
                      };
    You need not write the prototype of INC.  INC can assume that root is
    either NULL or the root of a properly built binary tree.
          void Tree::INC(BinaryNode *rt){
            if(rt!=NULL){
              rt->key++;
              INC(rt->child[0]);
              INC(rt->child[1]);
            }
          }

    2.  (15 pts) Suppose that the class Node is as defined below.  Document
    the function PURP, below.
           class Node{
             public:
               int x;
               Node *a[2];
           };

     //Return the product of all the entries in the tree whose root is r
     //PreConditions: r is either NULL or points to a properly constructed
     //tree, where each child is another node or NULL
       int PURP(Node *r){
        if(r==NULL)
         return 1;
        else
         return(r->key * PURP(r->a[0]) * PURP(r->a[1]));
       }
    3.  (10 pts) Assume that the class Link is as defined below.  State
    the output of the code below.
          class Link{ public:
                       int key;
                       Link *next; };
          Link *a,*b;
          a=new Link;
          a->key=19;
          b=a;
          for(int j=1;j<4;j++){
            b->next=new Link;
            b=b->next;
            b->key=j;
          }
          b->next=a;
          for(int j=1;j<6;j++){
            cout<<(b->key)<<"  ";
            b=b->next;
          }
        >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>3 19 1 2 3
    4.  (25 pts)  Write overloaded operators "+" and "==" for the class
    Junk defined below such that for Junk a,b,c;  the expression
    "a+b+c" returns an object of class Junk containing the sum of the
    entries in a, b, and c, and the expression "a==b" returns true if
    and only if the contents of a and be are the same.  You need not
    write the prototypes.

        class Junk{
          public:
            int x;
        };

       Junk operator+(const Junk & a, const Junk & b){
         Junk temp;
         temp.x=a.x+b.x;
         return temp;
       }

       bool operator ==(const Junk &a,const Junk &b){
         return a.x==b.x;
       }

    5.  (25 pts) Assume the class Link defined in question 3 is used to
    create a linked list and that head, defined as Link *head, points
    to the first Link in the list.  Further assume we have defined int x;
    Write a function Insert such that the call Insert(head,x) causes
    a new Link containing x to be inserted at the beginning of the list
    pointed to by head.

      void Insert(Link *&head, int x){
         Link *temp;
         temp=new Link;
         temp->key=x;
         temp->next=head;
         head=temp;
      }