CSE 109   Final Examination  Monday 10 May 2004
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<
1.  Below is the declaration of class Word.  Write the declaration and
definitions (code) for a subclass of Word called MyWord such that the functions
below work as indicated.
class Word
{public:
  Word(char *st="");
  Word(char s);
  Word(const Word & w);
  ~Word();
  friend bool operator<(const Word &a, const Word &b);
  friend bool operator<=(const Word &a, const Word &b);
  friend bool operator>(const Word &a, const Word &b);
  friend bool operator>=(const Word &a, const Word &b);
  friend bool operator==(const Word &a, const Word &b);
  friend bool operator!=(const Word &a, const Word &b);
  Word operator=(const Word &w);
  friend ostream & operator <<(ostream &out,const Word &w);
 protected:
  char str[22];  //for storage of c-string
};
void upcase(MyWord &w)//make all lower case characters in w uppercase
{for(int j=0; j<w.length(); j++)
  if(w[j]>='a' && w[j]<='z')
    w[j]=char(w[j]-'a'+'A'); }
void upAndOut(const MyWord & w)//display w in uppercase letters
{for(int j=0; j<w.length(); j++)
  if(w[j]>='a' && w[j]<='z')
    cout<<char(w[j]-'a'+'A'); }
void test()   // test the constructors
{MyWord  v('a'),r("hello"), x(r);
 x[0]='H';
 cout<<v<<r<<x<<endl;//display "ahelloHello"}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
class MyWord:public Word
{public:
  MyWord(char *st="");
  MyWord(char s);
  MyWord(const MyWord&w);
  int length()const;
  char & operator[](int index);
  char operator[](int index)const;
 private:
   int size;
   static void check(bool b, char *mess);
 };

 MyWord::MyWord(char *st):Word(st){size=0;
                               while(size<22 && str[size]!='\0')
                                 size++;
                              }
MyWord::MyWord(char s):Word(s){size=1;}

MyWord::MyWord(const MyWord&w):Word(w){size=w.size;}

int MyWord::length()const{return size;}

char & MyWord::operator[](int index)
   {check(index>=0 && index<size,"Index out of range");
    return str[index];}

char MyWord::operator[](int index)const
   {check(index>=0 && index<size,"Index out of range");
    return str[index];}

void MyWord::check(bool b, char *mess)
     {if(!b)
        {cerr<<"ERROR: "<<mess<<endl;
        exit(1);
        }
     }
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
2. Write a program that reads a line of text from cin and determines whether
it obeys the syntax for Exp given by the syntax diagrams below.  It should
display "Good syntax" if the line is correct and "Bad syntax if the line is
incorrect. Note [] represents a rectangle, and () a circle.  Blanks and tabs
should not be allowed.
          Exp  ----->(a)-->[T]-->(a)---->
                  |                   |
                  +------>[T]---------+

                    +<-----------------+
                    |                  |
                    v                  |
           T  -------->(b)-->[F]-->(b)----+
                  |                       |
                  +------>[F]-------------+---->

           F  ----->(c)-->[T]-->(c)---->
                  |                   |
                  +------>(d)---------+
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
void getCh(char &ch);
void exp(char&ch);
void T(char&ch);
void F(char &ch);
void check(bool b);

int main(){
  char ch;
  ch=' ';
  getCh(ch);
  exp(ch);
  check(ch=='\n');
  cout<<"Good Syntax\n";
  return 0;
}

void getCh(char &ch)
{if(ch!='\n')
  cin.get(ch);
}

void exp(char &ch)
{if(ch=='a')
  {getCh(ch);
   T(ch);
   check(ch=='a');
   getCh(ch);
  }
 else
   T(ch);
}

void T(char &ch)
{if(ch=='b')
  while(ch=='b')
   {getCh(ch);
    F(ch);
    check(ch=='b');
    getCh(ch);
   }
 else
  F(ch);
}

void F(char&ch)
{if(ch=='c')
  {getCh(ch);
   T(ch);
   check(ch=='c');
   getCh(ch);
  }
 else
 {check(ch=='d');
  getCh(ch);
 }
}

void check(bool b)
{if(!b)
  {cerr<<"Bad syntax\n";
  exit(1);
  }
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
3.  Write the declaration and definitions (code) for the a class Lex which
reads input from cin and, when next() is called, returns distinct int constants
corresponding to the following symbols:  Lex::READ for "read", Lex::HALT for
"halt", Lex::PLUS for "+", Lex::PLUSPLUS for "++", Lex::ENDOFLINE for "\n",
and Lex::JUNK for anything else.  The method next() should ignore blanks and
tabs.  You may assume class Word from question 1.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
class Lex
{public:
  static const int READ=0, HALT=1, PLUS=2, PLUSPLUS=3, ENDOFLINE=4, JUNK=5;
  Lex();
  int next();
 private:
 int getWord(char&ch);
 char ch;
};

Lex::Lex(){cin.get(ch);}

int Lex::getWord(char &ch)
{ int loc;
  char w[6];
  loc=0;
   while(ch>='a' && ch<='z')
    {if(loc<5)
      {w[loc]=ch;
       loc++;
      }
     cin.get(ch);
    }
   w[loc]='\0';
   if(Word(w)=="read")
    return READ;
   else if(Word(w)=="halt")
    return HALT;
   else return JUNK;
}

int Lex::next()
{while(ch==' ' || ch=='\t')
  cin.get(ch);
 if(ch>='a' && ch<='z')
  return getWord(ch);
 else switch(ch)
  {case '\n': cin.get(ch); return ENDOFLINE;
   case '+' : cin.get(ch);
              if(ch!='+')
                return PLUS;
              cin.get(ch);
              return PLUSPLUS;
   default: cin.get(ch); return JUNK;
 }
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
4. Write a program that reads a line of input and writes it out to the screen.
If the user calls the program with the name of a file that exists, the input
should be the first line in the file. If the user calls the program without
specifying a file or the file specified does not exist, then the input
should be from the screen.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <fstream.h>

void line(istream &in);

int main(int ct,char **arg)
{ifstream fin;
 if(ct==1)
  line(cin);
 else
  {fin.open(arg[1]);
   if(fin.good())
    line(fin);
   else
    line(cin);
  }
}

void line(istream &in)
{char ch;
 in.get(ch);
 while(in.good() && ch!='\n')
  {cout<<ch;
   in.get(ch);
  }
}
5. For each question (a) and (b) you are given the following tree structure
   and you should show the state of the tree after each item is added to the
   tree, assuming that the ascending order of the elements is preserved.

                     (15)
                     /   \
                   (10) (30)

(a) Assume the above tree is a binary tree and add the following values:
     20, 40, 19, 35, 0, 50
(b) Now assume the same tree above is a Btree of order 1 and add the same
    values as in step (a).
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
(a)            (15)
             /      \
          (10)    (30)
           /       / \
        (0)     (20) (40)
               /    /   \
             (19)  (35) (50)
(b)
                    (15)
                 /       \
             (10)    (20, 30, 40)


                    (15, 30)
                 /     |     \
               (10)   (20) (40)


                   (15, 30)
             /         |         \
            (0,10) (19, 20) (35,40,50)


          (15,        30,        40  )
           /       \         \        \
          (0,10)  (19, 20)  (35)      (50)


                         (30)
                   /              \
                (15)               (40)
               /     \             /   \
            (0,10) (19,20)       (35) (50)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
6. Create a class called Stack that has the properties of a stack. Write the
class declaration and definitions (code) so that class Stack can do the
following, where we assume class Word from question 1.

int main()
{
   Stack <double> a;
   Stack  <Word> b;
   a.push(2.5);
   cout << a.pop();
   b.push("hello");
   cout << b.pop();
   return 0;
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <fstream.h>
#include "word.cc"
template <class T>
class Stack
{public:
  Stack();
  Stack& push(T t);
  T pop();
private:
  int top;
  T stack[40];
  static void check(bool b,char *mess);
};
template <class T>
Stack<T>::Stack()
  {top = 0;}
template <class T>
Stack<T> & Stack<T>::push(T n)
  {check(top < 40,"stack overflow");
   stack[top]=n;
   top++;
   return  *this;
  }
template <class T>
T Stack<T>::pop()
  {check(top > 0,"stack underflow");
   top--;
   return stack[top];
  }
template <class T>
void Stack<T>::check(bool b,char *mess)
{if(!b)
  {cerr<<"ERROR[Stack<>]: "<<mess<<endl;
   exit(1);
  }
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
7. Below is a 17-entry hash table. Assume the quadratic probe discussed in
class was used to construct the table. Assume the table stores integers, and
uses the integer for the hash number. Use the algorithms discussed in class
for answering the questions (a), (b), (c), and (d). Question (e) refers to
the second table.
        0   1   2   3   4  5   6   7   8   9   10  11  12 13  14  15   16
      ---------------------------------------------------------------------
      | 51|69 |   |20| 68|   |   |   |   | 60|   |   |   |   |   | 15|   |
      ---------------------------------------------------------------------
a. If 85 was stored next, where would it be stored and why? (If collision(s)
   explain where?)
b. If 119 was stored next, after 85 was stored, where would it be stored and
   why?(If collision(s) explain where?)
c. Was the number 51 stored in the array before 68? Why or Why not?
d. Based on the size of the hash table, what is the maximum number of
   elements I can store in this array in order to have efficient hashing and
   a dependable quadratic probe.
e. Explain why adding 32 to the hash table below is problematic.

        0   1   2   3   4  5   6   7   8   9   10  11  12 13  14  15
      ----------------------------------------------------------------
      | 48|65 |   |  | 64|   |   |   |   | 25|   |   |   |   |   |  |
      ----------------------------------------------------------------
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
(a) (b)
        0   1   2   3   4  5   6   7   8   9   10  11  12 13  14  15   16
      ---------------------------------------------------------------------
      | 51|69 |   |20| 68|   |   |   |119| 60|   |   |   |   |   | 15| 85 |
      ---------------------------------------------------------------------
(3) 51 was stored before 68 because 68 is divisible by 17 so it collided with
    0 and then was placed in 4.
(4) A maximum of 17/2 = 8 elements can be stored in the hash table
(5) The size of a good table should be prime.  The second table has 16 elements
    which is not a prime number. When the table size is notP prime a quadratic
    probe fails to have the property that at least half the table will be
    probed before the same place is probed twice, in this case a quadratic
    will never succeed, only probing locations 0,1,4 and 9 forever.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
8. Given the classes and program below, state the output of the program when
   it is executed.
 #include <fstream.h>
  class A
    {public:
         A(){k=0, j=10;}
         virtual int y(){return x();}
         int x(){return k + j;}
         int z(){return x() + y() ;}
         int k,j;
  };
  class B:public A
    { public: B(){k=5, j= 0;}
          int y(){return k;}
          int x(){return k + 100;}
  };

  int main()
   { A a;
     B b;
     cout<<a.y()<<" "<<a.x()<<" "<<a.z()<<endl<<endl;
     cout<<b.y()<<" "<<b.x()<<" "<<b.z()<<" " << b.A::y()<< " " <<b.A::x()<< endl;
   }
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
   10 10 20

   5 105 10 5 5