CSc 17 Final Examination  Wednesday 12 May 1999 4 PM      Page 1
    !!!!!!!!!!!!!!!SUGGESTED ANSWERS!!!!!!!!!!!!!!!!!
  1.  (10 pts)  Assume class Staque implements an ADT which has the properties
  of both a stack and a queue.  Further assume that Staque has the member
  functions  push(int), enqueue(int), int pop(), int dequeue(), bool full(),
  and empty(), where the functions push and enqueue have exactly the same
  effect. For the code below, list the contents of aStaque after each push,
  pop, enqueue, or dequeue is called. List the entries from left to right,
  with the latest entry on the right.
    Staque aStaque(100);  //create a Staque with capacity for 100 entries
    for(int j=5;j<7;j++){
      aStaque.push(j);                           5
      aStaque.push(j+10);                        5 15
      aStaque.enqueue(aStaque.dequeue());        15 5
    }                                            15 5 6
    while(!aStaque.empty()){                     15 5 6 16
       aStaque.pop();                            5 6 16 15
       aStaque.dequeue();                        5 6 16
    }                                            6 16
                                                 6
                                                 <empty>
  2.  (25 pts)  Assume we have the following data structure for building a
  binary tree:       class TNode{ public: int data;
                                          TNode *child[2];  };
                     class Tree{ private: TNode *root;
                                     //possibly other stuff...
                                 public:   //other stuff....
                               };
  Write a member function for Tree called recPrintRange such that the call
  recPrintRange(root,low,high) displays on the screen all entries in the
  tree that are greater than the int low and less than the int high.
   void Tree::recPrintRange(TNode *rt,int low, int high){
    if(rt!=NULL){
      if(rt->data>low && rt->data<high)
       cout<<rt->data<<endl;
      recPrintRange(rt->child[0],low,high);
      recPrintRange(rt->child[1],low,high);
   }
  }
  3.  (20 pts)  For class Tree in question 2, I wrote the following member
  function which assumes a Tree constructed in ascending order, but I forgot
  to provide documentation.  Provide it.
  //Purpose: To return the largest entry in the tree.  If the tree is
  //  emtpy, return 0.
  //Pre-condition(s):  The TNodes actually form a binary tree; each value
  //  of data is valid; each root and each child are defined;  There is only
  //  one way to go from the root to any child.
  //Post-condition(s):  The tree is unchanged.  The largest value (or 0 if
  //   the tree is empty) has been returned.
    int Tree::Puzzling(){
      TNode *temp;
      if(root!=NULL){  temp=root;
                           while(temp->child[1]!=NULL)
                             temp=temp->child[1];
                           return temp->data;
                         }
          else return 0;
        }

  4.  (20 pts) For the class TNode in question 2 overload the << operator
  so that for the declaration TNode t, the statement  "cout<<t" displays
  t.data on the screen.  Write both the prototype and the definition.

  friend ostream & operator <<(ostream &out,const TNode &t);
  ostream & operator <<(ostream &out,const TNode &t){
    out<<t.data;
      return out;
  }
  5.  (20 pts) For the class TNode in question 2 write the function "output"
  so that for the declaration TNode t, the statement  "t.output(cout)" displays
  t.data on the screen.  Write both the prototype and the definition.

  void output(ostream &out);
  void TNode::output(ostream&out){
    out<<data;
  }
  6.  (30 pts) Suppose we have the declaration: int x[100], first, last.
  Suppose the call sum(x,first,last) returns the sum of x[first],
  x[first+1], ..., x[last].  Write a version of sum that uses the following
  recursvie algorithm:  To sum the numbers between first and last, inclusive,
  take the entry in the middle and add it to the sum of the entries to the
  left of the entry in the middle and the sum of the entries to the right of
  the entry in the middle.
  int sum(int x[],int first, int last){
     if(first>last)
       return 0;
     if(first==last)
       return x[first];
     int middle=(first+last)/2;
     return(sum(x,first,middle-1)+x[middle]+sum(x,middle+1,last));
  }
  7.  (10 pts) Write one, and only one, definition of the function swap
  so that the following code compiles (even though the code may not make
  much sense).  Swap is supposed to interchange the values of its two
  arguments.
     int a,b;
     TNode c,d;  //TNode is defined in question 2
     swap(a,b);
     swap(c,d);
  template <class T>
  void swap(T &u,T&v){
    T temp;
    temp=u;
    u=v;
    v=temp;
  }
  8.  (5 pts)  What is the output of the following code?
    char line[]="One fine day", *p;
    p=line;
    cout<<line[4]<<p[5]<<endl;                   fi
    cout<<p<<endl;                               One fine day
    cout<<(p+1)[4]<<endl;                        i
    cout<<(p+1)<<endl;                           ne fine day
    line[3]='\0';
    cout<<line<<endl;                            One
  9.  (5 pts)  Write a prototype for the function junk so that the
  following code will compile:
        int x[5], y[5][2], z[2][4][2], w[5][4][2];
        junk(x,z,z[3]);
        junk(y[2],w,y);
        junk(w[3][3],w,y);
    void junk(int x[],int[][4][2],int [][2]);
  10.  (30 pts)  Write a function "charCount" which counts the number of
  times a given character appears as the first character on a line in a file.
  In particular, suppose we have the declaration:  istream in;
  The call charCount(in,'a') should return the number of times the character
  'a' appears as the first character of a line in the file "in".  If the file
  contained the lines of this paragraph, right justified, then the call
  charCount(in,'c') would return 4 (c appears on lines 6 thorugh 9), and the
  call charCount(in,'T') would return 1 (T appears on line 4).  Your function
  can assume the file is opened and at the beginning.
   int charCount(istream &in,char target){
    char ch;
    int count;

    count=0;
    in.get(ch);
    while(!in.eof()){
       if(ch==target)
         count++;
       while(ch!='\n' && !in.eof())
           in.get(ch);
       if(!in.eof())
         in.get(ch);
    }
    return count;
   }
  11.  (25 pts)  Write a function "sort" which sorts an array of doubles into
  ascending order.  In particular, if x is an array of doubles, and n is an
  int which counts the number of entries in x, after the call sort(x,n) the
  first n entries in x should be in ascending order.
   void sort(double x[],int last){
     bool sorted;
     do{
       sorted=true;
       for(int j=1;j<last;j++)
        if(x[j-1]>x[j]){
          swap(x[j-1],x[j]);   //use the swap of question 7
          sorted=false;
        }
     }while(!sorted);
   }