CSc 109 Test 1  1 March 2000
   >>>>>>>>>>>>>>[SUGGESTED ANSWERS]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
   1.  Class Rect below is meant to represent a rectangle.
   Write the declaration and definition of a subclass of Rect called Box,
   which represents a 3-dimensional box.    You should note that Rect has
   no protected members and that Box should have only one more data member
   beyond those it inherits (len, wid).  Including your declaration and
   definition (code) should allow the following statement to compile.

     cout<<"The volume of the 2x3x4 box is "<<box(2,3,4).volume()<<endl;

    class Rect{
     public:
      Rect();
      Rect(double le,double wi); //create a box of length le and width wi
      Rect(const Rect & r);
      double area();
     private:
      double len, wid;
    };

   class Box : public Rect{
     public:
       Box(const Box & b);
       Box(double le,double wi, double ht);
       double volume();
     private:
       double high;
   };

   Box::Box(double le, double wi, double ht):Rect(le,wi){
      high=ht;
   }

   Box::Box(const Box &b):Rect(b){
     high=b.high;
   }

   double Box::volume(){
     return area()*high;
   }

   2.  For the Simpletron program below, fill in the values in the table
   for PC and Accumulator for the first 20 steps or until a halt, when the
   program  executes.  Indicate undefined values with ????.  List the initial
   memory.  When memory changes, indicate the new value and the value of the
   program counter in parentheses (e.g., if location 5 changes to 84 when the
   program counter is 9, write 84(9) at Addr 5).

    Program       PC  Accumulator                 Memory
    -------     ------------------         -------------------------------
    1011       |_0___|__???_______|        Addr  Initial
    2012       |  1  |   10       |              Value
    3312       |-----|------------|        -------------------------------
    2113       |__2__|__100_______|         0  |1011 |300(5)|4300(9)|      |
    3311       |  3  |  100       |        --------------------------------
    2100       |-----|------------|         1  |2012 |      |       |      |
    3013       |__4__|__300_______|        --------------------------------
    3312       |  5  |  300       |         2  |3312 |      |       |      |
    3000       |-----|------------|        --------------------------------
    2100       |__6__|__400_______|         3  |2113 |      |       |      |
    4000       |  7  |  4000      |        --------------------------------
    0          |-----|------------|         4  |3311 |      |       |      |
    10         |__8__|__4300______|        --------------------------------
    0          |  9  |  4300      |         5  |2100 |      |       |      |
    END        |-----|------------|        --------------------------------
    3          |__0__|__4300______|         6  |3013 |      |       |      |
               |  halt            |        --------------------------------
               |-----|------------|         7  |3312 |      |       |      |
               |_____|____________|        --------------------------------
               |     |            |         8  |3000 |      |       |      |
               |-----|------------|        --------------------------------
               |_____|____________|         9  |2100 |      |       |      |
               |     |            |        --------------------------------
               |-----|------------|        10  |4000 |      |       |      |
               |_____|____________|        --------------------------------
               |     |            |        11  | 0   | 3(0) |       |      |
               |-----|------------|        --------------------------------
               |_____|____________|        12  | 10  |      |       |      |
               |     |            |        --------------------------------
               |-----|------------|        13  | 0   |100(3)|       |      |
               |_____|____________|        --------------------------------

 3.   Assume that we have a hash table with locations 0 through 4
    occupied.  Given a new item whose hash number is 88, find the location
    where it would be stored in the hash table and find the number of
    probes needed to place it in the table (unless it cannot be placed) when
      (1) The table size is 8, and a linear probe is used to resolve
          collisions.
      (2) The table size is 8, and a quadratic probe is used to
          resolved collions.
      (3) The table size is 11, and a linear probe is used to resolve
          collisions.
      (4) The table size is 11, and a quadratic probe is used to
          resolve collisions.

     (1)  88%8=0 --> 1 -->2 -->3 -->4 -->5   ==> 6 probes
     (2)  88%8=0 --> 1 -->4 -->9%8=1 -->16%8=0 -->25%8=1 -->36%8=4
              -->... never stops ==>no placement
     (3)  88%11=0 -->1 -->2 -->3 -->4 -->5   ==> 6 probes
     (4)  88%11=0 -->1 -->4 -->9  ==> 4 probes

  4.   It is normally a bad idea to use the same file name more than once when
  running a program from the command line, because the program may wipe out
  itself or the input file.  Write a program whose only purpose is to tell
  the user when he has entered two names that are the same on the command
  line.  If the program is stored in the file prog, then the first three
  lines below should display the message "okay" and the fourth and fifth
  the message "dufus".

    prog one two
    prog
    prog one
    prog one one
    prog one prog a b

  #include <fstream.h>

  void main(int argCt, char *argSt[]){
    for(int j=0;j<argCt-1;j++)
     for(int k=j+1;k<argCt;k++)
       if(strcmp(argSt[j],argSt[k])==0){
         cout<<"dufus\n";
         return;
       }
    cout<<"okay\n";
  }

  5.  Below are the complete declarations of class Key and of class Rek,
   and the partial declaration of class Table.  Write the definition (code)
   for the Table member function Delete().
  class Key{
  public:
    Key(char *str);
    Key();
    bool operator==(const Key & k);
    bool operator!=(const Key &k);
    void Key::operator=(const Key & sk);
  private:
    char * strng;
  };

  class Rek{
  public:
    Rek(char *str,int d);
    Rek();            //A Rek with key==""
    Key key()const;   //Return rekKey
    int getData();    //return data
    void operator = (const Rek & s);
  private:
    Key rekKey;
    int data;
  };

  class Table{
  public:
    Table(int n); //Allocate a table with size==n
    bool Delete(const Key & k); //remove an item whose Key is k; return true
     ...                        //if and only if item found and removed
     ...//other Table stuff omitted
  private:
    Rek *table;
    int count, size;  //entries in table[0],...,table[count-1], count<=size
  };

bool Table::Delete(const Key &k){
  int loc;
  loc=0;
  while(loc<count && table[loc].key()!=k)
    loc++;
  if(loc==count)
   return false;
  delete table[loc];
  for(int j=loc;j<loc-1;j++)
   table[j]=table[j+1];
  count--;
  return true;
}