CSc 17  Test 2        Thursday   8 April 1999
  .....>>>>>>>>>>>>>>>>>>>>>>ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  1.  (10 pts)  Assume the following data structure is used to create a linked
  list:       class Link{public: int key,next; };
              class LinkedList{
                private: int head,count; Link data[10];
                public: //other stufff
              }
  Further suppose that data have been loaded into the array as depicted in the
  first row of the table below but that the data are not yet linked
  together. Complete the first row by filling in the value for head.  Also,
  fill out as many of the remaining rows as is necessary to show the state of
  the data structure after each of the entries Link[0], Link[1],..., Link[3]
  is added to the list. Note that a link is depicted as ------
                                                        | key |
                                                        | next|
                                                        -------
    head count Link[0] Link[1] Link[2] Link[3] Link[4] Link[5] .......
   -----------------------------------------------------------------------
   | -1 |  4  |  5    |   6   |   -3  |   10  |       |       | .......
   -----------|       |       |       |       |       |       | .......
   -----------------------------------------------------------------------
   |  0 |  4  |  5    |   6   |   -3  |   10  |       |       | .......
   -----------| -1    |       |       |       |       |       | .......
   -----------------------------------------------------------------------
   |  0 |  4  |  5    |   6   |   -3  |   10  |       |       | .......
   -----------|  1    |  -1   |       |       |       |       | .......
   -----------------------------------------------------------------------
   |  2 |  4  |  5    |   6   |   -3  |   10  |       |       | .......
   -----------|  1    |  -1   |    0  |       |       |       | .......
   -----------------------------------------------------------------------
   |  2 |  4  |  5    |   6   |   -3  |   10  |       |       | .......
   -----------|  1    |   3   |    0  |   -1  |       |       | .......
   -----------------------------------------------------------------------
  2. (25 pts)  An array x[0], x[1],.....,x[n] is "symmetric" if listing the
  data in the order x[0], x[1],..., x[n] produces the same list as that
  obtained by listing the data in the order x[n], x[n-1],...,x[0].  Thus, the
  array x[0]=1, x[1]=2, x[2]=3, x[3]=3, x[4]=2, x[5]=1 is symmetric.  Write
  a recursive bool function symm() such that symm(x,0,n) returns true if the
  x is symmetric and false if it is not, where we have the declations
  double x[100]; int n; and where we can assume 0<=n<=99.  Your recursive
  function MUST use the following algorithm.  The array x[0],....x[n] is
  symmetric if the 0th and nth entries are equal and the array x[1],...,x[n-1]
  is symmetric.
     bool symm(double x [],int low, int high){
       if(low>=high)
        return true;
       else if(x[low]!=x[high])
        return false;
       else
        return symm(x,low+1,high-1);
    }
    //A terser solution:
    //return(low>=high ||(x[low]==x[high] && symm(x,low+1,high-1)));

  3. (25 pts)  Assume we have the class Link defined in question 1.  Write
  the prototypes and the definitions for a member function output() and for
  overloading the operator << so that a variable aLink, of type Link, responds
  to aLink.output(cout) by displaying key on cout and responds to
  cout << aLink by displaying key on cout.
    Prototypes(inside class Link):
      void output(ostream & out);
      friend ostream& operator<<(ostream &out,const Link & aLink);




    Definitions:
      void Link::output(ostream & out){
        out<<key;
      }
      ostream & operator<<(ostream &out,const Link & aLink){
         out<<aLink.key;
         return out;
      }

  4. (10 pts) For the code below state the output when the user enters

      a) 1                       >>>> Enter a value for x- One
      b) 2                       >>>> Enter a value for x- TwoThree
      c) 3                       >>>> Enter a value for x- Three
      d) 4                       >>>> Enter a value for x-

             int x;
             cout<<"Enter a value for x- ";
             cin>>x;
             switch(x){
               case 1: cout<<"One"; break;
               case 2: cout<<"Two";
               case 3: cout<<"Three";
             }

  5. (20 pts) The function quizzical() below lacks documentation.  Provide it.
  class Link{public: int key; *Link next};
  class LinkList{private: *Link head;
                 public: bool quizzical();
                 //....other stuff }
   //Purpose: Display the first entry in the list and remove it, if the
   //   first entry exists.  Otherwise, do nothing.
   //Precondition:  head is NULL or points to a Link whose next pointer
   //   is either NULL or pointing to another Link
   //Postcondition:  The first entry, if it exists, has been printed,
   //   and head now points to the next Link in the list.
   void LinkList::quizzical(){
      if(head!=NULL){
        cout<<(head->key);
        head=head->next;
      }
   }

   6. (10 pts)  State what appears on the screen when the function func(),
   defined below, is called.

    void func(){
      int a,b,*c,*d;
      c=&b;
      *c=5;
      b=3;
      cout<<"One "<<*c<<" "<<b<<endl;            One 3 3
      d=&a;
      *d=*c;
      d=c;
      b=4;
      cout<<"Two "<<*c<<" "<<*d<<" "<<a<<endl;   Two 4 4 3
    }