CSc 17 Final   Saturday 18 December 1999
      >>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<,
      1.  (25 pts)  a.  Provide the missing documentation for the
                        function below.
                    b.  Determine the complexity of the algorithm used
                        in the function and state the complexity in
                        terms of the O() notation.

        // Purpose:  Determine whether any two adjacent entries in data[0],
                   data[1],...,data[n] are duplicates.
        // Preconditions: n>=0
        // Postconditions: data, and n left unchanged
        //                 return true if and only if two entries are the
        //                 same.
           bool one(int data[],int n){
             int j;
             bool d;

             d=false;
             while(n>0 && !d){
               j=0;
               while(j<n-1 && !d){
                 d=data[j]==data[j+1];
                 j++;
               }
               n--;
             }
             return d;
           }

         The number of iterations of the loop is 1+2+...+(n-1)=n(n-1)/2
         =n*n/2-n/2 ==>O(n^2)
    2.  (25 pts)  Write a private recursive member function for the class
    Tree which returns true if and only if every entry in the tree is even.
    Assume the function is named EVEN and is called by other member functions
    as follows, EVEN(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 EVEN.  EVEN can assume that root is
    either NULL or the root of a properly built binary tree.
                private:
                  bool EVEN();    //prototype

      bool Tree::EVEN(BinaryNode *root){
       if(root==NULL)
         return true;
       return root->key %2 ==0 && EVEN(root->child[0])&&EVEN(root->child[1]);
      }
    3.  (15 pts) a.  Write the prototype for the function GLOG so that the
                     following code will compile (Tree is defined in 2).
                     Tree a[5];
                       if(GLOG(a[3]) && GLOG(6))
                         cout<<"This code is silly";
                 b.  Write the prototype for the function FOG so that the
                     following code will compile.
                       int a[3][4], b[5][6][4];
                       cout<<(FOG(a,3,4)+FOG(b[3],6,4));
        template<class A>
           bool GLOG(A b){}
        int FOG(int x[][4],int a, int b){}

    4.  (25 pts)  Write the function "meanUpcase" which returns the
    average number of upper-case letters per line in a file.  Calls to
    the function take the form "meanUpcase(f)", where f is declared
    to be of type "ifstream".
       void getCh(ifstream &f,char &ch){
          if(!f.eof())
            f.get(ch);
          if(f.eof())
            ch='\n';
          cout<<ch;
       }
       double meanUpcase(ifstream &f){
        int charCt,lineCt;
        char ch;
        charCt=0;
        lineCt=0;
        getCh(f,ch);
        while(!f.eof()){
          lineCt++;
          while(ch!='\n'){
            if(ch>='A' && ch<='Z')
              charCt++;
            getCh(f,ch);
          }
          getCh(f,ch);
        }
        return double(charCt)/lineCt;
      }

    5.  (25 pts) Assume you have the class Link defined below. Write the
    definition (not the prototype) of the function which returns true
    if and only if every entry in a linked list is even.  Assume the
    function is named EVEN and is called as follows, EVEN(head), where
    "head" is a pointer to a linked list of Links and class Link is
    defined as follows:
          class Link{ public:
                       int key;
                       Link *next; };
    The function EVEN can assume that "head" is either NULL or points to
    a properly formed linked list whose last Link points to NULL.
     bool EVEN(Link *head){
        bool good;
        good=true;
        while(head!=NULL && good){
          good=head->key%2==0;
          head=head->next;
        }
        return good;
     }
    6.  (15 pts)  Consider the data abstraction of the Staque.  It combines
    the properties of the stack and the queue.  Give a detailed description
    of this data abstraction.  (It is inappropriate to answer this question
    by given the interface for a C++ class which implements a Staque.  I am
    am asking for a description of its properties.)
      A Staque stores homegeneous items.  It has the following operations:
        (a)  Empty.  One can ask a Staque whether it contains any items.
             It answers no(true) or yes(false).
        (b)  Full.  One can ask a Staque whether it has any room to store
             another item.  It answers no(true) or yes(false).
        (c)  Pop.  Retrieve (and remove from the Staque) the item which
             was most recently stored.  If there are no items, report an
             error.
        (d)  Dequeue.  Retrieve (and remove from the Staque) the item which
             has been stored the longest.  If there are no items, report an
             error.
        (e)  Add.  Add an item to the Staque. If there is no room to add an
             item, report an error.
        (f)  There are other, less important, operations one might have:
               i) Count.  Return the number of items stored.
               ii) Top.  Return the item most recently stored, but do not
                   remove it.
               iii) Bottom.  Return the item in the Staque the longest, but
                    do not remove it.
               iv)  Flush.  Empty out the stack.

    7.  (20 pts) For the class Link defined in question 5, write the
    prototype and definition for overloading "<<".  You should overload
    "<<" so that, e.g., if aLink is of type Link and aLink's key equals 7,
    then "cout << aLink" should cause the following to appear on the screen
    (without quotes):  "Link[7]"
      friend ostream& operator<<(ostream &out,Link a); //Prototype
      ostream& operator<<(ostream &out,Link a){  //Definition
          out<<"Link["<<a.key<<"]";
          return out;
      }

    8.  (10 pts) Document the following function, where LinkStack
    is a class which implements a stack for storing objects of type
    Link, where Link is defined in question 5.
      //Purpose: Display on the screen the contents of a linked list
      //         if reverse order
      //PreConditions:  head points to a properly formed linked list,
      //                where eacn node points to another node or (in
      //                the case of the last node) points to NULL
      //PostConditions: the original list is unchanged.  The contents
      //                of the list appear on the screen in reverse
      //                order.
      void two(Link *head){
        LinkStack stk;
        while(head!=NULL){
          stk.push(*head);
          head=head->next;
        }
        while(!stk.empty())
          cout<<stk.pop().key<<endl;
      }

    9.  (15 pts)  What is the output of the following code?
             class BinaryNode{
                    public:
                     int key;
                     BinaryNode *child[2];
             };
             BinaryNode *rt;
             int xx[5][3],j;
             for(int j=0;j<5;j++)
              for(int k=0;k<3;k++)
                xx[j][k]=10*j+5*k%3;
             for(int j=2;j<5;j++)
               cout<<xx[2][j]<<" "<<endl;              //  21
             rt=new BinaryNode;                        //  30
             rt->key=4;                                //  32
             rt->child[0]=rt;
             rt->child[1]=NULL;
             j=0;
             while(rt!=NULL){
               cout<<(rt->key+j)<<endl;                //   4
               rt=rt->child[j];                        //   5
               j++;  }

   10. (25 pts)  Write a function called "Reverse" which reverses the order
   in which the elements of an array of doubles appear.  If we have
   double x[20], then after the call Reverse(x,10) the entry that was
   formerly the 10th entry in x is now the first entry, the entry that
   was formerly the 9th entry is now the second entry, etc.
     void Reverse(double x[],int last){
       int bot;
       double temp;
       bot=0;
       last--;
       while(bot<last){
          temp=x[bot];
          x[bot]=x[last];
          x[last]=temp;
          bot++;
          last--;
       }
     }