CSc 17  Test 2  Friday  13 November 1998                      Page 1
   >>>>>>>>>>>   Answers <<<<<<<<<<<<<<<<<<<<<<<

   1.  (15 pts) In writing the function below, I forgot to provide the
        documention.  Provide it by stating the pre- and post-conditions.
        The function assumes the class Node, which is defined as follows:

          class Node{
           public:
            int key;
            Node * next;
          };

          void enigma(Node * head, int x, int &c){
            if(head!=NULL){
              if(head->key > x)
                   c++;
              enigma(head->next,x,c);
            }
          }

     PRECONDITIONS: head is NULL or points to a valid node. Valid nodes
                    either point to NULL or to a valid node.  The variable
                    c has some value, x has some value
     POSTCONDITIONS: c has been increased by the number of nodes whose
                     keys exceed x.

   2.  (25 pts) Write a bool function, dup, such that the call
         dup(head) returns the value true if and only if the linked
         list to which head points has two consecutive keys which
         are equal.  Assume that head is declared as Node * head, as
         where Node is the class defined in question 1.  Of course,
         you can assume that the last link  in the list points to NULL.
         For example, if we have head->2->3->2->4, dup(head) returns
         false; if we have head->3->7->8->8->4, dup(head) returns true.
           bool dup(Node * head){
             bool found;
             found=false;
             while(!found && head!=NULL && head->next!=NULL){
               found=head->key==head->next->key;
               head=head->next;
             }
            return found;
           }

   3.  (15 pts) Draw pictures of a binary tree after each of the following
         numbers are added to the tree in the order in which they are read
         and such that the tree will produce a sorted list if traveresed
         with an in-order traversal: 9, 6, 12, 4, 8, 10, 7, 11.  Then
         show the tree after the entry at the root is removed twice (i.e.,
         the tree is reconfigured twice, each time deleting the entry at
         the root).
            9    9    9           9        9          9           9
               6     6  12      6  12    6   12     6   12      6    12
                                        4         4  8        4  8  10

             9                 9               8              7
          6     12          6       12       6     12       6    12
       4    8  10        4    8  10        4  7  10       4    10
           7                 7    11              11            11

   4.  (20 pts)  Suppose we are given the class definition for biNode
         below, a class used for creating binary trees. Overload the
         operator << so that it can be included in class biNode and
         have the property that for the declaration
             biNode *h
         the statement
             cout<<h
         displays either NULL, if h is NULL or displays h in the form
         a<-x->b, where each of a and be are either the word NULL or BINODE,
         and x is the value of the key.  For example, if h points to a node
         whose left child is NULL, whose right child is not NULL, and whose
         key is 17, then
         cout<<h
         will produce    NULL<-17->BINODE
           class biNode {
             public:
               int key;
               biNode *left,*right;
           }
      The operator cannot be overloaded, because it is already defined for
      pointers.  The answer below assumes that the ooperator can be overloaded.

         Provide both the prototype and the definition.
           friend ostream & operator <<(ostream &out,biNode * root);
           ostream & operator <<(ostream &out, biNode * root) {
             if(root==NULL)
              out<<"NULL";
             else {
               if(root->left==NULL)
                out<<"NULL";
               else
                out<<"BINODE";
               out<<"<-"<<root->key<<"<-";
               if(root->right==NULL)
                out<<"NULL";
               else
                out<<"BINODE";
             }
            return out;
          }

   CSc 17  Test 2  Friday  13 November 1998                      Page 2

   5.  (25 pts) Write a function max such that max(x,last) returns the
         largest entry in the array x between x[0] and x[last], inclusive.
         The function  requires no documentation, assumes 100>last>0, and
         assumes x is defined as    double x[100].

           double max(double x[],int last){
              double temp;
              temp=x[0];
              for(int loc=1;loc<=last;loc++)
               if(x[loc]>temp)
                 temp=x[loc];
              return temp;
           }