CSc 17 Final Examination  Friday  15 May 1998  8-11AM             Page 1

      >>>>>>>>>>>>>>>>>>>>ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  1.  (25 pts)  One should never retrieve the contents of a variable
   before one has stored a value in the variable.  An ADT SafeVar could
   prevent this error.  Consider the ADT SafeChar, with the following
   properties: (1) A character can be stored in a SafeChar; (2) The
   value of SafeChar can be retrieved only after (1) has occurred
   otherwise an error occurs. Write a class SafeChar which implements this
   ADT, i.e., write both the declaration and the definitions (implementation).

        class SafeChar
          {public:
              SafeChar();
              char get();
              void put(char ch);
           private:
              char kh;
              bool stored;
          };
        SafeChar::SafeChar()
           {stored=false;}
        void SafeChar::put(char ch)
           {kh=ch; stored=true;}
        char SafeChar::get()
           {if(!stored)
               {cout<<"Error: tried to access undefined value.\n"
                    <<"Press <enter> to quit program....";
                cin.get();
               }
            else return kh;
           }


  2.  (10 pts)  Expand the above specification of the ADT so that it allows
   input and output.
      (1) The same as above. (2) Read from a file into SafeChar.
      (3) Retrieve a char from SafeChar only after either (1) or (2) has
          occurred, else an error.
      (4) Write the contents of SafeChar to a file only after either (1)
          or (2) has occurred, else an error.

  3.  (20 pts)  Write a recursive function REVERSE() such for the
   declarations  int first, last, nums[20]; the call
   REVERSE(first,last,nums) reverses the order of the entries in nums
   between (and including) locations first and last.  For example,
   if nums=[5,6,2,3,4,7,2,6,....], after the call REVERSE(2,5,nums)
   nums=[5,6,7,4,3,2,2,6,...]. YOU MUST USE THE FOLLOWING ALGORITHM: TO
   REVERSE THE NUMBERS BETWEEN FIRST AND LAST SWAP THE NUMBERS IN FIRST
   AND LAST AND THEN REVERSE ALL THE NUMBERS IN BETWEEN.
     void reverse(int first, int last, int ray[])
       { if(first<last)
          {int temp=ray[first];
            ray[first]=ray[last];
            ray[last]=temp;
            reverse(first+1,last-1,ray);
          }
       }

  4.  (10 pts)  Write down a solution to the 5-queens problem:

          --------------
         |  |xx|  |  |  |
          --------------
         |  |  |  |xx|  |
          --------------
         |xx|  |  |  |  |
          --------------
         |  |  |xx|  |  |
          --------------
         |  |  |  |  |xx|
          --------------

  5.  (10 pts)  Write single prototypes for each of the two template functions
    aFunc and bFunc so that all the following calls will compile.
       aFunc(8,9,10);
       aFunc("ppp","ccc","ddd");
       bFunc(8,"ppppp");
       bFunc(9.0,8);
       bFunc("pp","pppp");
       bFunc(6,"pp");

      template <class T>
        aFunc(T a, T b, T c);
      template <class T, class U>
        bFunc(T a, U b);


  6.  (10 pts) Given the following data structure, write the pre- and
   post-conditions for the function X():
        class ONE
         { public:
              int key;
              ONE *child[];
         }

      void X(ONE *rt,int val)
      //Pre-Conditions: rt points to an allocated node or NULL and so do
                       all of rt's descendants.


      //Post-Conditions: rt is unchanged, all values in the tree larger
                         than val have been printed.



       {if (rt!=NULL)
            {X(rt->child[0],val);
             if(r->key>val)
               cout<<rt->key;
             X(rt->child[1],val);
            }
       }

  7.  (25 pts) Write a function CountLines() so that when the following
    fragment of code is executed the number of lines of text in the file
    FINAL.TXT is displayed on the screen:

       ifstream in("FINAL.TXT");

       cout << "The file FINAL.TXT has "<<CountLines(in)
            <<" lines of text.\n";

       int CountLines(istream & in)
        {char ch;
         int count;
         count=0;
         while (!in.eof())
          {do
            {if(in.eof())
               ch='\n';
             else in.get(ch);
            } while (ch!='\n');
           count++;
          }
         return count;
        }

  8.  (10 pts)  Assume that the classes Stack and Queue have been defined
    as in class.  What is the output when the following fragment is executed?

    Stack X(10);
    Queue Y(10);

    for (int j=2; j<15; j+=3)
      { X.push(j);
        X.push(3*j);
        Y.enQueue(2*j);
      }
    for (int j=1; j<=10; j++)
      { Y.enQueue(X.pop());
        cout<<Y.deQueue()<<" ";
      }

    4 10 16 22 28 42 14 33 11 24
  9.  (25 pts) Given the declarations  int first, last, nums[20]; write
    a function "Absolute()" such that after the call
    "Absolute(nums,first,last)"
    the numbers in "nums" in locations "first" through "last" inclusive
    have been replaced with their absolute values.
       void Absolute(int n[],int f, int lst)
         {for (int loc=f;loc<=lst;loc++)
            if (n[loc]<0)
               n[loc]= -n[loc];
         }

  10.  (25 pts) Given the declarations
                       class Node
                         {public:
                           float key;
                           Node * next;
                         }
                       Node *head;
       write a function "absolute()" such that when head points to a properly
       formed linked list (with the last Node in the list pointing to NULL)
       after the call "absolute(head)" the numbers stored in the nodes have
       been replaced with their absolute values.
         void absolute(Node *head)
           {while(head!=NULL)
              {if(head->key<0)
                 head->key=-head->key;
               head=head->next;
              }
           }


  11.  (20 pts) Given the declarations  int last,y[5]; write an int-valued
       function "numerate()" such that when "last" has some value between
       0 and 4 and locations 0, 1, ..., last of y contain digits, the
       call "numerate(y,last)" returns an int comprised of the digits in
       y in locations 0 through last.  Thus, if last=2 and y=[2,3,2,3,4]
       then "numerate(y,2)" returns the value 232.
           int numerate(int y[],int last)
            {int temp;
             temp=0;
             for(int j=0;j<=last;j++)
               temp=10*temp+y[j];
             return temp;
            };



  12.  (10 pts)Given the function and variable declarations below, state
         what output is generated by the code below the dashed line.

          void b(int & x, int &y)

           {x++;
            y+=x;
            cout <<x<<" "<<y<<" ";
           }
          void a(int & x, int y,int & z)
          { x=y+z;
            y=y+z;
            b(x,z);
            cout << x << " " << y << " " << z<<endl; }
     -----------------------------------------------------------
      int u=1,v=2,w=3;
      a(u,v,w);                                     6 9 6 5 9
                                                    6 2 9
      cout << u << " " << v << " " << w << endl;
      b(v,v);                                       6 6