CSc 17 Final Examination  Friday 2 July 1999      Page 1

     >>>>>>>>>>>>>>ANSWERS>>>>>>>>>>>>>>>>>>>>>>>>.
  1.  (25 pts)  Call an array of ints with one entry "balanced" if the entry
  is 9.  Call an array of ints with two entries "balanced" if the sum of the
  two entries is 9.  Call an array of ints with more than two entries
  "balanced" if the sum of the first and last entry is 9 and the rest of the
  array between the first and last entries is balanced.  Use this recursive
  definition (and do not change it) to write a recursive function "balanced"
  which is called as follows, balanced(x,first,last), where x is an array of
  ints and first and last are ints giving the locations of the first and last
  entries in the array. The call "balanced(x,first,last)" should return true
  when the array is balanced and false otherwise.
     bool balanced(int x[],int first,int last){
       if(first>last)
        return true;
       if(firts==last)
        return x[first]==9;
       return( x[first]+x[last]==9 && balanced(x,first+1,last-1));
     }

  2.  (10 pts)  Assume the class IntStack is defined as follows:
   class IntStack{
      public:
       IntStack(int n);
       IntStack(IntStack & stk);
       ~IntStack();
       bool empty();
       bool full();
       int pop();
       void push(int x);
       int peek();
      private:
       IntStack();  //Don't allow use
       int size, top,    //top points to the first free location
              *stk;
       void error(char *mess);
     };

   Also assume that the class IntQueue has been similarly defined.
   What is the output of the following code?



      IntStack stk[20];
      IntQueue q[20];
      for(int j=0;j<10;j++)
        if(j%2 ==0)
          stk.push(j);
        else
          q.enqueue(j);
      for(int j=0;j<2;j++){
        cout<<q.dequeue()<<endl;           //1
        stk.push(q.dequeue());             //5
      }                                    //7
      for(int j=0;j<2;j++)){               //8
        cout<<stk.pop()<<endl;             //9
        q.enqueue(stk.pop());
      }
      cout<<q.dequeue()<<endl;

  3.  (30 pts) For the class IntStack defined in question 2
    (a) write the prototype and definiton of a member function "rotate" which
    takes no arguments and which puts the top entry in the stack at the
    bottom.
           void rotate();
           void IntStack::rotate(){
             if(!empty()){
               int temp;
               IntStack tStk(size);
               temp=pop();
               while(!empty())
                 tStk.push(pop());
               push(temp);
               while(!tStk.empty())
                 push(tStk.pop());
             }
           }

    (b) write the prototype and definition of an overloaded operator << such
    that for an instance of IntStack, stk, the statement "cout<<stk" would
    display the contents of the stack.
       friend ostream & operator <<(ostream &out,IntStack & st);
       ostream & operator <<(ostream &out,IntStack & st){
         out<<"Stack(bottom)[\n";
         for(int j=0;j<st.top;j++){
          if(j>0)
            out<<", ";
          out<<st.stk[j];
         }
         out<<"]";
        return out;
       }

  4.  (25 pts)  Assume the following structure, is used to build a binary
  tree:     class BiNode{
                public: double key;
                        BiNode *child[2];
               }
  Write a function named "exceeds", which is called as follows,
  exceeds(root,n), where root is declared as BiNode *root, and root points
  to the root of a properly constructed binary tree and n is of type double.
  The call exceeds(root,n) should return the value of true if and only if
  some entry in the tree pointed to by root exceeds n.
      bool exceeds(BiNode *rt,double x){
        if(rt==NULL)
          return false;
        if(rt->key>x)
          return true;
        return exceeds(rt->child[0],x) || exceeds(rt->child[1],x);
      }


  5. (15  pts)  I forgot to document the following procedure.  Provide
  the missing documentation for the procdure (not for the class).

  //Purpose: Determine whether two linked lists have the same entries
  //         in the same order
  //PreConditions: x and y each either point to NULL or the first node of
  //               a well-defined linked list which terminates with a NULL
  //               pointer, with each node appearing only once in the list
  //               (i.e., no loops)
  //PostCondtions: The lists are unchanged.  A true is returned if and only
  //               if the lists are of the same length and their corresponding
  //               nodes contain the same entries.
   class Link{
     public:
      double key;
      Link * next;
   };
   bool h(Link *x, Link*y){
      while(x!=NULL && y!=NULL && x->key == y->key){
        x=x->next;
        y=y->next;
     }
     return x==NULL && y==NULL;
  }


  6.  (30 pts) Assume the class Link of problem 5 is used to construct a
  linked list with "head" pointing to the first link, where head is declared
  as Link *head, and assume that cHead is declared as Link * cHead.  Write
  the function "copy", called as follows, copy(head,cHead).  After the call
  cHead points to a linked list containing the same numbers (but not the same
  Links) as the linked list to which head points. Don't worry about heap
  errors.
    void copy(Link*head,Link*&cHead){
    //recursive
      if(head==NULL)
        cHead==NULL;
      else{
        cHead=new Link;
        cHead->key=head->key;
        copy(head->next,cHead->next);
      }
    }

    void copy(Link*head,Link*&cHead){
    //non-recursive
      if(head==NULL){
         cHead=NULL;
         return;
      }
      Link *loc;
      cHead=new Link;
      cHead->key=head->key;
      loc=cHead;
      while(head->next!=NULL){
        loc->next=new Link;
        loc=loc->next;
        head=head->next;
        loc->key=head->key;
      }
      loc->next=NULL;
    }

  7.  (30 pts)  Write a function "replace" which is called as follows,
  replace(in,out,oldCh,newCh), where in, out, oldCh, and newCh are declared
  as: istream in; ostream out; char oldCh,newCh;  After the call the file
  referred to by "out" contains an exact copy of the contents of the file
  referred to by "in", except that every occurrence of the character stored
  in oldCh is replaced by the character stored in newCh.
    void replace(istream &in,ostream&out,char oldCh,char newCh){
      char ch;
      in.get(ch);
      while(!in.eof()){
       if(ch==oldCh)
         ch=newCh;
       out.put(ch);
       in.get(ch);
      }
    }

  8.  (25 pts)  Write a function "sum" which is called as follows, sum(g,n),
  where g is a function whose prototype is int g(int x) and n is an int.  The
  call sum(g,n) returns the number obtained by adding g(1), g(2), ..., g(n).
     int sum(int g(int x),int n){
       int temp;
       temp=0;
       for(int j=1; j<=n; j++)
         temp+=g(j);
       return temp;
     }

  9.  (10 pts) Write one prototype for the function "g" so that the following
   lines of code will all compile.
                double  y[20][30],z[40][30];
                int t[10];
                IntStack  st(9);//See problem 2 for the definition of IntStack
                g(2,   3,t   ,y[5][3],y);
                g(5.0,st,z[4],y[9][1],z);

        template <class T,class U>
        void g(T a, U b,T c[],double d,double e[][30]);