CSc 17  Test 2    24 June 1999                     Page 1
      >>>>>>>>>>>>>>>>ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
     1.  (15 pts) (a) Using the standard algorithm for building a binary
     tree for storing numbers in order: (1) show the state of the tree
     after the numbers 15, 12, 14, 6, and 9 have been added to an empty
     tree in that order;  (2) then show the state of the tree after the
     numbers 8, 17, and 16 have also been added to the tree in that order.

                     15                 15
                    /                  /   \
                  12                 12     17
                 /  \               /  \    /
               6    14             6   14  16
                \                   \
                 9                   9
                                    /
                                   8
            (b)  Given the binary tree         2
                                              /  \
                                            /      \
                                           3        9
                                         /   \     /  \
                                        19   -7   8    3
      list the numbers resulting from
       (1) an in-order search of the tree       19 3 -7 2 8 9 3
       (2) a post-order search of the tree      19 -7 3 8 3 9 2
       (3) a pre-order search of the tree       2 3 19 -7 9 8 3
     2.  (10 pts)  What is the output when the following code is executed?
          char s[]="one\ntwo\nthree", t[20];
          for(int j=0;j<12;j++)
            t[j]=s[j];
          t[3]='-';
          t[8]='\0';
          cout<<t;                                  //one-two
          int *x;
          x=new int[10];
          for(int j=0;j<10;j++)
            x[j]=j*j;
          cout<<endl<<(x+3)[4]<<" "<<(x-3)[4]<<endl;   //49 1
          int f,*g,*h,j;
          f=4;
          g=&f;
          h=g;
          *g=9;
          *h=8;
          cout<<f<<" "<<*g;                          //8 8

     3.  (25 pts)  The key idea of the bubble sort involves scanning an
     array until all its adjacent elements are in order.  Write a function,
     sort, which is called as follows, sort(x,n), where x is an array of
     doubles and n is an int which gives the number of entries in the array.
     The function must use the bubble sort algorithm.
       void sort(double x[],int n){
         bool sorted;
         do{sorted=true;
            for(int j=1;j<n;j++)
             if(x[j]<x[j-1]){
               double temp=x[j];
                      x[j]=x[j-1];
                      x[j-1]=temp;
               sorted=false;
               }
         }while (!sorted);
      }
     4.  (25 pts)  Write a function "collect" which is called as follows,
     collect(x,xLast,y,yLast,z), where x, y, and z are arrays of doubles,
     and xLast and yLast are ints that count the numbers of entries in x and y,
     respectively.  After the call, z has the entries in x, followed by
     the entries in y.
        void collect(double x[], int xL, double y[],int yL,double z[]){
           for(int j=0;j<xL;j++)
             z[j]=x[j];
           for(int j=0;j<yL;j++)
             z[xL+j]=y[j];
        }
     5.  (25 pts)  Assume we use the following structure to build a linked
     list of doubles:   class Link{ public:  double  key;
                                    Link * next;    }
     Write the function "del2", which is called as follows, del2(list),
     where list is declared as  Link * list and is assumed to point to
     the first entry of a linked list (or NULL if the list is empty).
     The function del2 should remove the second entry in the list,
     provided it is there, and return a bool which is true if something
     has been removed and false otherwise.
       bool del2(Link *list){
         if(list==NULL || list->next==NULL)
            return false;
         Link *temp;
         temp=list->next;
         list->next=list->next->next;
         if(temp!=NULL)
          delete temp;
         return true;
       }