CSc 17  Test 2   Wednesday  28 November 2001
>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<
1. (10 pts) Using the algorithms discussed in class for building a balanced
binary tree for sorting integers, draw a picture of the tree after each
of the numbers listed in (a) are added to the tree in the order given.
Repeat the exercise for the numbers in (b).
  (a)  16 -4  28 35 20 40
     16  -->   16    -->   16   -->   16        -->   16   -->    16
              /           /  \       /  \            /  \        /  \
            -4          -4   28    -4   28         -4   28     -4   28
                                          \            /  \        /  \
                                           35         20   35    20   35
                                                                        \
                                                                        40
    ==>        28
              /  \
            16    35
           /  \     \
         -4   20    40

  (b)  16 -4  28 -2 8 12
     16  -->   16    -->   16   -->   16        -->   16   -->    -2
              /           /  \       /  \            /  \        /  \
            -4          -4   28    -4   28         -4    28    -4   16
                                     \               \             /  \
                                     -2               -2          8    28
                                                        \
                                                         8
    ==>        -2      -->   -2      ==>      8
              /  \          /  \             / \
            -4    16      -4   16          -2  16
                /  \          /  \         /  /  \
               8    28       8   28       -4 12  28
                              \
                              12

2. (25 pts)  Write a function inList().  If we have the declarations
int n,y,x[20]; then the call inList(y,x,n) should return the index of the
first entry among the first n entries in x[] which equals y.  If none of
the first n entries in x[] equals y, then inList(y,x,n) should return -1.
  int inList(int y, int x[],int n)
   {int loc;
    loc=0;
    while(loc<n && x[loc]!=y)
      loc++;
    if(loc<n)
      return loc;
    return -1;
   }
3.  (25 pts) The selection sort uses the following algorithm to sort a
list of doubles.  The largest entry is placed in the first location, the
second largest entry is placed in the second location, etc.  Write the
function sort() which sorts a list of doubles using the above algorithm.
In particular, for the declarations double x[20]; int n; the call
sort(x,n) returns with the first n entries in x in descending order.
    void sort(double x[],int n)
    {for(int j=0;j<n-1;j++)
     {int maxLoc=j;
      for(int loc=j+1;loc<n;loc++)
        if(x[maxLoc]<x[loc])
          maxLoc=loc;
      int temp=x[j];
      x[j]=x[maxLoc];
      x[maxLoc]=temp;
     }
   }
4.  (15 pts)  Given the class Link and the function q() below, provide the
documentation for the function q().
    class Link
    {public:
       double x;
       Link *next;
    };
    bool q(Link *r,Link *t)
    {while(r!=NULL && t!=NULL && r->x==t->x)
      {r=r->next;
       t=t->next;
      }
      return r==NULL && t==NULL;
    }

   Purpose:  To determine whether the two link lists with head pointers
             r and t are identical.
   Preconditions:  r and t point to well-formed linked lists.  In particular,
             in each list eventually a Link has next == NULL, i.e., neither
             list has a Link pointing to a previous Link in the list.
   Postcondtions:  The linked lists are unchanged.  The value 'true' is
             returned if the two are identical. Otherwise 'false' is returned.
5.  (25 pts)  We define the "depth" of the root of a tree to be 1.  We
define the depth of a child to be one more than the depth of its parent.
Assume class Node below is used to build a binary tree.  Write a function
markDepth which traverses the binary tree and sets each node in the tree
to the correct depth.  If rt is declared as Node *rt, the call to mark
the depth of each node of the binary tree whose root is rt would be
markDepth(rt,1).
  class Node
  {public:
     int x,depth;
     Node *child[2];
  };

 void markDepth(Node *rt,int d)
  { if(rt!=NULL)
     {rt->depth=d;
      markDepth(rt->child[0],d+1);
      markDepth(rt->child[1],d+1);
     }
  }