CSc 17  Final Examination    Monday  14 December 1998              Page 1

   1.  (   pts)  Assume the declarations of class biNode and of rt below.
    Write a function "zero" such that the call "zero(rt)" stores a 0 in each
    leaf of the tree whose root is rt.  The function assumes that rt is
    indeed the root of a properly defined tree.  That is, rt either points
    to NULL or to a biNode, and the children of each biNode in the tree
    are either NULL or a biNode.
            class biNode{
                 public:
                   int key;
                   biNode *left,*right;
            }
            biNode *rt;
       -------------
       void zero(biNode *rt){
          if(rt!=NULL)
           if(rt->left==NULL && rt->right==NULL)
              rt->key=0;
           else {
              zero(rt->left);
              zero(rt->right);
           }
       }

   2. (   pts) Write a function DIGITS which makes a copy of a file of text
    which is identical to the original file, except that any line which has
    at least one digit has an asterisk (*) appended to it.  So, for example,
    if the file consists of 7 lines of text for this question, the new file
    would be identical, except that the first and fourth lines would have
    an asterisk at the end.  Assume the call is DIGITS(in,out) where we
    have ofstream out; ifstream in;

       void DIGITS(istream &in,ostream &out){
          char ch;
          bool foundDigit;
          in.get(ch);
          while(!in.eof()){
             foundDigit=false;
             while(ch!='\n' && !in.eof()){
               if(ch>='0' && ch<='9')
                 foundDigit=true;
               out.put(ch);
               in.get(ch);
             }
          if(foundDigit)
            out.put('*');
          out.put('\n');
          in.get(ch);
         }
      }


   3. (   pts) Suppose we have the following prototypes and declarations.
         int f(int i, int j);
         int g(int k, int l);
         char ch[200];
         int  ints[100];
         double dubs[50];
    Write (only) the prototype for the function GLOB so that all the
    following calls will compile:
        GLOB(ch,190,f);
        GLOB(ints,45,g);
        GLOB(dubs,30,f);

       template <class T>
       void GLOB(T x[],int last,int f(int v, int w));

   4. (   pts) I want to use a stack to mimic the recursion of the function
   RECURSE, which is below.  The stack would store frames which have the
   necessary information. Write the declaration of the class that would
   be used to declare the frames which would be stored on the stack in
   mimicking the recursion.  (I have no idea what RECURSE is supposed to
   do.)

           void RECURSE(int n, int m, int j){
              int k;

              cout<<(n+m+j);
              k=2*m+j;
              if(n>0){
                 k=k-1;
                 RECURSE(n-1,m-k,j-k);
                 k=k+2;
                 RECURSE(n-2,m,k);
                 k=k-2;
                 RECURSE(n-3,m,k);
              }
           }

       class Frame {
          int en,em,jay,kay,step;
       }


   5. (   pts) Given the declaration of the class Length below
     (1) add a prototype to the class for a member function PLUS.  Then
       write its definition.  The member function PLUS has the property
       that for class instances A and B, A.PLUS(B) returns an instance
       of Length which stores the sum of A and B.
     (2) add a prototype to the class for an overloaded operator "<".  Then
       write its definition.  For class instances A and B the expression
       A<B returns true if and only if the length stored in A is less than
       the length stored in B.

             class Length{
                 public:
                   Length();
                   Length PLUS(Length B);  //added for answer
                   friend bool operator < (Length A, Length B);
                                          //added for answer
                 private:
                    int inches,feet;
             };


             Length Length::PLUS(Length B){
                  Length temp;
                  temp.inches=inches+B.inches;
                  temp.feet=feet+B.feet;
                  temp.feet=temp.feet+temp.inches/12; //These two lines are
                  temp.inches=temp.inches%12;        //not required
                  return temp;
             }

             bool operator < (Length A, Length B){
                return (A.inches + A.feet*12 < B.inches +B.feet*12);
             }

   6.  (   pts) The following function needs some documentation.  Provide
      it.  HINT: You get little or no credit for restating the details
      of the computation.

           bool func(char a[], char b[]){
              bool x;
              int loc;
              loc=0;
              while(a[loc]==b[loc] && a[loc]!='\0')
                 loc++;
              return (a[loc]<b[loc]);
           }

    //Purpose: To determine whether the string of characters in a
    //         is lexicographically less than (would appear in a dictionary
    //         before) b.  The comparison is case sensitive, so that, e.g.,
    //         'A'<...<'Z'<'a'<...<'z'
    //Precondition:  The strings of characters in a and b end with the
    //         character '\0'.
    //Postcondition:  The values of a and b are unchanged. The truth of
    //         comparison is returned

   7.  (   pts)  Write a recursive function SUM which returns the sum
      of the entries in an array of doubles by using the following
      recursive algorithm: Add the first and last entries to the sum
      of the rest of the entries in between the first and last entries.
      So, if x is an array of doubles, the call SUM(x,0,20) would return
      the sum x[0]+x[1]+...+x[20].

      double sum(double x[],int first,int last){
        if(first==last)
          return x[first];
        if(first<last)
          return (x[first]+x[last]+sum(x,first+1,last-1));
        return 0;
      }

   8.  (10 pts) Describe the properties of a queue.
      A queue stores homogeneous items, where the order of storage and
      removal is important.  Items can only be removed from the queue
      in the same order as they are stored (first in, first out).  A
      queue has four operations:  (1) answer whether the queue is empty,
      (2) answer whether the queue is full, (3) add an item, provided
      the queue is not full, and (4) remove an item, provided the queue
      is not empty.

   9.  (25 pts)  Write a function SORT.  It is called as follows:
     SORT(X,first,last), where X is an array of doubles, first and last
     are ints, and the function sorts in ascending order all the entries
     x[first], ..., x[last].  You may use whichever sorting algorithm
     you like.

       I use the bubble sort:

       void SORT(double x[], int first, int last){
         bool done;
         double temp;
         do{        //if first>=last, no sorting is done
          done=true;
          for(int k=first;k<last-1;k++)
            if(x[k]>x[k+1]){
              temp=x[k];
              x[k]=x[k+1];
              x[k+1]=temp;
              done=false;
            }
         } while (!done);
       }

  10. (25 pts) Given the class Link defined below, write a function
    SUM which returns the sum of all the numbers in a linked list.  It
    is called as follows: SUM(x), where x is a pointer to a Link.  The
    function assumes that x is either NULL or a Link, that each Link points
    to either NULL or another Link, and that one Link points to NULL.
        class Link{
          public:
            int n;
            Link *next;
        }

     int SUM(Link *x){
       int tempS;
       tempS=0;
       while(x!=NULL){
         tempS+=x->n;
         x=x->next;
       }
       return (tempS);
     }