Midterm 2 Solution

CS 23

April 18, 1997

1. Short Answer Problem. Answer each question. Each question is worth 5 points.
   1. If you want to make use of polymorphism, what type of inheritance should be used in classes derived from a base class? Why?

      Public inheritance, because it yields the IS-A relationship between derived classes and the base class. Overridden virtual functions would also be necessary.

   2. Name and define the three class member access classifications.
      1. Public --- any function can access public members.

      2. Protected --- only member functions and member functions of derived classes can access protected members.

      3. Private --- only member functions can access private members.

   3. We know that we can construct a queue using a list. Is it possible to construct a list using a queue (which itself is not constructed from a list)? Briefly explain.

      Yes. Here is a sketch of insert():

      // Assume data members: List l and int count.
      
      Insert(int item, int pos)
      {
         validate pos against count;
         delete pos - 1 items from l, re-inserting each at tail;
         insert item;
         delete count - (pos - 1) items from l, re-insert each at tail;
         increment count;
      }
      

      delete() is similar.

   4. Would a queue or a stack be used in converting an infix expression to postfix? Explain.

      A stack, because of expressions such as a * (b + c) and a + b * c in which a stack's LIFO property is necessary in positioning the operators in the correct order in the postfix expression.

   5. In writing a function to reverse a string, would you make use of a queue or a stack? Explain.

      A stack, because of its LIFO property.

2. Essay. Answer each question.
   1. (10 pts.) You need a queue, but, alas, all you have available are stacks. Use pseudocode to show how to implement queue insert and delete using two stacks, A and B. (It is permissible to write statements such as, ``Pop everything from A, simultaneously pushing each item onto B.'')

      Qinsert(int item)
      {
         pop everything from B and push onto A;
         push item onto A;
      }
      
      
      Qdelete(int &item)   // Variation on the standard theme.
      {
         pop everything from A and push onto B;
         pop an item from B and return through item parameter.
      }
      

   2. (15 pts.) What is printed by the following program? Will the program compile if private inheritance is used? Why or why not?

      #include <iostream.h>
      
      class Base
      {
       public:
         void F(void) { cout << "Flyers in 4\n"; }
         virtual void G(void) { cout << "Flyers in 5\n"; }
         virtual void H(void) { cout << "Flyers in 6\n"; }
      };
      
      class Derived : public Base
      {
       public:
         void F(void) { cout << "Penguins in 4\n"; }
         void G(void) { cout << "Penguins in 5\n"; }
      };
      
      int main()
      {
         Base B;
         Base *p;
         Derived D;
      
         p = &B;
         p->F();
         p->G();
         p->H();
      
         p = &D;
         p->F();
         p->G();
         p->H();
      
         return 0;
      }
      

      This is printed:

      Flyers in 4
      Flyers in 5
      Flyers in 6
      Flyers in 4
      Penguins in 5
      Flyers in 6
      

      The program will not compile if private inheritance is used. The pointer p within main is not permitted to point to Derived class instance D since formerly public members of Base are no longer so.

3. Programming Problem. Solve one of the two following problems. This problem is worth 25 points. Use the following pages to write your solution.
   1. Implement the following queue class. Terminate on error conditions (e.g., calling Head() on an empty queue.

      class Queue
      {
       private:
         double data[MAX];
         int head;   // Index of next item to be deleted.
         int tail;   // Index to use for next item to be inserted.
         int count;  // Number of items in queue.
      
       public:
         Queue(void) : head(0), tail(0), count(0) { }
         int IsEmpty(void);
         int IsFull(void);
         double Head(void);
         void Insert(double item);
         void Delete(void);
      };
      

      Solution:

      int Queue::IsEmpty(void)
      {
         return count == 0;
      }
      
      
      int Queue::IsFull(void)
      {
         return count == MAX;
      }
      
      
      double Queue::Head(void)
      {
         assert(!IsEmpty());
      
         return data[head];
      }
      
      
      void Queue::Insert(double item)
      {
         assert(!IsFull());
      
         data[tail] = item;
         ++count;
         tail = ++tail % MAX;
      }
      
      
      void Queue::Delete(void)
      {
         assert(!IsEmpty());
      
         --count;
         head = ++head % MAX;
      }